Adjustability in Robust Linear Optimization

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.

Article

Download

View Adjustability in Robust Linear Optimization