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. 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.
Kasperski and Zieli ' n ski @cite_31 also developed a Fully Polynomial Time Approximation Scheme (FPTAS) for interval min-max regret problems. However, this FPTAS relies on two very restrictive conditions: (i) the problem tackled must present a pseudopolynomial algorithm, and (ii) the corresponding classical counterpart has to be polynomially solvable. Condition (ii) comes from the fact that the aforementioned FPTAS uses AMU within its framework. Notice that, from (ii), this FPTAS does not naturally hold for interval robust-hard problems.
@cite_31
1988146710
The general problem of minimizing the maximal regret in combinatorial optimization problems with interval costs is considered. Some results are proven that allow to obtain a fully polynomial time approximation scheme (FPTAS) for the problem under the assumption that a pseudopolynomial algorithm is given.