Reoptimization in branch-and-bound algorithms with an application to elevator control
Please always quote using this 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.
Author: | Benjamin HillerORCiD, Torsten Klug, Jakob WitzigORCiD |
---|---|
Document Type: | ZIB-Report |
Tag: | branch-and-bound; column generation; elevator control; reoptimization |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
CCS-Classification: | J. Computer Applications |
Date of first Publication: | 2013/03/20 |
Series (Serial Number): | ZIB-Report (13-15) |
ISSN: | 1438-0064 |
Published in: | 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 |
Licence (German): | Creative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung |