90C26 Nonconvex programming, global optimization
Refine
Year of publication
Document Type
- ZIB-Report (22)
- Doctoral Thesis (2)
Is part of the Bibliography
- no (24)
Keywords
- Pooling Problem (4)
- nonconvex (3)
- Cutting Planes (2)
- Large Neighborhood Search (2)
- MINLP (2)
- Nonconvexity (2)
- Primal Heuristic (2)
- Quadratic Programming (2)
- Relaxation (2)
- Relaxations (2)
- Standard Quadratic Programming (2)
- global optimization (2)
- mixed-integer quadratically constrained programming (2)
- Computations (1)
- Decomposition (1)
- Extreme Points (1)
- Feasibility Pump (1)
- Gas Network Planning (1)
- Intersection cuts (1)
- LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl (1)
- MINLP, global optimization, operative planning, water supply networks (1)
- MIP (1)
- MIQCP (1)
- Mixed Integer Nonlinear Programming (1)
- Mixed-Integer Quadratically Constrained Programming (1)
- Mixed-Integer Nonlinear Programming (1)
- Nonconvex Optimization (1)
- OBBT (1)
- QCQPs (1)
- Quadratic-free sets (1)
- Robust Optimization (1)
- SCIP, MIP, MINLP, CIP, LP, modeling, optimization (1)
- Uncertainty (1)
- Valid Inequalities (1)
- bivariate functions (1)
- branch-and-cut (1)
- branching rule (1)
- computational (1)
- constraint integer programming (1)
- convex envelope (1)
- convex relaxation (1)
- large neighborhood search (1)
- linear underestimator (1)
- mixed integer nonlinear programming (1)
- mixed integer programming (1)
- mixed integer quadratically constrained programming (1)
- mixed-integer programming (1)
- optimality-based bound tightening (1)
- optimization-based bound tightening (1)
- perspective cuts, mixed-integer nonlinear programming, nonconvex optimization, computational study (1)
- primal heuristic (1)
- propagation (1)
- solver software (1)
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.