2016 Optimization Days
HEC Montréal, Québec, Canada, 2 — 4 May 2016
TA5 Two-Stage Robust Optimization I
May 3, 2016 10:30 AM – 12:10 PM
Location: Marie-Husny
Chaired by Erick Delage
4 Presentations
-
10:30 AM - 10:55 AM
Duality in two-stage linear adjustable robust optimization and its applications.
We derive and exploit duality in general two-stage linear adjustable robust optimization models. The equivalent dualized formulation we derive is again a two-stage linear adjustable robust optimization model. Therefore, all existing solution approaches for two-stage linear adjustable robust models can be used to solve or approximate the dual formulation. The new dualized model differs from the primal formulation in its dimension and uses a different description of the uncertainty set. We show that the optimal primal affine policy can be directly obtained from the optimal affine policy in the dual formulation. We provide empirical evidence that the dualized model in the context of two-stage lot-sizing on a network and two-stage facility location problems solves an order of magnitude faster than the primal formulation with affine policies. We also provide an explanation and associated empirical evidence that offer insight on which characteristics of the dualized formulation make computations faster. Furthermore, the affine policy of the dual formulations can be used to provide stronger lower bounds on the optimality of affine policies.
-
10:55 AM - 11:20 AM
Exploiting the structure of two-stage robust optimization problems with integer variables in the adversary’s problem
This work addresses a class of two-stage robust optimization models with integer variables in the adversary's problem. We discuss the importance of this class of robust problems in modeling two-stage robust resource planning problems where some tasks with uncertain arrivals and durations are expected. 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 problem. Since the master problem and subproblem in the Benders algorithm are mixed integer programs it is computationally burdensome to optimally solve them in each iteration of the algorithm. Therefore, we develop novel stopping conditions for these mixed integer programs and provide the relevant convergence proofs. We also develop a heuristic algorithm called dual algorithm. In this heuristic, we dualize the linear programming relaxation of the adversary's problem in the reformulated problem and iteratively generate cuts to shape the convex hull of the uncertainty set. We combine this heuristic with the Benders algorithm to create a more effective algorithm called Benders-dual algorithm. Extensive computational experiments on a two-stage nurse planning problem are performed to compare these algorithms.
-
11:20 AM - 11:45 AM
Robust scheduling with budgeted uncertainty
In this work we study min max robust scheduling problems assuming that the processing times can take any value in the budgeted uncertainty set introduced by Bertsimas and Sim (2003,2004). We focus more particularly on one-machine problems minimizing the weighted sum of completion times and multiple machines problems minimizing the makespan, providing polynomial algorithms, pseudo-polynomial algorithms, and approximation algorithms (FPTAS, PTAS, constant factor and average non-constant factor). In addition, we prove that the robust version of the polynomial problem 1||sum w_j C_j is NP-hard in the strong sense.
-
11:45 AM - 12:10 PM
Satisficing awakens: Models to mitigate uncertainty
Satisficing, as an approach to decision-making under uncertainty, aims at achieving solutions that satisfy the problem's constraints as well as possible. In this paper, we study key features of satisficing decision-making and propose a general satisficing modeling framework that yields tractable models for many practical situations.