Issue |
RAIRO-Oper. Res.
Volume 56, Number 6, November-December 2022
|
|
---|---|---|
Page(s) | 4281 - 4301 | |
DOI | https://doi.org/10.1051/ro/2022198 | |
Published online | 21 December 2022 |
Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty
1
Computer Science Department, Universidade Federal de Alfenas, Av. Jovino Fernandes de Sales 2600, Alfenas, MG 37133-840, Brazil
2
Computer Science Department, Universidade Federal de Minas Gerais, Av. Pres. Antônio Carlos 6627, Belo Horizonte, MG 31270-901, Brazil
3
Laboratoire d’Informatique, du Traitement de l’Information et des Systèmes, Universitè Le Havre Normandie, 25 Rue Philippe, Lebon, 76600 Le Havre, France
* Corresponding author: tfn@dcc.ufmg.br
Received:
7
April
2022
Accepted:
6
November
2022
The Binary Integer Programming problem (BIP) is a mathematical optimization problem, with linear objective function and constraints, on which the domain of all variables is {0, 1}. In BIP, every variable is associated with a determined cost coefficient. The Minmax regret Binary Integer Programming problem under interval uncertainty (M-BIP) is a generalization of BIP in which the cost coefficient associated to the variables is not known in advance, but are assumed to be bounded by an interval. The objective of M-BIP is to find a solution that possesses the minimum maximum regret among all possible solutions for the problem. In this paper, we show that the decision version of M-BIP is Σp2-complete. Furthermore, we tackle M-BIP by both exact and heuristic algorithms. We extend three exact algorithms from the literature to M-BIP and propose two fix-and-optimize heuristic algorithms. Computational experiments, performed on the Minmax regret Weighted Set Covering problem under Interval Uncertainties (M-WSCP) as a test case, indicates that one of the exact algorithms outperforms the others. Furthermore, it shows that the proposed fix-and-optimize heuristics, that can be easily employed to solve any minmax regret optimization problem under interval uncertainty, are competitive with ad-hoc algorithms for the M-WSCP.
Mathematics Subject Classification: 68R01 / 90C11 / 90C17 / 90C47 / 90C59
Key words: Minmax regret / interval uncertainty / binary integer programming / fix-and-optimize / metaheuristics
© The authors. Published by EDP Sciences, ROADEF, SMAI 2022
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.