TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover: a primal MINLP heuristic exploring a largest sub-MIP N2 - 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. T3 - ZIB-Report - 12-07 KW - Primal Heuristic KW - Mixed-Integer Nonlinear Programming KW - Large Neighborhood Search KW - Mixed-Integer Quadratically Constrained Programming KW - Nonconvex Optimization Y1 - 2012 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1463 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-14631 SN - 1438-0064 ER -