Journées de l'optimisation 2016
HEC Montréal, Québec, Canada, 2 — 4 mai 2016
TA5 TwoStage Robust Optimization I
3 mai 2016 10h30 – 12h10
Salle: MarieHusny
Présidée par Erick Delage
4 présentations

10h30  10h55
Duality in twostage linear adjustable robust optimization and its applications.
We derive and exploit duality in general twostage linear adjustable robust optimization models. The equivalent dualized formulation we derive is again a twostage linear adjustable robust optimization model. Therefore, all existing solution approaches for twostage 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 twostage lotsizing on a network and twostage 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.

10h55  11h20
Exploiting the structure of twostage robust optimization problems with integer variables in the adversary’s problem
This work addresses a class of twostage robust optimization models with integer variables in the adversary's problem. We discuss the importance of this class of robust problems in modeling twostage robust resource planning problems where some tasks with uncertain arrivals and durations are expected. We apply DantzigWolfe decomposition to exploit the structure of these models and show that the original problem reduces to a singlestage 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 Bendersdual algorithm. Extensive computational experiments on a twostage nurse planning problem are performed to compare these algorithms.

11h20  11h45
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 onemachine problems minimizing the weighted sum of completion times and multiple machines problems minimizing the makespan, providing polynomial algorithms, pseudopolynomial algorithms, and approximation algorithms (FPTAS, PTAS, constant factor and average nonconstant factor). In addition, we prove that the robust version of the polynomial problem 1sum w_j C_j is NPhard in the strong sense.

11h45  12h10
Satisficing awakens: Models to mitigate uncertainty
Satisficing, as an approach to decisionmaking 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 decisionmaking and propose a general satisficing modeling framework that yields tractable models for many practical situations.