Why is stochastic optimization necessary

Stochastic optimization

This enables a more realistic modeling of many economic issues in which the input data such as prices, product demand, resources or capacities are often not exactly known at the time of decision-making. Introductory standard works are the books by Kall and Wallace [Kall, Wallace 1994] and by Birge and Louveaux [Birge, Louveaux 1997].

Optimal decision-making under uncertainty

Three approaches have been established for dealing with uncertainty in decision-making problems [Madanski 1960]:

  • "Expected value" - In this approach, the expected value of the underlying random distribution is determined for each uncertain date. The deterministic optimization model is solved for this “averaged” data (the so-called expected-value problem (EV)). The optimal solution to this problem can then in turn be evaluated for all possible manifestations of the uncertain parameters (scenarios), which leads to the so-called expected value of the solution to the EV problem (EEV).

  • "Wait-and-see" - The basic assumption of this approach is that the decision maker has the opportunity to wait until the uncertainty has resolved and then to make the optimal decision. The “wait-and-see” problem therefore consists in calculating the distribution of the optimal objective function values ​​of the deterministic model for each possible scenario. The expected value of this distribution is called the “wait-and-see” value (WS). The disadvantage of the WS problem is that it does not provide a planning solution that can be implemented when the decision is actually made.

  • "Here-and-now" - The solution of the "here-and-now" problem (HN) delivers the optimal decision at the time of the decision making, which is permissible for every possible scenario. Optimality is usually defined via the expected value of the objective function across all scenarios. However, other optimality terms are also conceivable, for example if risk measures are to be taken into account. Then a multi-criteria optimization problem arises.

By comparing the EEV, WS and HN values, the so-called value of the complete information (EVPI) and the value of the stochastic solution (VSS) can be calculated. These values ​​provide information about the added value that is achieved by explicitly considering the uncertainty in the decision-making process.

Models and solution methods of stochastic programming

The models and solution methods of stochastic optimization mainly deal with the HN problem. The different model classes result from the typology of the mathematical programming (linear, non-linear, integer, etc.), from the temporal structure of the decision-making and the admissibility definition of the solution. The most important model classes are:

  • Two-stage and multi-stage stochastic programs with compensation - In this model type, which goes back to Dantzig [Dantzig 1955], the decision variables are assigned to those discrete points in time within the planning period at which the decision-making takes place. Level 1 decisions must always be made at the beginning of the planning period and are then fixed for all further levels. Two-stage linear stochastic programs can be efficiently solved for a discrete set of scenarios in many cases. The solution methods used are based on the decomposition method of linear programming (Benders decomposition). Multi-level, integer and non-linear stochastic programs can often not be solved or only with great effort (specialized solution methods) for practically relevant problem sizes.

  • Stochastic programs with probabilistic constraints - With this type of model developed by Charnes and Cooper [Charnes, Cooper 1959], the requirement that the solution must be permissible for all constraints and possible scenarios is dropped. Instead, so-called probabilistic constraints can be defined, which may be violated in some of the scenarios. The efficient solvability of this type of model depends on whether an efficiently solvable equivalent deterministic model can be derived. If this is not the case, then these models are very difficult to solve.

literature

Birge, J. R .; Louveaux, F .: Introduction to stochastic programming: Springer, 1997.

Charnes, A .; Cooper, W.W .: Chance-constrained programming: Management Science 5: 73-79, 1959.

Dantzig, G.B .: Linear Programming under uncertainty: Management Science 1: 197-206, 1955.

Kall, P; Wallace, S.W .: Stochastic Programming: John Wiley and Sons, 1994.

Madanski, M .: Inequalities for stochastic linear programming problems: Management Science 6: 197-204, 1960.

author


 

Jun.-Prof. Dr. Achim Koberstein, University of Paderborn, DS&OR Lab, junior professorship for business informatics, especially optimization systems, Warburger Str. 100, 33098 Paderborn

Author info


Item Actions