Large Neighborhood Search beyond MIP

Please always quote using this URN: urn:nbn:de:0297-zib-12989
  • Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.

Download full text files

Export metadata

Author:Timo Berthold, Stefan Heinz, Marc E. Pfetsch, Stefan Vigerske
Document Type:ZIB-Report
Tag:Large Neighborhood Search; MIP; MIQCP; Primal Heuristic; Pseudo-Boolean
Date of first Publication:2011/05/31
Series (Serial Number):ZIB-Report (11-21)
Published in:Appeared in: Proceedings of the 9th Metaheuristics International Conference (MIC 2011). 2011. Luca di Gaspar et al. eds. ISBN 978-88-900984-3-7, pp. 51-60