A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs. (May 2017)

• Record Type: Journal Article
• Authors: Assunção, Lucas; Noronha, Thiago F.; Santos, Andréa Cynthia; Andrade, Rafael
• Is Part Of: Computers & operations research. Volume 81(2017)
• Page Start: 51
• Page End: 66
• Publication Date: 2017-05
• Subjects: Robust optimization -- Matheuristics -- Benders' decomposition; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.12.010
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A heuristic framework for a class of robust optimization problems is proposed. The heuristic framework explores dual information. The heuristic is successfully applied to solve two robust optimization problems. The heuristic is able to outperform a widely used 2-approximation procedure. A robust optimization version of the restricted shortest path problem is introduced. 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.