An algorithmic framework for convex mixed integer nonlinear programs. (English) Zbl 1151.90028

Bonami, Pierre; Biegler, Lorenz T.; Conn, Andrew R.; Cornuéjols, Gérard; Grossmann, Ignacio E.; Laird, Carl D.; Lee, Jon; Lodi, Andrea; Margot, François; Sawaya, Nicolas; Wächter, Andreas

Discrete Optim. 5, No. 2, 186-204 (2008).

Summary: This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.

MSC:

90C11	Mixed integer programming
90C25	Convex programming

Keywords:

branch-and-bound; outer-approximation; open-source; MINLP test problems

Software:

Ipopt; COIN-OR; DICOPT; SBB; Bonmin; filterSQP; MIPLIB

References:

[1]	Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Operations Research Letters, 3, 42-54 (2005) · Zbl 1076.90037
[2]	Balas, E.; Ceria, S.; Cornuejols, G., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Mathematical Programming, 58, 295-324 (1993) · Zbl 0796.90041
[3]	Benichou, M.; Gauthier, J. M.; Girodet, P.; Hentges, G.; Ribiere, G.; Vincent, O., Experiments in mixed-integer programming, Mathematical Programming, 1, 76-94 (1971) · Zbl 0233.90016
[6]	Castillo, I.; Westerlund, J.; Emet, S.; Westerlund, T., Optimization of block layout design problems with unequal areas: A comparison of MILP and MINLP optimization methods, Computers & Chemical Engineering, 30, 54-69 (2005)
[9]	Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 201-213 (2002) · Zbl 1049.90004
[10]	Duran, M.; Grossmann, I. E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Mathematical Programming, 36, 307-339 (1986) · Zbl 0619.90052
[11]	Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Mathematical Programming, 66, 327-349 (1994) · Zbl 0833.90088
[13]	Geoffrion, A. M., Generalized Benders decomposition, Journal of Optimization Theory and Applications, 10, 237-260 (1972) · Zbl 0229.90024
[14]	Grossmann, I. E., Review of nonlinear mixed-integer and disjunctive programming techniques, Optimization and Engineering, 3, 227-252 (2002) · Zbl 1035.90050
[15]	Grossmann, I. E.; Lee, S., Generalized disjunctive programming: Nonlinear convex hull relaxation and algorithms, Computational Optimization and Applications, 26, 83-100 (2003) · Zbl 1030.90069
[16]	Gupta, O. K.; Ravindran, V., Branch and bound experiments in convex nonlinear integer programming, Management Science, 31, 1533-1546 (1985) · Zbl 0591.90065
[17]	Harjunkoski, I.; Westerlund, T.; Pörn, R.; Skrifvars, H., Different transformations for solving non-convex trim loss problems by MINLP, European Journal of Operational Research, 105, 594-603 (1998) · Zbl 0955.90095
[18]	(Jünger, M.; Naddef, D., Computational Combinatorial Optimization. Computational Combinatorial Optimization, Lecture Notes in Computer Science, vol. 2241 (2001), Springer) · Zbl 0977.00014
[19]	Laird, C. D.; Biegler, L. T.; Bloemen Waanders, B. V., A mixed integer approach for obtaining unique solutions in source inversion of drinking water networks, ASCE Journal of Water Resource Management and Planning, 132, 4, 242-251 (2006)
[20]	Leyffer, S., Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Computational Optimization & Applications, 18, 295-309 (2001) · Zbl 1009.90074
[21]	Linderoth, J. T.; Savelsbergh, M. W.P., A computational study of search strategies for mixed integer programming, INFORMS Journal of Computing, 11, 173-187 (1999) · Zbl 1040.90535
[24]	Padberg, M. W.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large scale symmetric travelling salesman problems, SIAM Review, 33, 60-100 (1991) · Zbl 0734.90060
[25]	Quesada, I.; Grossmann, I. E., An LP/NLP based branched and bound algorithm for convex MINLP optimization problems, Computers and Chemical Engineering, 16, 937-947 (1992)
[26]	Raman, R.; Grossmann, I. E., Modeling and computational techniques for logic based integer programming, Computers and Chemical Engineering, 18, 563-578 (1994)
[30]	Stubbs, R.; Mehrotra, S., A branch-and-cut method for 0-1 mixed convex programming, Mathematical Programming, 86, 515-532 (1999) · Zbl 0946.90054
[31]	Tawarmalani, M.; Sahinidis, N. V., Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Mathematical Programming, 99, 563-591 (2004) · Zbl 1062.90041
[32]	Turkay, M.; Grossmann, I. E., Logic-based MINLP algorithms for the optimal synthesis of process networks, Computers & Chemical Engineering, 20, 959-978 (1996)
[33]	Vechietti, A.; Grossmann, I. E., LOGMIP: A disjunctive 0-1 non-linear optimizer for process systems models, Computers & Chemical Engineering, 23, 555-565 (1999)
[34]	Viswanathan, J.; Grossmann, I. E., A combined penalty function and outer-approximation method for MINLP optimization, Computers & Chemical Engineering, 14, 769 (1990)
[35]	Wächter, A.; Biegler, L. T., On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Mathematical Programming (2005)
[36]	Westerlund, T.; Pettersson, F., An extended cutting plane method for solving convex MINLP problems, Computers & Chemical Engineering, 19, 131-136 (1995)
[37]	Wolsey, L. A., Integer Programming (1998), Wiley · Zbl 0930.90072