Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2007/1053/

Berthold, Timo

RENS - Relaxation Enforced Neighborhood Search

pdf-Format:
Dokument 1.pdf (181 KB)
ps-Format:
Dokument 1.ps (636 KB)

Kurzfassung in Englisch

In the recent years, a couple of quite successful large neighborhood search heuristics for mixed integer programs has been published.
Up to our knowledge, all of them are improvement heuristics.
We present a new start heuristic for general MIPs working in the spirit of large neighborhood search.
It constructs a sub-MIP which represents the space of all feasible roundings of some fractional point - normally the optimum of the LP-relaxation of the original MIP.
Thereby, one is able to determine whether a point can be rounded to a feasible solution and which is the best possible rounding.
Furthermore, a slightly modified version of RENS proves to be a well-performing heuristic inside the branch-cut-and-price-framework SCIP.

Freie Schlagwörter (deutsch): Primalheuristiken, Gemischt-Ganzzahlige Programmierung, Nachbarschaftssuche
Freie Schlagwörter (englisch): mixed integer programming, primal heuristics, large neighborhood search
MSC - Klassifikation 90C11
MSC - Klassifikation 90C59
Abteilung: Optimierung
DDC-Sachgruppe: Mathematik
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 07-28
ISBN: 1438-0064
Sprache: Englisch
Erstellungsjahr: 2007
Publikationsdatum: 24.10.2007
Bemerkung: printed version not available / keine gedruckte Version

Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: