Optimization Online


Adjustability in Robust Linear Optimization

Ningji Wei (ningjiwei***at***cmu.edu)
Peter Zhang (pyzhang***at***cmu.edu)

Abstract: Dynamic robust optimization involves sequential decisions over multiple stages against worst-case uncertainty realizations. At each stage, the decision-maker observes the uncertainty realization before committing to decisions, known as adjustable decisions. We focus on adjustability --- the difference between objective values of two problems: a static robust optimization problem where all decisions have to be made prior to uncertainty realization, and a fully adjustable robust optimization problem where all decisions are made after uncertainty realization. In this work, we develop a theoretical framework to quantify adjustability based on the input data of a robust optimization problem with linear objective, linear constraints, and fixed recourse. We make very few additional assumptions. In particular, we do not assume constraint-wise separability or parameter nonnegativity. Based on the discovery of an interesting connection between the reformulations of the static and fully adjustable problems, our analysis gives a necessary and sufficient criterion for adjustability to be zero when the uncertainty set is polyhedral. Then, we develop a constructive approach to quantify adjustability when the uncertainty set is general. We also develop an efficient algorithm to bound adjustability. We exemplify the value of our theoretical framework by applying it to interdiction, supply chain design, and inventory control problems.

Keywords: Robust Optimization, Adjustable Robust Optimization, Adaptability Gap

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 10/11/2021
Entry Accepted: 10/11/2021
Entry Last Modified: 10/13/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