2016 Optimization Days

HEC Montréal, Québec, Canada, 2 — 4 May 2016

Schedule Authors My Schedule

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.

    • Frans de Ruiter, presenter, Tilburg University
    • Dimitris Bertsimas, Massachusetts Institute of Technology

    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

    • Seyed Hossein Hashemi Doulabi, presenter, Polytechnique Montréal
    • Patrick Jaillet, Massachusetts Institute of Technology
    • Gilles Pesant, Polytechnique Montréal
    • Louis-Martin Rousseau, Polytechnique Montréal

    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

    • Michael Poss, presenter, LIRMM
    • Artur Pessoa, UFF
    • Marin Bougeret, LIRMM

    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

    • Patrick Jaillet, Massachusetts Institute of Technology
    • Sanjay Dominik Jena, presenter, SMART, Massachusetts Institute of Technology
    • Tsan Sheng Ng, National University of Singapore
    • Melvyn Sim, NUS Business School

    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.