Exploiting the Structure of Two-Stage Robust Optimization Models with Exponential Scenarios

Hossein Hashemi Doulabi (), Patrick Jaillet (), Gilles Pesant () and Louis-Martin Rousseau ()
Additional contact information
Hossein Hashemi Doulabi: Department of Mechanical, Industrial and Aerospace Engineering, Concordia University, Montreal, Quebec H3G 1M8, Canada; Interuniversity Research Center on Enterprise Networks, Logistics and Transportation (CIRRELT), Université de Montréal, Montreal, Quebec H3C 3J7, Canada
Patrick Jaillet: Department of Electrical Engineering and Computer Science, Laboratory for Information and Decision Systems, Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Gilles Pesant: Interuniversity Research Center on Enterprise Networks, Logistics and Transportation (CIRRELT), Université de Montréal, Montreal, Quebec H3C 3J7, Canada; Department of Computer and Software Engineering, Polytechnique Montréal, Montreal, Quebec H3T 1J4, Canada
Louis-Martin Rousseau: Interuniversity Research Center on Enterprise Networks, Logistics and Transportation (CIRRELT), Université de Montréal, Montreal, Quebec H3C 3J7, Canada; Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montreal, Quebec H3T 1J4, Canada

INFORMS Journal on Computing, 2021, vol. 33, issue 1, 143-162

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.

Keywords: integer programming; Dantzig–Wolfe decomposition; two-stage robust optimization (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2019.0928 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:1:p:143-162

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().