- Tytuł:
- Improving logic-based Benders’ algorithms for solving min-max regret problems
- Autorzy:
-
Assunção, Lucas
Santos, Andréa Cynthia
Noronha, Thiago F.
Andrade, Rafael - Powiązania:
- https://bibliotekanauki.pl/articles/2099670.pdf
- Data publikacji:
- 2021
- Wydawca:
- Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
- Tematy:
-
robust optimisation
min-max regret problem
Benders’ decomposition
warm-start procedure - Opis:
- 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.
- Źródło:
-
Operations Research and Decisions; 2021, 31, 2; 23--57
2081-8858
2391-6060 - Pojawia się w:
- Operations Research and Decisions
- Dostawca treści:
- Biblioteka Nauki
Artykuł