We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Exploiting the Structure of Two-Stage Robust Optimization Models with Exponential Scenarios.
- Authors
Hashemi Doulabi, Hossein; Jaillet, Patrick; Pesant, Gilles; Rousseau, Louis-Martin
- Abstract
This paper addresses a class of two-stage robust optimization models with an exponential number of scenarios given implicitly. We apply Dantzig–Wolfe decomposition to exploit the structure of these models and show that the original problem reduces to a single-stage robust problem. We propose a Benders algorithm for the reformulated single-stage problem. We also develop a heuristic algorithm that dualizes the linear programming relaxation of the inner maximization problem in the reformulated model and iteratively generates cuts to shape the convex hull of the uncertainty set. We combine this heuristic with the Benders algorithm to create a more effective hybrid Benders algorithm. Because the master problem and subproblem in the Benders algorithm are mixed-integer programs, it is computationally demanding to solve them optimally at each iteration of the algorithm. Therefore, we develop novel stopping conditions for these mixed-integer programs and provide the relevant convergence proofs. Extensive computational experiments on a nurse planning problem and a two-echelon supply chain problem are performed to evaluate the efficiency of the proposed algorithms.
- Subjects
ROBUST optimization; LINEAR programming; HEURISTIC algorithms; EXPECTATION-maximization algorithms; INTEGER programming; SUPPLY chains
- Publication
INFORMS Journal on Computing, 2021, Vol 33, Issue 1, p143
- ISSN
1091-9856
- Publication type
Article
- DOI
10.1287/ijoc.2019.0928