1463
eng
reportzib
0
2012-02-06
2012-02-06
--
Undercover: a primal MINLP heuristic exploring a largest sub-MIP
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.
1438-0064
12-07
urn:nbn:de:0297-zib-14631
10.1007/s10107-013-0635-2
Mathematical Programming
urn:nbn:de:0297-zib-14631
Timo Berthold
Timo Berthold
Ambros M. Gleixner
ZIB-Report
12-07
eng
uncontrolled
Primal Heuristic
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Large Neighborhood Search
eng
uncontrolled
Mixed-Integer Quadratically Constrained Programming
eng
uncontrolled
Nonconvex Optimization
Mixed integer programming
Quadratic programming
Nonconvex programming, global optimization
Nonlinear programming
Approximation methods and heuristics
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1463/ZR-12-07.pdf
https://opus4.kobv.de/opus4-zib/files/1463/ZR-12-07_rev.pdf
4217
eng
reportzib
0
2013-08-23
2013-08-23
--
Primal MINLP Heuristics in a nutshell
Primal heuristics are an important component of state-of-the-art codes for mixed integer nonlinear programming (MINLP). In this article we give a compact overview of primal heuristics for MINLP that have been suggested in the literature of recent years. We sketch the fundamental concepts of different classes of heuristics and discuss specific implementations. A brief computational experiment shows that primal heuristics play a key role in achieving feasibility and finding good primal bounds within a global MINLP solver.
1438-0064
urn:nbn:de:0297-zib-42170
Timo Berthold
Timo Berthold
ZIB-Report
13-42
eng
uncontrolled
Primal Heuristic
eng
uncontrolled
MINLP
eng
uncontrolled
Mixed Integer Nonlinear Programming
eng
uncontrolled
Feasibility Pump
eng
uncontrolled
Large Neighborhood Search
Mixed integer programming
Nonconvex programming, global optimization
Approximation methods and heuristics
Mathematical Optimization
Berthold, Timo
https://opus4.kobv.de/opus4-zib/files/4217/Berthold_MINLP_heuristics.pdf