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

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02291622
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, September 19, 2019 - 9:38:31 AM
Last modification on : Friday, September 20, 2019 - 1:25:19 AM

Links full text

Identifiers

Collections

Citation

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

Share

Metrics

Record views

8