×

Solving convex MINLP optimization problems using a sequential cutting plane algorithm. (English) Zbl 1111.90087

Summary: In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.

MSC:

90C25 Convex programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.S. Manne, ”GAMS/MINOS: Three examples,” Technical Report, Department of Operations Research, Stanford University, Stanford: California, 1986.,
[2] E.M.L. Beale and J.A. Tomlin, ”Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables,” in: OR69 Proceedings of the Fifth International Conference on Operational Research, J. Lawrence (Ed.), Tavistock Publications, London, 1970, pp. 447–454.,
[3] M. Benichou, J.M. Gauthier, P. Girodet, G. Hentges, G. Ribiere, and O. Vincent, ”Experiments in mixed-integer linear programming,” Mathematical Programming, vol. 1, pp. 76–94, 1971., · Zbl 0233.90016
[4] R.E. Bixby, M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling, ”MIP: Theory and practice–closing the gap,” in: System Modelling and Optimization: Methods, Theory and Applications, M.J.D. Powell, S. Scholtes (Eds.), Kluwer Academic Publishers: Dordrecht, 2000, pp. 19–49., · Zbl 0986.90025
[5] K.-M. Björk, P.O. Lindberg, and T. Westerlund, ”Some convexifications in global optimization of problems containing signomial terms,” Computers and Chemical Engineering, vol. 27, pp. 669–679, 2003.,
[6] B. Borchers and J.E. Mitchell, ”An improved branch and bound algorithm for mixed integer nonlinear programs,” Computers and Operations Research, vol. 21, pp. 359–367, 1994., · Zbl 0797.90069
[7] M.R. Bussieck, A.S. Drud, and A. Meeraus, ”MINLPLib–A collection of test models for mixed-integer nonlinear programming,” GAMS Development Corporation, Washington DC, 2001. Web page at < http://www.gamsworld.org/minlp/minlplib.htm >., · Zbl 1238.90104
[8] J. Czyzyk, M.P. Mesnier, and J.J. Moré, ”The NEOS Server,” IEEE Journal on Computational Science and Engineering, vol. 5, pp. 68–75, 1998.,
[9] H. Dahl, A. Meeraus, and S.A. Zenios, ”Some financial optimization models: I risk management,” in: Financial Optimization, S.A. Zenios (Ed.), Cambridge University Press, Cambridge, 1993, pp. 3–36.,
[10] R.J. Dakin, ”A tree-search algorithm for mixed integer programming problems,” Computer Journal, vol. 8, pp. 250–255, 1965., · Zbl 0154.42004
[11] E.D. Dolan, ”The NEOS Server 4.0 Administrative guide, technical memorandum ANL/MCS-TM-250,” Mathematics and Computer Science Division, Argonne National Laboratory, Argonne: IL, 2001.,
[12] E.D. Dolan and J.J. Moré, ”Benchmarking optimization software with performance profiles,” Mathematical Programming, vol. 91, pp. 201–213, 2002., · Zbl 1049.90004
[13] M.A. 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., · Zbl 0619.90052
[14] R. Fletcher and S. Leyffer, ”User manual for filterSQP,” Numerical Analysis Report NA/181, Department of Mathematics, University of Dundee, Dundee, 1998., · Zbl 0912.90225
[15] R. Fletcher and S. Leyffer, ”Nonlinear programming without a penalty function,” Mathematical Programming, vol. 91, pp. 239–269, 2002., · Zbl 1049.90088
[16] C.A. Floudas, ”Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications, Topics in Chemical Engineering,” Oxford University Press: New York, 1995., · Zbl 0886.90106
[17] C.A. Floudas and P.M. Pardalos, Encyclopedia of Optimization, Kluwer Academic Publishers, Dordrecht, 2001., · Zbl 1027.90001
[18] B. Gavish, D. Horsky, and K. Srikanth, ”An approach to the optimal positioning of a new product,” Management Science, vol. 29, pp. 1277–1297, 1983., · Zbl 0526.90056
[19] P.E. Gill, W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, 1981., · Zbl 0503.90062
[20] O.K. Gupta and A. Ravindran, ”Branch and bound experiments in convex nonlinear integer programming,” Management Science, vol. 31, pp. 1533–1546, 1985., · Zbl 0591.90065
[21] I. Harjunkoski, T. Westerlund, R. Pörn, and H. Skrifvars, ”Different transformations for solving non-convex trim-loss problems by MINLP,” European Journal of Operational Research, vol. 105, pp. 594–603, 1998., · Zbl 0955.90095
[22] I. Harjunkoski, T. Westerlund, and R. Pörn, ”Numerical and environmental considerations on a complex industrial mixed integer non-linear programming (MINLP) problem,” Computers and Chemical Engineering, vol. 23, pp. 1545–1561, 1999.,
[23] G.R. Kocis and I.E. Grossmann, ”Global optimization of nonconvex mixed-integer nonlinear programming (MINLP) problems in process synthesis,” Industrial and Engineering Chemical Research, vol. 27, pp. 1407–1421, 1988.,
[24] A.H. Land and A.G. Doig, ”An automatic method of solving discrete programming problems,” Econometrica, vol. 28, pp. 497–520, 1960., · Zbl 0101.37004
[25] S. Leyffer, ”MacMINLP : AMPL collection of mixed integer nonlinear programs,” University of Dundee, Dundee, 2000. Available from < http://www.maths.dundee.ac.uk/leyffer/MacMINLP/ > .,
[26] S. Leyffer, ”Integrating SQP and branch-and-bound for mixed integer nonlinear programming,” Computational Optimization and Applications, vol. 18, pp. 295–309, 2001., · Zbl 1009.90074
[27] J.C.T. Mao and B.A. Wallingford, ”An extension of Lawler and Bell’s method of discrete optimization with examples from capital budgeting,” Management Science, vol. 15, pp. 51–60, 1968.,
[28] 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.,
[29] 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.,
[30] N.V. Sahinidis and I.E. Grossmann, ”Convergence properties of generalized Benders decomposition,” Computers and Chemical Engineering, vol. 15, pp. 481–491, 1991.,
[31] N.V. Sahinidis, ”BARON: A general purpose global optimization software package,” Journal of Global Optimization, vol. 8, pp. 201–205, 1996., · Zbl 0856.90104
[32] M.W.P. Savelsbergh, ”Preprocessing and probing techniques for mixed integer programming problems,” ORSA Journal on Computing, vol. 6, pp. 445–454, 1994., · Zbl 0814.90093
[33] C. Still and T. Westerlund, ”Extended cutting plane algorithm,” in: Encyclopedia of Optimization, C.A. Floudas, P.M. Pardalos (Eds.), Kluwer Academic Publishers, Dordrecht, 2001, Vol. 2, pp. 53–61.,
[34] C. Still and T. Westerlund, ”A sequential cutting plane algorithm for solving convex NLP problems,” European Journal of Operational Research, 2005, (Accepted)., · Zbl 1125.90038
[35] T. Westerlund and F. Pettersson, ”An extended cutting plane method for solving convex MINLP problems,” Computers and Chemical Engineering, vol. 19(Suppl.), pp. S131–S136, 1995.,
[36] T. Westerlund, H. Skrifvars, I. Harjunkoski, and R. Pörn, ”An extended cutting plane method for a class of non-convex MINLP problems,” Computers and Chemical Engineering, vol. 22, pp. 357–365, 1998., · Zbl 0955.90095
[37] T. Westerlund and K. Lundqvist, ”Alpha-ECP Version 5.01. An interactive MINLP-Solver based on the extended cutting plane method,” Report 01-178-A, Process Design Laboratory, bo Akademi University, bo, 2001.,
[38] T. Westerlund and R. Pörn, ”Solving pseudo-convex mixed integer optimization problems by cutting plane techniques,” Optimization and Engineering, vol. 3, pp. 253–280, 2002., · Zbl 1035.90051
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.