Structure-based primal heuristics for mixed integer programming

Please always quote using this URN: urn:nbn:de:0297-zib-55518
  • Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Gerald Gamrath, Timo Berthold, Stefan Heinz, Michael Winkler
Document Type:ZIB-Report
Tag:mixed-integer programming, large neighborhood search, primal heuristics, domain propagation
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
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] / 90C59 Approximation methods and heuristics
Date of first Publication:2015/07/03
Series (Serial Number):ZIB-Report (15-26)
ISSN:1438-0064
Preprint:urn:nbn:de:0297-zib-55518
DOI:http://dx.doi.org/http://dx.doi.org/10.1007/978-4-431-55420-2_3

$Rev: 13581 $