An algorithmic framework for convex mixed integer nonlinear programs

By Pierre Bonami, Lorenz T. Biegler, Andrew R. Conn, Gérard Cornuéjols, Ignacio E. Grossmann, Carl D. Laird, Jon Lee, Andrea Lodi, François Margot, Nicolas W. Sawaya and 1 more. Discrete Optimization, 2008

350 citations recorded by the source corpus.

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.

Subfields: Control and Systems Engineering, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/c67221c85dfdd2aa13ec41656aff849c5809dbd3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Control and Systems Engineering

Juan Pablo Vielma

In Numerical Analysis

Citations in the corpus

Non-convex mixed-integer nonlinear programming: A survey (2012, neutral): “Examples include generalized Benders’ decomposition [1], branch-and-bound [2], outer approximation [3], LP/NLP-based branch-and-bound [4], the extended cutting-plane method [5], branch-and-cut [6], and the hybrid methods described in [7,8].”
Mixed-integer nonlinear optimization*† (2013, neutral): “Here, we review three such methods: outer approximation (Duran and Grossmann, 1986; Fletcher and Leyffer, 1994; Bonami et al., 2008), generalized Benders decomposition (Geoffrion, 1972; Van Roy, 1983), and the extended cutting-plane method (Westerlund and Pettersson, 1995).”
Algorithms and Software for Convex Mixed Integer Nonlinear Programs (2012, neutral): “The set J is the index set of nonlinear constraints, I is the index set of discrete variables and C is the index set of continuous variables, so I ∪ C = { 1 , . . . , n } .”
Polyhedral approximation in mixed-integer convex optimization (2016, positive): “Indeed, in 2014 benchmarks by Hans Mittelman, the OA algorithm implemented within Bonmin using CPLEX as the MILP solver was found to be the fastest among MICP solvers [37].”
When is rounding allowed in integer nonlinear optimization? (2014, neutral): “More recently, outer approximation procedures have been suggested (Bonami et al., 2008). Research has also been done for special cases such as integer minimization of polynomial functions over polyhedral sets where an FPTAS is possible (De Loera, Hemmecke, Köppe, & Weismantel, 2006), of separable co”
Variable Neighborhood Search (2018, neutral): “Some good solvers targeting convex MINLPs exist in the literature [1, 24, 26, 45, 46, 78]; and although they can all be used on nonconvex MINLPs as well (forsaking the optimality guarantee), their quality varies wildly in practice with the instance of the problem being solved, resulting in a high fr”