Journal
MATHEMATICAL PROGRAMMING
Volume 144, Issue 1-2, Pages 315-346Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-013-0635-2
Keywords
Primal heuristic; Mixed-integer nonlinear programming; Large neighborhood search; Mixed-integer quadratically constrained programming; Nonconvex optimization
Categories
Funding
- DFG Research Center MATHEON Mathematics for key technologies in Berlin
Ask authors/readers for more resources
We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programs (MINLPs) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a smallest set of variables to fix, a so-called cover, such that each constraint is linearized. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We apply domain propagation to try to avoid infeasibilities, and conflict analysis to learn additional constraints from infeasibilities that are nonetheless encountered. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and MINLPs. It turns out that the majority of these instances allows for small covers. Although general in nature, we show that the heuristic is most successful on MIQCPs. It nicely complements existing root-node heuristics in different state-of-the-art solvers and helps to significantly improve the overall performance of the MINLP solver SCIP.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available