Optimization Online


A Primal-Dual Perspective on Adaptive Robust Linear Optimization

Jianzhe Zhen (trevorzhen***at***gmail.com)
Frans de Ruiter (fjctderuiter***at***gmail.com )

Abstract: Adaptive robust optimization is a modelling paradigm for multistage optimization under uncertainty where one seeks decisions that minimize the worst-case cost with respect to all possible scenarios in a prescribed uncertainty set. However, optimal policies for adaptive robust optimization problems are difficult to compute. Therefore, one often restricts to the class of affine policies which give good solutions. We propose a simple set-lifting procedure to enhance the quality of affine policies for adaptive robust linear optimization problems, which yields the optimal solution in finite iterations. Using a new lower bound technique, we compute tight lower bounds on the optimal value and the obtained solution can be used to warm start the exact methods to reduce the computation time. Leveraging the primal and dual formulations, we improve the efficiency and effectiveness of the exact solution method of Zeng and Zhao (2013), and extend their method to solve problems without complete recourse. The effectiveness of our proposed approach is demonstrated on a uncapacitated lot-sizing problem (with relatively complete recourse) and a capacitated lot-sizing problem (without relatively complete recourse).

Keywords: affine policies, reformulation linearization technique, column-and-constraint generation algorithm

Category 1: Robust Optimization



Entry Submitted: 10/14/2019
Entry Accepted: 10/14/2019
Entry Last Modified: 08/19/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society