Undercover: a primal MINLP heuristic exploring a largest sub-MIP

Please always quote using this URN: urn:nbn:de:0297-zib-14631
  • 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.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Timo Berthold, Ambros M. Gleixner
Document Type:ZIB-Report
Tag: Primal Heuristic; Large Neighborhood Search; Mixed-Integer Quadratically Constrained Programming; Mixed-Integer Nonlinear Programming; Nonconvex Optimization
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C20 Quadratic programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C26 Nonconvex programming, global optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C30 Nonlinear programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C59 Approximation methods and heuristics
Date of first Publication:2012/02/06
Series (Serial Number):ZIB-Report (12-07)
ISSN:1438-0064
Published in:Mathematical Programming
Preprint:urn:nbn:de:0297-zib-14631
DOI:http://dx.doi.org/10.1007/s10107-013-0635-2

$Rev: 13581 $