Duality in Two-Stage Adaptive Linear Optimization: Faster Computation and Stronger Bounds
- 1 July 2016
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 28 (3), 500-511
- https://doi.org/10.1287/ijoc.2016.0689
Abstract
In this paper we derive and exploit duality in general two-stage adaptive linear optimization models. The equivalent dualized formulation we derive is again a two-stage adaptive linear optimization model. Therefore, all existing solution approaches for two-stage adaptive 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.Keywords
This publication has 32 references indexed in Scilit:
- Solving two-stage robust optimization problems using a column-and-constraint generation methodOperations Research Letters, 2013
- On the power and limitations of affine policies in two-stage adaptive optimizationMathematical Programming, 2011
- Theory and Applications of Robust OptimizationSiam Review, 2011
- Facility Location: A Robust Optimization ApproachProduction and Operations Management, 2010
- Robust optimization for emergency logistics planning: Risk mitigation in humanitarian relief supply chainsTransportation Research Part B: Methodological, 2010
- Primal and dual linear decision rules in stochastic and robust optimizationMathematical Programming, 2009
- Robust improvement schemes for road networks under demand uncertaintyEuropean Journal of Operational Research, 2009
- Cutting-set methods for robust convex optimization with pessimizing oraclesOptimization Methods and Software, 2009
- Robust capacity expansion of network flowsNetworks, 2007
- Adjustable robust solutions of uncertain linear programsMathematical Programming, 2004