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 -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.
Keywords: Minmax regret, interval uncertainty, binary integer programming, fix-and-optimize, metaheuristics
@article{RO_2022__56_6_4281_0,
author = {Carvalho, Iago A. and Noronha, Thiago F. and Duhamel, Christophe},
title = {Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty},
journal = {RAIRO. Operations Research},
pages = {4281--4301},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {6},
doi = {10.1051/ro/2022198},
mrnumber = {4523953},
zbl = {1553.90035},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022198/}
}
TY - JOUR AU - Carvalho, Iago A. AU - Noronha, Thiago F. AU - Duhamel, Christophe TI - Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty JO - RAIRO. Operations Research PY - 2022 SP - 4281 EP - 4301 VL - 56 IS - 6 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022198/ DO - 10.1051/ro/2022198 LA - en ID - RO_2022__56_6_4281_0 ER -
%0 Journal Article %A Carvalho, Iago A. %A Noronha, Thiago F. %A Duhamel, Christophe %T Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty %J RAIRO. Operations Research %D 2022 %P 4281-4301 %V 56 %N 6 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022198/ %R 10.1051/ro/2022198 %G en %F RO_2022__56_6_4281_0
Carvalho, Iago A.; Noronha, Thiago F.; Duhamel, Christophe. Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty. RAIRO. Operations Research, Tome 56 (2022) no. 6, pp. 4281-4301. doi: 10.1051/ro/2022198
[1] , and , Complexity of the min–max and min–max regret assignment problems. Oper. Res. Lett. 33 (2005) 634–640. | MR | Zbl | DOI
[2] , and , Complexity of the min-max (regret) versions of cut problems, in International Symposium on Algorithms and Computation. Springer (2005) 789–798. | MR | Zbl
[3] , and , Min-max and min-max regret versions of combinatorial optimization problems: A survey. Eur. J. Oper. Res. 197 (2009) 427–438. | MR | Zbl | DOI
[4] , and , A comparative analysis of optimization solvers. J. Stat. Manag. Syst. 20 (2017) 623–635.
[5] , , and , A linear programming based heuristic for robust optimization problems: a case study on solving the restricted robust shortest path problem, in Matheuristics 2014–5th International Workshop on Model-Based Metaheuristics. Hambourg, Alemagne (2014) 8.
[6] , , and , On the finite optimal convergence of logic-based benders’ decomposition in solving 0–1 min-max regret optimization problems with interval costs, in International Symposium on Combinatorial Optimization. Springer (2016) 1–12. | MR | Zbl
[7] , , and , A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs. Comput. Oper. Res. 81 (2017) 51–66. | MR | Zbl | DOI
[8] and , Interval data minmax regret network optimization problems. Discrete Appl. Math. 138 (2004) 289–301. | MR | Zbl | DOI
[9] and , On the complexity of minmax regret linear programming. Eur. J. Oper. Res. 160 (2005) 227–231. | MR | Zbl | DOI
[10] , On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program. 90 (2001) 263–272. | MR | Zbl | DOI
[11] , Complexity of robust single facility location problems on networks with uncertain edge lengths. Discrete Appl. Math. 127 (2003) 505–522. | MR | Zbl | DOI
[12] and , Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study, in Combinatorial Optimization. Springer (1980) 37–60. | MR | Zbl
[13] , Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41 (1990) 1069–1072. | DOI
[14] , Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4 (1962) 238–252. | MR | Zbl | DOI
[15] and , Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88 (2000) 411–424. | MR | Zbl | DOI
[16] and , The price of robustness. Oper. Res. 52 (2004) 35–53. | MR | Zbl | DOI
[17] , , and , Covering vehicle routing problem: application for mobile child friendly spaces for refugees. OR Spectr. (2021) 1–24.
[18] , On the statistical evaluation of algorithmic’s computational experimentation with infeasible solutions. Inf. Process. Lett. 143 (2019) 24–27. | MR | Zbl | DOI
[19] , , and , A scenario based heuristic for the robust shortest path tree problem, in VIII Conference on Manufacturing, Modelling, Management & Control (2016) 443–448.
[20] , , , and , A fix-and-optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty. Int. Trans. Oper. Res. (2021). | MR | Zbl
[21] , and , Set covering problem, in Annotated Bibliographies in Combinatorial Optimization, Edited by and . Wiley (1997) 415–428. | Zbl
[22] , and , Senario-based heuristics with path-relinking for the robust set covering problem. in Proceedings of the XI Metaheuristics International Conference (MIC) (2015) 1–6.
[23] , and , Coupling scenario-based heuristics to exact methods for the robust weighted set covering problem with interval data, in VIII Conference on Manufacturing, Modelling, Management & Control (2016) 455–460.
[24] , and , Formulation and algorithms for the robust maximal covering location problem. Electron. Notes Discrete Math. 64 (2018) 145–154. | MR | Zbl | DOI
[25] , A branch and bound algorithm for the minimax regret spanning arborescence. J. Glob. Optim. 37 (2007) 467–480. | MR | Zbl | DOI
[26] , , and , On integer points in polyhedra. Combinatorica 12 (1992) 27–37. | MR | Zbl | DOI
[27] and , A fix-and-optimize heuristic for the integrated fleet sizing and replenishment planning problem with predetermined delivery frequencies. Comput. Ind. Eng. 127 (2019) 778–787. | DOI
[28] and , A Robust Formulation of the Uncertain Set Covering Problem. Working paper, Bochum (2013).
[29] and , Pinpointing the complexity of the interval min–max regret knapsack problem. Discrete Optim. 7 (2010) 191–196. | MR | Zbl | DOI
[30] , and , A fix-and-optimize heuristic for the high school timetabling problem. Comput. Oper. Res. 52 (2014) 29–38. | MR | Zbl | DOI
[31] and , Min–max and min–max (relative) regret approaches to representatives selection problem. 4OR 10 (2012) 181–192. | MR | Zbl | DOI
[32] , Covers and packings in a family of sets. Bull. Am. Math. Soc. 68 (1962) 494–499. | MR | Zbl | DOI
[33] , and , A note on the selection of benders’ cuts. Math. Program. 124 (2010) 175–182. | MR | Zbl | DOI
[34] , The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J. Am. Stat. Assoc. 32 (1937) 675–701. | JFM | DOI
[35] , , and , Heuristic and exact algorithms for the interval min-max regret knapsack problem. INFORMS J. Comput. 27 (2015) 392–405. | MR | Zbl | DOI
[36] and , An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons. J. Mach. Learn. Res. 9 (2008) 2677–2694. | Zbl
[37] , and , Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice. OR Spectr. 27 (2005) 507–523. | Zbl | DOI
[38] , , and , Gantry crane scheduling in intermodal rail-road container terminals. Int. J. Prod. Res. 56 (2018) 5419–5436. | DOI
[39] , and , The robust shortest path problem with interval data, Tech. Rep., Bilkent University, Department of Industrial Engineering (2001).
[40] , Reducibility among combinatorial problems, in Complexity of computer computations. Springer (1972) 85–103. | MR | Zbl | DOI
[41] and , Complexity of the robust weighted independent set problems on interval graphs. Optim. Lett. 9 (2015) 427–436. | MR | Zbl | DOI
[42] and , An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inf. Process. Lett. 97 (2006) 177–180. | MR | Zbl | DOI
[43] and , Robust discrete optimization under discrete and interval uncertainty: A survey, in Robustness Analysis in Decision Aiding, Optimization, and Analytics. Springer (2016) 113–143. | MR
[44] and , Robust discrete optimization and its applications, In Vol. 14 of Nonconvex Optimization and its Applications. Springer (1997). | MR | Zbl
[45] and , Complexity of minimizing the total flow time with interval data and minmax regret criterion. Discrete Appl. Math. 154 (2006) 2167–2177. | MR | Zbl | DOI
[46] , , and , The robust traveling salesman problem with interval data. Transp. Sci. 41 (2007) 366–381. | DOI
[47] , Distribution-free multiple comparisons. Biometrics 18 (1962) 263. | MR
[48] and , Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions. Eur. J. Oper. Res. 214 (2011) 595–605. | Zbl | DOI
[49] , , and , Sce: A manifold regularized set-covering method for data partitioning. IEEE Trans. Neural Netw. Learn. Syst. 29 (2017) 1760–1773. | MR | DOI
[50] , Computational Complexity, Theoretical computer science. Addison-Wesley (1994). | MR | Zbl
[51] and , The robust set covering problem with interval data. Ann. Oper. Res. 207 (2013) 1–19. | MR | Zbl | DOI
[52] and , An analysis of variance test for normality (complete samples). Biometrika 52 (1965) 591–611. | MR | Zbl | DOI
[53] , The polynomial-time hierarchy. Theor. Comput. Sci. 3 (1976) 1–22. | MR | Zbl | DOI
[54] and , Mixed integer programming based heuristics for the patient admission scheduling problem. Comput. Oper. Res. 80 (2017) 38–49. | MR | Zbl | DOI
[55] , and , Improved algorithms for the minmax-regret 1-center and 1-median problems. ACM Trans. Algorithms (TALG) 4 (2008) 36. | MR | Zbl
Cité par Sources :
