Lagrangian solution techniques and bounds for loosely coupled mixed-integer stochastic programs

Many production problems involve facility setups that lead to integer varia bles, production decisions that are continuous, and demands that are likely to be random. While these problems can be quite difficult to solve, we pro pose a model and an efficient solution technique for this basic class of st ochastic mixed-integer programs. We use a set of scenarios to reflect uncer tainty. The resulting mathematical model is solved using Lagrangian relaxat ion. We show that the duality gap of our relaxation is bounded above by a c onstant that depends on the cost function and the number of branching point s in the scenario tree. We apply our technique to the problem of generating electric power. Numerical results indicate significant savings when the st ochastic model is used instead of a deterministic one.