A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs - Archive ouverte HAL Access content directly
Journal Articles Computers and Operations Research Year : 2017

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

(1) , (1) , (2) , (3)
1
2
3

Abstract

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.

Dates and versions

hal-02291622 , version 1 (19-09-2019)

Identifiers

Cite

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⟩

Collections

CNRS UTT LOSI
17 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More