zbMATH — the first resource for mathematics

Mixed integer programming versus logic-based Benders decomposition for planning and scheduling. (English) Zbl 1382.90061
Gomes, Carla (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 10th international conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38170-6/pbk). Lecture Notes in Computer Science 7874, 325-331 (2013).
Summary: A recent paper by S. Heinz and J. C. Beck [ibid. 7298, 211–227 (2012; Zbl 1382.90064)] found that mixed integer software has become competitive with or superior to logic-based Benders decomposition for the solution of facility assignment and scheduling problems. Their implementation of Benders differs, however, from that described in the literature they cite and therefore results in much slower performance than previously reported. We find that when correctly implemented, the Benders method remains 2 to 3 orders of magnitude faster than the latest commercial mixed integer software on larger instances, thus reversing the conclusion of the earlier paper.
For the entire collection see [Zbl 1263.68017].

90C11 Mixed integer programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
Full Text: DOI