A Texas Engineer has developed tractable solution schemes for difficult decision-making problems under uncertainty which are impacted by exogenous random quantities governed by a probability distribution which is itself only partially known.

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

Discovery: Tractable solution schemes for difficult decision-making problems under uncertainty which are impacted by exogenous random quantities governed by a probability distribution which is itself only partially known. Such decision problems give rise to ambiguous chance constrained programs that aim to determine the best decision in view of the most adverse or most benign distribution that is compatible with the available a priori information. 

In the paper “Ambiguous Joint Chance Constraints under Mean and Dispersion Information,” G. A. Hanasusanto and co-workers study ambiguous chance constrained programs where the unknown true probability distribution is characterized by the mean and the support of the random quantities, as well as by an upper bound on their dispersion. The researchers present a minimal set of conditions under which such problems give rise to tractable conic reformulations, and they demonstrate that the obtained reformulations allow to solve large-scale project management and image reconstruction models to global optimality. 

Why It Matters: The optimal design or control of a physical, engineering or economic system under uncertainty is a ubiquitous problem that arises in numerous practical applications. Such a problem can naturally be formulated as a chance constrained program that seeks the best decision that satisfies a number of uncertainty-affected safety conditions with a high probability. Classical models for chance constrained programming, however, suffer from the curse of dimensionality and are extremely challenging to solve. The proposed tractable solution schemes can therefore alleviate the computational burden of solving these difficult decision problems in the big data regime and will enable effective and efficient solutions for large-scale industrial size decision problems that are significantly affected by uncertainty (e.g., problems in energy systems, finance, supply chain, etc.).     

How it Works: By leveraging results from conic duality theory, the researchers first reduce the infinite dimensional optimization problem (over the set of probability measures) into an equivalent finite dimensional one. The emerging problem, however, is still generically intractable as it involves bilinear terms. The researchers then identify a minimal set of conditions under which the bilinear terms are amenable to tractable reformulations. Specifically, if the tractability conditions are satisfied then the emerging optimization problem is shown to be equivalent to a second-order cone program that can be solved very efficiently using standard off-the-shelf solvers (CPLEX, MOSEK, etc.). The researchers then demonstrate that the derived tractability conditions are tight, in the sense that the problem becomes immediately NP-hard whenever any of the conditions is violated. The researchers then assess the power of the conic programming reformulation in two real-life problems of huge scale: project management and image denoising. These problems give rise to chance constrained programs with 10,000 and 640,000 safety conditions, respectively. Such problem sizes are beyond the reach of any classical chance constrained programming models. The tractability result nevertheless allows to solve these problems exactly and quickly to global optimality.  

Published: Operations Research, “Ambiguous Joint Chance Constraints under Mean and Dispersion Information” 

What’s Next: The researchers have recently applied the schemes successfully to decision problems in energy systems, and are currently extending the proposed schemes to the multi-stage dynamic decision-making setting.