A Texas Engineer has developed a new data-driven solution scheme for two-stage decision-making problems under uncertainty. The proposed scheme is amenable to standard off-the-shelf optimization solvers and yields high quality solutions with attractive out-of-sample performance guarantees. 

UT Austin Researcher: Grani A. Hanasusanto, Assistant Professor of Operations Research & Industrial Engineering at The University of Texas at Austin

Discovery: In the paper “Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls,” G. Hanasusanto and D. Kuhn show that two-stage robust and distributionally robust linear programs can be reformulated exactly as conic programs that scale polynomially with the problem dimensions. These results directly extend to the classical robust setting and motivate strong tractable approximations based on semidefinite approximations of the copositive cone.

Why It Matters: Dynamic decision problems under uncertainty are prevalent in many areas of engineering, science and economics. These decision problems involve recourse decisions that adjust to the information observed over time, and thus can only be solved approximately by restricting the adaptive decisions to simple parametric decision rules. In this case, however, the corresponding approximation error can be substantial. Our exact reformulations enable decision makers to apply the state-of-the-art approximation schemes for the equivalent conic programs. Extensive numerical tests suggest that even the coarsest of these approximations distinctly outperform the best decision rule approximations in terms of accuracy.

How it Works: By leveraging techniques from copositive programming and data-driven distributionally robust optimization, the researchers are able to transform the infinite-dimensional two-stage problem into a concise finite-dimensional one. The emerging optimization problem is a linear program over the cone of copositive matrices, which is well studied in the literature. The researchers then approximate the cone using an established semidefinite-representable approximation. This gives rise to a tractable semidefinite program that can be solved efficiently using off-the-shelf optimization softwares (MOSEK, etc.). The researchers further identify sufficient conditions that lead to exactness of the semidefinite programs. The effectiveness of the proposed scheme is then assessed on large-scale instances of inventory planning problem.

Published: Operations Research, “Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

What’s Next: The researcher is extending the proposed scheme to multi-stage dynamic decision-making problems and investigating new applications in energy systems, inventory control and machine learning.