Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 5 of 210
Back to Result List

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

Metadaten
Author:Timo BertholdORCiD, Stefan Heinz, Marc PfetschORCiD, Stefan Vigerske
Document Type:ZIB-Report
Tag:Large Neighborhood Search; MIP; MIQCP; Primal Heuristic; Pseudo-Boolean
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Date of first Publication:2011/05/31
Series (Serial Number):ZIB-Report (11-21)
ZIB-Reportnumber: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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.