Reoptimization in branch-and-bound algorithms with an application to elevator control
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-17876
- We consider reoptimization (i.e. the solution of a problem based on information available from solving a similar problem) for branch-and-bound algorithms and propose a generic framework to construct a reoptimizing branch-and-bound algorithm. We apply this to an elevator scheduling algorithm solving similar subproblems to generate columns using branch-and-bound. Our results indicate that reoptimization techniques can substantially reduce the running times of the overall algorithm.
Verfasserangaben: | Benjamin HillerORCiD, Torsten Klug, Jakob WitzigORCiD |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | branch-and-bound; column generation; elevator control; reoptimization |
MSC-Klassifikation: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
CCS-Klassifikation: | J. Computer Applications |
Datum der Erstveröffentlichung: | 20.03.2013 |
Schriftenreihe (Bandnummer): | ZIB-Report (13-15) |
ISSN: | 1438-0064 |
Verlagspublikation: | Appeared in: Proceedings of the 12th International Symposium on Experimental Algorithms, 2013, LNCS 7933, pp. 378-389 |
DOI: | https://doi.org/10.1007/978-3-642-38527-8_33 |
Lizenz (Deutsch): | Creative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung |