Issue: 2021/Vol.31/No.2, Pages 23-57


Lucas Assunção, Andréa Cynthia Santos, Thiago F. Noronha, Rafael Andrade

Full paper (PDF)    

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

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