90C26 Nonconvex programming, global optimization
Refine
Document Type
- ZIB-Report (2)
Language
- English (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- bivariate functions (1)
- convex envelope (1)
- global optimization (1)
- linear underestimator (1)
Institute
- Mathematical Optimization Methods (2) (remove)
This is a technical report for the SCIP constraint handler cons_bivariate. We describe a cut-generation algorithm for a class of bivariate twice continuously differentiable functions with
fixed convexity behavior over a box.
Computational results comparing our cut-generation algorithms with
state-of-the-art global
optimization software on a series of randomly generated test instances are reported and discussed.
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.