Abstract
This paper has as a major objective to present a unified overview and derivation of mixed-integer nonlinear programming (MINLP) techniques, Branch and Bound, Outer-Approximation, Generalized Benders and Extended Cutting Plane methods, as applied to nonlinear discrete optimization problems that are expressed in algebraic form. The solution of MINLP problems with convex functions is presented first, followed by a brief discussion on extensions for the nonconvex case. The solution of logic based representations, known as generalized disjunctive programs, is also described. Theoretical properties are presented, and numerical comparisons on a small process network problem.
Similar content being viewed by others
References
C. S. Adjiman, I. P. Androulakis, and C. A. Floudas, “Global optimization of mixed-integer nonlinear problems,” AIChE Journal vol. 16, no. 9, pp. 1769–1797, 2000.
E. Balas, “Disjunctive programming and a hierarchy of relaxations for discrete optimization problems,” SIAM J. Alg. Disc. Meth. vol. 6, pp. 466–486, 1985.
E. Balas, S. Ceria, and G. Cornuejols, “A lift-and-project cutting plane algorithm for mixed 0–1 programs,” Mathematical Programming vol. 58, pp. 295–324, 1993.
C. Barnhart, E. L. Johnson, G. L. Nemhauser, M.W. P. Savelsbergh, and P. H. Vance, “Branch-and-price: Column generation for solving huge integer programs,” Operations Research vol. 46, pp. 316–329, 1998.
M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming, John Wiley: New York, 1994.
N. Beaumont, “An algorithm for disjunctive programs,” European Journal of Operations Research vol. 48, pp. 362–371, 1991.
J. F. Benders, “Partitioning procedures for solving mixed-variables programming problems,” Numeri. Math. vol. 4, pp. 238–252, 1962.
L. T. Biegler, I. E. Grossmann, and A.W. Westerberg, Systematic Methods for Chemical Process Design, Prentice-Hall: Englewood Cliffs, NJ, 1997.
B. Borchers and J. E. Mitchell, “An improved branch and bound algorithm for mixed integer nonlinear programming,” Computers and Operations Research vol. 21, pp. 359–367, 1994.
A. Brooke, D. Kendrick, A. Meeraus, and R. Raman, “GAMS–Auser's guide,” available at www.gams.com, 1998.
S. Ceria and J. Soares, “Convex programming for disjunctive optimization,” Mathematical Programming vol. 86, no. 3, pp. 595–614, 1999.
R. J. Dakin, “A tree search algorithm for mixed-integer programming problems,” Computer Journal vol. 8, pp. 250–255, 1965.
Ding-Mei and R. W. H. Sargent, “A combined SQP and branch and bound algorithm for MINLP optimization,” Internal Report, Centre for Process Systems Engineering, London, 1992.
M. A. Duran and I. E. Grossmann, “An outer-approximation algorithm for a class of mixed-integer nonlinear programs,” Math Programming vol. 36, p. 307, 1986.
J. E. Falk and R. M. Soland, “An algorithm for separable nonconvex programming problems,” Management Science vol. 15, pp. 550–569, 1969.
R. Fletcher and S. Leyffer, “Solving mixed integer nonlinear programs by outer approximation,” Math Programming vol. 66, p. 327, 1994.
O. E. Flippo and A. H. G. Rinnoy Kan, “Decomposition in general mathematical programming,” Mathematical Programming vol. 60, pp. 361–382, 1993.
C. A. Floudas, Deterministic Global Optimization: Theory, Methods and Applications, Kluwer Academic Publishers: Dordrecht, The Netherlands, 2000.
A. M. Geoffrion, “Generalized benders decomposition,” Journal of Optimization Theory and Applications vol. 10, no. 4, pp. 237–260, 1972.
I. E. Grossmann, “Mixed-integer optimization techniques for algorithmic process synthesis,” Advances in Chemical Engineering, J. L. Anderson, ed., vol. 23: Process Synthesis, pp. 171–246, Academic Press: San Diego, 1996a.
I. E. Grossmann (ed.), “Global optimization in engineering design,” Kluwer: Dordrecht, 1996b.
I. E. Grossmann, J. A. Caballero, and H. Yeomans, “Advances in mathematical programming for automated design, integration and operation of chemical processes,” Korean J. Chem. Eng. vol. 16, pp. 407–426, 1999.
I. E. Grossmann and M. M. Daichendt, “New trends in optimization-based approaches for process synthesis,” Computers and Chemical Engineering vol. 20, pp. 665–683, 1996.
I. E. Grossmann and S. Lee, “Generalized disjunctive programming: Nonlinear convex hull relaxation,” to appear in Computational Optimization and Applications (2002).
I. E. Grossmann and Z. Kravanja, “Mixed-integer nonlinear programming: A survey of algorithms and applications,” in The IMA Volumes in Mathematics and its Applications, vol. 93: Large-Scale Optimization with Applications, Part II: Optimal Design and Control, Biegler, Coleman, Conn, and Santosa, eds, Springer-Verlag: Berlin, pp. 73–100, 1997.
I. E. Grossmann, J. Quesada, R. Raman and V. Voudouris, “Mixed integer optimization techniques for the design and scheduling of batch processes,” in Batch Processing Systems Engineering, G. V. Reklaitis, A. K. Sunol, D. W. T. Rippin, and O. Hortacsu, eds., Springer-Verlag: Berlin, pp. 451–494, 1996.
O. K. Gupta and V. Ravindran, “Branch and bound experiments in convex nonlinear integer programming,” Management Science vol. 31, no. 12, pp. 1533–1546, 1985.
J. N. Hooker and M. A. Osorio, “Mixed logical linear programming,” Discrete Applied Mathematics vol. 96/97, pp. 395–442, 1999.
J. N. Hooker, Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, Wiley: New York, 2000.
R. Horst and P. M. Tuy, Global Optimization: Deterministic Approaches, 3rd edn., Springer-Verlag: Berlin, 1996.
E. L. Johnson, G. L. Nemhauser, and M. W. P. Savelsbergh, “Progress in linear programming based branch-andbound algorithms: Exposition,” INFORMS Journal of Computing vol. 12, 2000.
J. Kallrath, “Mixed integer optimization in the chemical process industry: Experience, potential and future,” Trans. I.Chem E. vol. 78, part A, pp. 809–822, 2000.
J. E. Kelley Jr., “The cutting-plane method for solving convex programs,” Journal of SIAM vol. 8, pp. 703–712, 1960.
P. Kesavan and P. I. Barton, “Decomposition algorithms for nonconvex mixed-integer nonlinear programs,” American Institute of Chemical Engineering Symposium Series vol. 96, no. 323, pp. 458–461, 1999.
P. Kesavan and P. I. Barton, “Generalized branch-and-cut framework for mixed-integer nonlinear optimization problems,” Computers and Chem. Engng. vol. 24, pp. 1361–1366, 2000.
G. R. Kocis and I. E. Grossmann, “Relaxation strategy for the structural optimization of process flowsheets,” Ind. Eng. Chem. Res. vol. 26, p. 1869, 1987.
S. Lee and I. E. Grossmann, “New algorithms for nonlinear generalized disjunctive programming,” Computers and Chemical Engineering vol. 24, pp. 2125–2141, 2000.
S. Leyffer, “Deterministic methods for mixed-integer nonlinear programming,” Ph.D. Thesis, Department of Mathematics and Computer Science, University of Dundee, Dundee, 1993.
S. Leyffer, “Integrating SQP and branch and bound for mixed integer noninear programming,” Computational Optimization and Applications vol. 18, pp. 295–309, 2001.
T. L. Magnanti and R. T. Wong, “Acclerated benders decomposition: Algorithm enhancement and model selection criteria,” Operations Research vol. 29, pp. 464–484, 1981.
G. P. McCormick, “Computability of global solutions to factorable nonconvex programs: Part I–Convex underestimating problems,” Mathematical Programming vol. 10, pp. 147–175, 1976.
S. Nabar and L. Schrage, “Modeling and solving nonlinear integer programming problems,” Presented at Annual AIChE Meeting, Chicago, 1991.
G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley-Interscience: NewYork, 1988.
J. Pinto and I. E. Grossmann, “Assignment and sequencing models for the scheduling of chemical processes,” Annals of Operations Research vol. 81, pp. 433–466, 1998.
R. Pörn and T. Westerlund, “A cutting plane method for minimizing pseudo-convex functions in the mixed-integer case,” Computers and Chemical Engineering vol. 24, pp. 2655–2665, 2000.
I. Quesada and I. E. Grossmann, “An LP/NLP based branch and bound algorithm for convex MINLP optimization problems,” Computers and Chemical Engineering vol. 16, pp. 937–947, 1992.
I. E. Quesada and I. E. Grossmann, “A global optimization algorithm for linear fractional and bilinear programs,” Journal of Global Optimization vol. 6, pp. 39–76, 1995.
R. Raman and I. E. Grossmann, “Relation between MILP modelling and logical inference for chemical process synthesis,” Computers and Chemical Engineering vol. 15, p. 73, 1991.
R. Raman and I. E. Grossmann, “Symbolic integration of logic in mixed integer linear programming techniques for process synthesis,” Computers and Chemical Engineering vol. 17, p. 909, 1993.
R. Raman and I. E. Grossmann, “Modelling and computational techniques for logic based integer programming,” Computers and Chemical Engineering vol. 18, p. 563, 1994.
H. S. Ryoo and N. V. Sahinidis, “Global optimization of nonconvex NLPs and MINLPs with applications in process design,” Computers and Chem. Engng. vol. 19, no. 5, pp. 551–566, 1995.
N. V. Sahinidis, “BARON: A general purpose global optimization software package,” Journal of Global Optimization vol. 8, no. 2, pp. 201–205, 1996.
N. V. Sahinidis and I. E. Grossmann, “Convergence properties of generalized benders decomposition,” Computers and Chemical Engineering vol. 15, p. 481, 1991.
C. A. Schweiger and C. A. Floudas, “Process synthesis, design and control: A mixed integer optimal control framework,” in Proceedings of DYCOPS-5 on Dynamics and Control of Process Systems, 1998, pp. 189–194.
N. Shah, “Single and multisite planning and scheduling: Current status and future challenges,” AIChE Symp. Ser. vol. 94, no. 320, p. 75, 1998.
E. M. B. Smith and C. C. Pantelides, “A symbolic reformulation/spatial branch and bound algorithm for the global optimization of nonconvex MINLPs,” Computers and Chemical Engineering vol. 23, pp. 457–478, 1999.
R. Stubbs and S. Mehrotra, “A branch-and-cut method for 0–1 mixed convex programming,” Mathematical Programming vol. 86, no. 3, pp. 515–532, 1999.
M. Tawarmalani and N. V. Sahinidis, “Global optimization of mixed integer nonlinear programs: A theoretical and computational study,” Mathematical Programming submitted, 2000.
M. Türkay and I. E. Grossmann, “Alogic based outer-approximation algorithm for MINLP optimization of process flowsheets,” Computers and Chemical Enginering vol. 20, pp. 959–978, 1996.
A. Vecchietti and I. E. Grossmann, “LOGMIP: A discrete continuous nonlinear optimizer,” Computers and Chemical Engineering vol. 23, pp. 555–565, 1999.
A. Vecchietti and I. E. Grossmann, “Modeling issues and implementation of language for disjunctive programming,” Computers and Chemical Engineering vol. 24, pp. 2143–2155, 2000.
J. Viswanathan and I. E. Grossmann, “A combined penalty function and outer-approximation method for MINLP optimization,” Comput. Chem. Engng. vol. 14, p. 769, 1990.
T. Westerlund and F. Pettersson, “A cutting plane method for solving convex MINLP problems,” Computers and Chemical Engineering vol. 19, pp. S131–S136, 1995.
H. P. Williams, Mathematical Building in Mathematical Programming, John Wiley: Chichester, 1985.
X. Yuan, S. Zhang, L. Piboleau, and S. Domenech, “Une methode d'optimisation nonlineare en variables mixtes pour la conception de procedes,” RAIRO vol. 22, p. 331, 1988.
J. M. Zamora and I. E. Grossmann, “Abranch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms,” Journal of Gobal Optimization vol. 14, pp. 217–249, 1999.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Grossmann, I.E. Review of Nonlinear Mixed-Integer and Disjunctive Programming Techniques. Optimization and Engineering 3, 227–252 (2002). https://doi.org/10.1023/A:1021039126272
Issue Date:
DOI: https://doi.org/10.1023/A:1021039126272