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)
We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem.
We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.