Improving logic-based Benders' algorithms for solving min-max regret problems

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

Operations Research and Decisions, 2021, vol. 31, issue 2, 23-57

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 (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://ord.pwr.edu.pl/assets/papers_archive/1583%20-%20published.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wut:journl:v:31:y:2021:i:2:p:21-39:id:1566

DOI: 10.37190/ord210202

Access Statistics for this article

More articles in Operations Research and Decisions from Wroclaw University of Science and Technology, Faculty of Management Contact information at EDIRC.
Bibliographic data for series maintained by Adam Kasperski ().