Abstract
This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems.
In contrast, an integrated approach to solving MINLP problems is considered here. This new algorithm is based on branch-and-bound, but does not require the NLP problem at each node to be solved to optimality. Instead, branching is allowed after each iteration of the NLP solver. In this way, the nonlinear part of the MINLP problem is solved whilst searching the tree. The nonlinear solver that is considered in this paper is a Sequential Quadratic Programming solver.
A numerical comparison of the new method with nonlinear branch-and-bound is presented and a factor of up to 3 improvement over branch-and-bound is observed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B. Borchers and J.E. Mitchell, “An improved branch and bound algorithm for mixed integer nonlinear programming, ” Computers and Operations Research, vol. 21, no. 4, pp. 359–367, 1994.
B. Borchers and J.E. Mitchell, “A computational comparison of branch and bound and outer approximation methods for 0–1 mixed integer nonlinear programs, ” Computers and Operations Research, vol. 24, no. 8, pp. 699–701, 1997.
A.R. Conn, N.I.M. Gould, and Ph.L. Toint, LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release A), Springer Verlag: Heidelberg, 1992.
A.R. Conn, N.I.M. Gould, and Ph.L. Toint, “Methods for nonlinear constraints in optimization calculations, ” Report RAL-TR-96-042, Rutherford Appleton Laboratory, 1996. (To appear in The State of the Art in Numerical Analysis, I. Duff and G.A. Watson (Eds.)).
R.J. Dakin, “A tree search algorithm for mixed integer programming problems, ” Computer Journal, vol. 8, pp. 250–255, 1965.
J.E. Dennis, M. El-Alem, and K.A. Williamson, “A trust-region approach to nonlinear systems of equalities and inequalities, ” SIAM Journal on Optimization, vol. 9, pp. 291–315, 1999.
M. Duran and I.E. Grossmann, “An outer-approximation algorithm for a class of mixed-integer nonlinear programs, ” Mathematical Programming, vol. 36, pp. 307–339, 1986.
M. El-Hallabi and R.A. Tapia, “An inexact trust-region feasible-point algorithm for non-linear systems of equalities and inequalities, ” Technical Report TR-09, Department of Computational and Applied Mathematics, Rice University, Houston, Texas, USA, 1995.
R. Fletcher, Practical Methods of Optimization, 2nd ed., John Wiley: Chichester, 1987.
R. Fletcher and S. Leyffer, “Solving mixed integer nonlinear programs by outer approximation, ” Mathematical Programming, vol. 66, pp. 327–349, 1994.
R. Fletcher and S. Leyffer, “Nonlinear programming without a penalty function, ” Numerical Analysis Report NA/171, Department of Mathematics, University of Dundee, Sept. 1997.
R. Fletcher and S. Leyffer, “User manual for filter SQP, ” Numerical Analysis Report NA/181, Dundee University, April 1998.
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, Nonlinear and Mixed-Integer Optimization, Oxford University Press: New York, 1995.
A.M. Geoffrion, “Generalized benders decomposition, ” Journal of Optimization Theory and Applications, vol. 10, pp. 237–260, 1972.
I.E. Grossmann and Z. Kravanja, “Mixed-integer nonlinear programming: A survey of algorithms and applications, ” in Large-Scale Optimization with Applications, Part II: Optimal Design and Control, A.R. Conn, L.T. Biegler, T.F. Coleman, and F.N. Santosa (Eds.), Springer: New York, Berlin, 1997.
I.E. Grossmann and R.W.H. Sargent, “Optimal design of multipurpose batch plants, ” Ind. Engng. Chem. Process Des. Dev., vol. 18, pp. 343–348, 1979.
O.K. Gupta and A. Ravindran, “Branch and bound experiments in convex nonlinear integer programming, ” Management Science, vol. 31, pp. 1533–1546, 1985.
S.P. Han, “A globally convergent method for nonlinear programming, ” Journal of Optimization Theory and Applications, vol. 22, no. 3, pp. 297–309, 1977.
R. Horst and H. Tuy, Global Optimization: Deterministic Approaches, 2nd ed., Springer-Verlag: Berlin, 1993.
G.R. Kocis and I.E. Grossmann, “Global optimization of nonconvex mixed-integer nonlinear programming (MINLP) problems in process synthesis, ” Industrial Engineering Chemistry Research, vol. 27, pp. 1407–1421, 1988.
A.H. Land and A.G. Doig, “An automatic method for solving discrete programming problems, ” Econometrica, vol. 28, pp. 497–520, 1960.
M.J.D. Powell, “A fast algorithm for nonlinearly constrained optimization calculations, ” in Numerical Analysis, 1977, G.A. Watson (Ed.), Springer Verlag: Berlin 1978, pp. 144–157.
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.
A.J. Quist, R. van Geemert, J.E. Hoogenboom, T. Illés, E. de Klerk, C. Roos, and T. Terlaky, “Optimization of a nuclear reactor core reload pattern using nonlinear optimization and search heuristics, ” Draft paper, Delft University of Technology, Faculty of Applied Mathematics, Department of Operation Research, Mekelweg 4, 2628 CD Delft, The Netherlands, Sept. 1997.
R.A. Stubbs and S. Mehrotra, “A branch-and-cut method for 0–1 mixed convex programming, ” Technical report 96-01, Department of IE/MS, Northwestern University, Evanston, IL 60208, USA, Jan. 1996.
J. Viswanathan and I.E. Grossmann, “Optimal feed location and number of trays for distillation columns with multiple feeds, ” I&EC Research, vol. 32, pp. 2942–2949, 1993.
O.V. Volkovich, V.A. Roshchin, and I.V. Sergienko, “Models and methods of solution of quadratic integer programming problems, ” Cybernetics, vol. 23, pp. 289–305, 1987.
T. Westerlund, J. Isaksson, and I. Harjunkoski, “Solving a production optimization problem in the paper industry, ” Report 95-146-A, Department of Chemical Engineering, Abo Akademi, Abo, Finland, 1995.
R.B. Wilson, “A simplicial algorithm for concave programming, Ph.D. Thesis, Harvard University Graduate School of Business Administration, 1963.
Y. Yuan, “Trust region algorithms for nonlinear equations, ” Technical Report 049, Department of Mathematics, Hong Kong University, Hong Kong, 1994.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Leyffer, S. Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming. Computational Optimization and Applications 18, 295–309 (2001). https://doi.org/10.1023/A:1011241421041
Issue Date:
DOI: https://doi.org/10.1023/A:1011241421041