Stochastic Integer Programming by Dynamic Programming

摘要

Optimization models in stochastic programming are considered. The dynamic programming algorithms for two-stage scheduling, bin packing and multiknapsack problems are studied. The numerical results are compared with results obtained by heuristics for the scheduling and bin packing problem. The computational experience gives empirical insight into the shape of the value functions of stochastic integer programming problems and shows the existence of discontinuities and nonconvexities. The results can be regarded as a first theory for stochastic integer programming.