DISJUNCTIVE DECOMPOSITION (D2) FOR STOCHASTIC MIXED-INTEGER PROGRAMMING

Disjunctive decomposition or D² is a novel decomposition method for large-scale stochastic mixed-integer programming (SMIP) initiated by Professors S. Sen and J. L. Higle at the University of Arizona in 1998. This approach uses disjunctive programming to derive a valid inequality (cut) for one scenario problem and then translate it for other scenarios to gain on computation time. D2 is  applicable to a wide class of stochastic mixed-integer programming problems with many applications in science and engineering.

THEORY AND ILLUSTRATION

Ntaimo, L. and S. Sen. “A Branch-and-Cut Algorithm for Two-Stage Stochastic Mixed-Binary Programs With Continuous First-Stage Variables,” International. J. on Computational Science and Optimization, accepted 2006.

Sen, S.  and H.D. Sherali,  "Decomposition with Branch-and-Cut Approaches for Two Stage Stochastic Mixed-Integer Programming, Mathematical Programming," vol. 106, no. 2, pp. 203--223, 2006.

Sen, S. and J. L. Higle.  "The C³ Theorem and a D² Algorithm for Large Scale Stochastic Mixed-Integer Programming: Set Convexification," Mathematical Programming, Vol. 104, No. 1,  2005.

Sen, S., J. L. Higle, L. Ntaimo,  "A summary and illustration of disjunctive decomposition with set convexification," in Stochastic Integer Programming and Network Interdiction Models, D. L. Woodruff, Ed., Kluwer Academic Press, Dordrecht, The Netherlands, Chap. 6, 2002.

APPLICATIONS AND COMPUTATIONAL RESULTS

Telecommunications, Facility Location:

Ntaimo, L. and S. Sen. "The million-variable “march” for stochastic combinatorial optimization," Journal of Global Optimization, vol. 32, no. 3, 385-400, 2005.

Telecommunications, Strategic Supply Chain Planning under Uncertainty, Stochastic Matching:                                                  Ntaimo, L. and S. Sen, “A Comparative Study of Decomposition Algorithms for Stochastic Combinatorial Optimization,” Computational Optimization and Applications J., accepted, 2006.

Send mail to ntaimo@tamu.edu with questions or comments about this web site.
Copyright © 2007 L. Ntaimo
Last modified: 09/19/07