SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework

Abstract

This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.

Keywords:

• mixed-integer nonlinear programming
• global optimization
• nonconvex constraints
• mixed-integer quadratically constrained programming
• MINLP
• MIQCP

Acknowledgments

We want to thank Tobias Achterberg for his initial creation of SCIP and all SCIP developers for their continuous dedication to this project. We would also like to thank the two anonymous referees for their valuable remarks that helped to improve the clarity of the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1 http://www.coin-or.org/CppAD

2 The case can occur by taking implications of the form into account, . SCIP stores these implications in a central data structure [2, Section 3.3].

3 For bilinear terms that involve binary variables, only the binary variable is considered for branching, since it linearizes this term in both child nodes. If a bilinear term involves unbounded variables, only the unbounded variables are considered for branching.

4 http://www.gamsworld.org/minlp/minlplib2/html/index.html

Additional information

Funding

This work has been supported by the DFG Research Center Matheon Mathematics for key technologies in Berlin, the Berlin Mathematical School, and the Research Campus Modal Mathematical Optimization and Data Analysis Laboratories funded by the Federal Ministry of Education and Research (BMBF Grant 05M14ZAM). All responsibility for the content of this publication is assumed by the authors.