[Previous chapter] [Next chapter]

Solution techniques

---

Various specialized algorithms can be used to solve stochastic problems. These algorithms can further be categorized, but in this section, we outline merely the generalized form of these algorithms.

• 2-stage:
  • LP: Stochastic linear programs are typically solved using the L-shaped method. This method falls in to the category of outer linearization methods where cuts (feasibility and optimality) are generated to solve the problem faster. The most prevalent versions of L-shaped method are single cut and multi-cut. LPs are also solved using the inner linearization methods, which essentially involved column generation by using the Dantzig-Wolfe decomposition method. Other methods such as basis factorization are quite intensive computationally.
  • IP: For integer problems, the Integer L-shaped method is used. If the 2-stage problem consists of binary first stage variables, then special kinds of cuts can be generated in order to obtain the solutions faster. Special techniques for MIP's can also be applied by decomposing the second stage variables in a 2-stage problem into discrete and continuous parts.
• Multi-stage:
  • Nested Decomposition methods are available for solving the multi-stage LP. The algorithm involves column generation from the previous sub-problems and using them in the current period master problem. The LP are solved by Nested L-shaped methods.

[Next] [Index]

---

If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.