A decomposition strategy for decision problems with endogenous uncertainty using mixed-integer programming

Decision problems under endogenous uncertainty are still challenging to solve, despite the advances in solution methods and increasing computational power. A novel framework called Decision Programming solves such decision problems using off-the-shelf solvers by using influence diagrams to represent decision problems with decision-dependent probabilities, and then converting the influence diagram representation of the problem to a mixed-integer linear programming problem.

This paper extends Decision Programming to accommodate the other fundamental type of endogenous uncertainty: conditionally observed information. Multi-stage stochastic programming (MSSP) models use conditional non-anticipativity constraints (C-NACs) to represent such uncertainties, and we show how such constraints can be incorporated into Decision Programming models. This allows us to consider both types of endogenous uncertainty simultaneously. Additionally, we present a decomposition approach that enables including continuous decision variables, whereas the original formulation was restricted to discrete variables only; and also provides significant computational savings.

The extended framework is illustrated with two example problems. The first considers an illustrative multiperiod game and the second is a large-scale cost-benefit problem regarding climate change mitigation. Neither of these example problems could be solved with existing frameworks.

 

 

 

Article

Download

View A decomposition strategy for decision problems with endogenous uncertainty using mixed-integer programming