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.
Regarding heuristics for interval robust-hard problems, a simple and efficient scenario-based procedure to tackle interval min-max regret problems in general was proposed in @cite_46 and successfully applied in several works (see, e.g., @cite_23 @cite_46 @cite_12 ). The procedure, called Algorithm Mean Upper (AMU), consists in solving the corresponding classical optimization problem in two specific scenarios: the so called , where the cost referred to each binary variable is set to its upper bound, and the , where the cost of the binary variables are set to the mean values referred to the bounds of the respective cost intervals. With this heuristic, one can obtain a feasible solution for any interval min-max regret optimization problem (including interval robust-hard problems) with the same worst-case asymptotic complexity of solving an instance of the classical optimization problem counterpart. Moreover, it is proven in @cite_12 that this algorithm is 2-approximative for any interval min-max regret optimization problem. Notice that AMU does not run in polynomial time for interval robust-hard problems, unless P = NP.
@cite_46 @cite_12 @cite_23
2075772595 2051407192 2180809430
The use of "optimality" as an operational research criterion is insufficiently discriminating. Ample evidence exists that for many problems simple optimization (particularly profit maximization) does not represent the aims of management. In this paper we discuss the nature of the problem situations for which alternative decision criteria are more appropriate. In particular the structure of strategic planning problems is analysed. The provisional commitment involved in a plan (in contrast to the irrevocable commitment of a decision) leads to the development of a particular criterion, robustness—a measure of the flexibility which an initial decision of a plan maintains for achieving near-optimal states in conditions of uncertainty. The robustness concept is developed through the case study of a sequential factory location problem. The general problem of minimizing the maximal regret in combinatorial optimization problems with interval data is considered. In many cases, the minmax regret versions of the classical, polynomially solvable, combinatorial optimization problems become NP-hard and no approximation algorithms for them have been known. Our main result is a polynomial time approximation algorithm with a performance ratio of 2 for this class of problems. We study a version of the traveling salesman problem where travel times are specified as a range of possible values. This model reflects the difficulties to estimate travel times exactly in reality. Robustness concepts are used to drive optimization. We propose some efficient heuristic and preprocessing techniques. Computational experiments are presented.