An algorithmic framework for convex mixed integer nonlinear programs.

*(English)*Zbl 1151.90028Summary: 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.

PDF
BibTeX
XML
Cite

\textit{P. Bonami} et al., Discrete Optim. 5, No. 2, 186--204 (2008; Zbl 1151.90028)

Full Text:
DOI

##### 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 |

[4] | R.E. Bixby, S. Ceria, C.M. McZeal, M.W.P. Savelsbergh, MIPLIB 3.0. http://www.caam.rice.edu/ bixby/miplib/miplib.html |

[5] | (Basic Open-source Mixed INteger programming). http://projects.coin-or.org/Bonmin |

[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) |

[7] | COIN-OR. www.coin-or.org |

[8] | . http://www.gams.com/solvers/dicopt/main.htm |

[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 |

[12] | R. Fletcher, S. Leyffer, User manual for FilterSQP. Numerical Analysis Report NA/181, Dundee University, 1998 |

[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] | () |

[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 |

[22] | CMU/IBM MINLP Project. http://egon.cheme.cmu.edu/ibm/page.htm |

[23] | J. Nocedal, A. Wächter, R.A. Waltz, Adaptive barrier strategies for nonlinear interior methods, Research Report RC 23563, IBM T.J. Watson Research Center, Yorktown, USA, 2005 |

[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) |

[27] | D.E. Ravemark, Optimization models for design and operation of chemical batch processes, Ph.D. Thesis, Swiss Federal Institute of Technology, 1995 |

[28] | N.W. Sawaya, Reformulations, relaxations and cutting planes for generalized disjunctive programming, Ph.D. Thesis, Chemical Engineering Department, Carnegie Mellon University, 2006 |

[29] | . http://www.conopt.com/sbb/SBB_announcement.htm |

[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 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.