The Minmax regret 0-1 integer linear programming problem under interval uncertainty: complexity and heuristics

Abstract

Minmax regret is a framework to tackle uncertainty in the decision-making process. In this thesis, we investigate minmax regret optimization problems where the coefficient of the variables on the objective function is unknown, but it is assumed to be bounded by an interval. The Minmax regret 0-1 Integer Linear Programming Problem under Interval Uncertainty (M-ILP) is investigated. We prove that this problem is complete for the second level of the polynomial hierarchy, being \Sigma^p_2-Complete. Furthermore, we introduce the Fix-and-Optimize (FAO) heuristics, which can be generalized for any minmax regret optimization problem under interval uncertainty. We assess the quality of the proposed heuristics by performing computational experiments on two instances of M-ILP: the Minmax regret Weighted Set Covering Problem under Interval Uncertainty and the Minmax regret Single-Source Shortest Path Problem under Interval Uncertainty. For the former, we show that it is contained in the class \Sigma^p_2. Furthermore, we extend exact algorithms based on the Bender's Decomposition for this problem, propose two variants of the FAO heuristics, and compare the obtained results with those of the literature for this problem. For the latter, we show that the problem is NP-Hard even on a layered digraph with 3 layers, obtain optimal solutions by solving a compact multi-commodities formulation using a branch-and-bound algorithm, and implement the same FAO heuristic variants. The results obtained by the FAO heuristics are also compared with those of the state-of-the-art heuristics for this problem. Computational experiments performed on classical instances from the literature demonstrated that one of the proposed Fix-and-Optimize heuristics significantly outperformed the literature heuristics for solving both of the studied problems.