Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 2
Zurück zur Trefferliste

Large Neighborhood Search beyond MIP

Zitieren Sie bitte immer diese 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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Timo BertholdORCiD, Stefan Heinz, Marc PfetschORCiD, Stefan Vigerske
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Large Neighborhood Search; MIP; MIQCP; Primal Heuristic; Pseudo-Boolean
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Datum der Erstveröffentlichung:31.05.2011
Schriftenreihe (Bandnummer):ZIB-Report (11-21)
ZIB-Reportnummer:11-21
Verlagspublikation: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.