Issue: 2021/Vol.31/No.2, Pages 23-57
IMPROVING LOGIC-BASED BENDERS’ ALGORITHMS FOR SOLVING MIN-MAX REGRET PROBLEMS
Lucas Assunção, Andréa Cynthia Santos
, Thiago F. Noronha, Rafael Andrade
Cite as: L. Assunção, A. C. Santos, T. F. Noronha, R. Andrade. Improving logic-based Benders’ algorithms for solving min-max regret problems. Operations Research and Decisions 2021: 31(2), 23-57. DOI 10.37190/ord210202
Abstract
This paper addresses a class of problems under interval data uncertainty, composed of min-max regret generalisations of classical 0-1 optimisation problems with interval costs. These problems are called robust-hard when their classical counterparts are already NP-hard. The state-of-the-art exact algorithms for interval 0-1 min-max regret problems in general work by solving a corresponding mixed-integer linear programming formulation in a Benders’ decomposition fashion. Each of the possibly exponentially many Benders’ cuts is separated on the fly by the resolution of an instance of the classical 0-1 optimisation problem counterpart. Since these separation subproblems may be NP-hard, not all of them can be easily modelled using linear programming (LP), unless P equals NP. In this work, we formally describe these algorithms through a logic-based Benders’ decomposition framework and assess the impact of three warm-start procedures. These procedures work by providing promising initial cuts and primal bounds through the resolution of a linearly relaxed model and an LP-based heuristic. Extensive computational experiments in solving two challenging robust-hard problems indicate that these procedures can highly improve the quality of the bounds obtained by the Benders’ framework within a limited execution time. Moreover, the simplicity and effectiveness of these speed-up procedures make them an easily reproducible option when dealing with interval 0-1 min-max regret problems in general, especially the more challenging subclass of robust-hard problems.
Keywords: robust optimisation, min-max regret problems, Benders’ decomposition, warm-start procedures
Received: 3 December 2020 Accepted: 2 March 2021