S. Takriti et Jr. Birge, Lagrangian solution techniques and bounds for loosely coupled mixed-integer stochastic programs, OPERAT RES, 48(1), 2000, pp. 91-98
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.