Hull scenario generation for two-stage stochastic programs with incomplete recourse

Abstract

In many stochastic programming problems, a common approach to treat uncertainty is to identify a number of scenarios to represent future realisations. In this way, it is possible to obtain a solution by solving a large-scale deterministic equivalent program. However, the program size may grow very large, and hence, a smaller but representative sample of scenarios is used to solve the program. In this dissertation, we focus on Monte-Carlo sampling based methods for solving two-stage stochastic programs with a fixed recourse matrix. Determining whether the approximated solution is good enough is a fundamental question in optimisation theory and algorithms. To this end, the characteristics of quality of a solution have been recently presented for the relatively complete recourse cases. Therefore, we focus on more difficult two-stage problems with incomplete recourse. The presented cases show the difficulties as the approximated solution obtained for a specific sample size is infeasible for the original set of scenarios that never appears in the case of a relatively complete recourse. The method proposed in this dissertation to overwhelm the infeasibility problem is to create any general hull of the original set of scenarios and then include the vertices of the hull as additional scenarios in the sample. We showed that the obtained optimal solution for this enlarged sample is contained in the feasible region of all possible scenarios. Indeed, the approximate solution may be pessimistic, but feasible and, hence in comparison with mentioned cases is an improvement. The other problem which we presented is to find a compromise between the number of additional scenarios and tightness of the hull. We applied the developed techniques to test instances of two-stage linear programs with incomplete recourse and finally we solved a reduced version of the real-world melt control model to show how the techniques may help metallurgists developing their charge policies in the Czech foundries.