1163
eng
reportzib
0
2009-12-16
2009-12-16
--
Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering
We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib.
09-40
1438-0064
1222
urn:nbn:de:0297-zib-11632
App. in: Proceedings of the EWMINLP. Pierre Bonami et al. eds. 2010, pp. 103-112
Timo Berthold
unknown unknown
Ambros Gleixner
ZIB-Report
09-40
deu
uncontrolled
MINLP
deu
uncontrolled
MIQCP
deu
uncontrolled
Primalheuristik
deu
uncontrolled
Nachbarschaftssuche
deu
uncontrolled
Mengenüberdeckung
eng
uncontrolled
mixed-integer nonlinear programming
eng
uncontrolled
MIQCP
eng
uncontrolled
primal heuristic
eng
uncontrolled
large neighborhood search
eng
uncontrolled
set covering
Mathematik
Optimization
Mixed integer programming
Nonlinear programming
Approximation methods and heuristics
Mathematical Optimization
Berthold, Timo
Gleixner, Ambros
MATHEON-B20
MIP-ZIBOPT
Siemens
https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40_rev2.pdf
https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40.pdf
https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40_rev2.ps
https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40.ps
https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40_rev3.pdf
https://opus4.kobv.de/opus4-zib/files/1163/ZR_09_40_rev3.ps