A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs

Lucas Assunção (1) , Thiago Ferreira de Noronha (1) , Andréa Cynthia Santos (2) , Rafael Andrade (3)

1 UFMG - Universidade Federal de Minas Gerais = Federal University of Minas Gerais [Belo Horizonte, Brazil]
2 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
3 UFC - Universidade Federal do Ceará = Federal University of Ceará

This work deals with a class of problems under interval data uncertainty, namely interval robust-hard problems, composed of interval data min-max regret generalizations of classical NP-hard combinatorial problems modeled as 0-1 integer linear programming problems. These problems are more challenging than other interval data min-max regret problems, as solely computing the cost of any feasible solution requires solving an instance of an NP-hard problem. The state-of-the-art exact algorithms in the literature are based on the generation of a possibly exponential number of cuts. As each cut separation involves the resolution of an NP-hard classical optimization problem, the size of the instances that can be solved efficiently is relatively small. To smooth this issue, we present a modeling technique for interval robust-hard problems in the context of a heuristic framework. The heuristic obtains feasible solutions by exploring dual information of a linearly relaxed model associated with the classical optimization problem counterpart. Computational experiments for interval data min-max regret versions of the restricted shortest path problem and the set covering problem show that our heuristic is able to find optimal or near-optimal solutions and also improves the primal bounds obtained by a state-of-the-art exact algorithm and a 2-approximation procedure for interval data min-max regret problems.

Mots clés: Benders’ decomposition; Matheuristics; Robust optimization

Domaines: Recherche opérationnelle [math.OC]

Lucas Assunção, Thiago Ferreira de Noronha, Andréa Cynthia Santos, Rafael Andrade. A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs. Computers and Operations Research, 2017, 81, pp.51-66. ⟨10.1016/j.cor.2016.12.010⟩. ⟨hal-02291622⟩