Abstract
In this paper we review the Disjunctive Decomposition (D2) algorithm for two-stage Stochastic Mixed Integer Programs (SMIP). This novel method uses principles of disjunctive programming to develop cutting-plane-based approximations of the feasible set of the second stage problem. At the core of this approach is the Common Cut Coefficient Theorem, which provides a mechanism for transforming cuts derived for one outcome of the second stage problem into cuts that are valid for other outcomes. An illustrative application of the D2 method to the solution of a small SMIP illustrative example is provided.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Balas, E. [1979], “Disjunctive Programming,” Annals of Discrete Mathematics, 5, pp. 3–51.
Balas, E.S. Ceria, and G. Cornuéjols [1993], “A lift-and-project cutting plane algorithm for mixed 0–1 integer programs,” Math. Programming, 58, pp. 295–324.
Benders, J.F. [1962], “Partitioning procedures for solving mixed-variable programming problems,” Numerische Mathematic 4, pp. 238–252.
Blair, C. [1995], “A closed-form representation of mixed-integer program value functions,” Math. Programming, 71, pp. 127–136.
Blair, C, and R. Jeroslow [1982], “The value function of an integer program,” Math. Programming, 23, pp. 237–273.
Carøe, C.C. [1998], Decomposition in Stochastic Integer Programming, Ph.D. thesis, Institute of Mathematical Sciences, Dept. of Operations Research, University of Copenhagen, Denmark.
Schultz, R., L. Stougie, and M.H. van der Vlerk [1998], “Solving stochastic programs with integer recourse by enumeration; a framework using Gröbner basis reduction,” Math. Programming, 83, pp. 71–94.
Sen, S. and J.L. Higle [2000], The C3 Theorem and a D2 Algorithm for Large Scale Stochastic Integer Programming: Set Convexification, Working Paper, Dept. of Systems and Industrial Engineering, The University of Arizona, Tucson AZ 85721. (submitted to Math. Programming
Sen, S. and H.D. Sherali [1987], “Nondifferentiable reverse convex programs and facetial cuts via a disjunctive characterization,” Math. Programming, 37, pp. 169–183.
Sherali, H.D. and W.P. Adams [1990], “A hierarchy of relaxations between the continuous and convex hull representations for 0–1 programming problems,” SIAM J. on Discrete Mathematics, 3, pp. 411–430.
Sherali, H.D. and B.M.P. Fraticelli [2002], “A modification of Benders’ decomposition algorithm for discrete subproblems: an approach for stochastic programs with integer recourse,” Journal of Global Optimization, 22, pp. 319–342.
Sherali, H.D. and CM. Shetty [1980], Optimization with Disjunctive Constraints, Lecture Notes in Economics and Math. Systems, Vol. 181, Springer-Verlag, Berlin.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Kluwer Academic Publishers
About this chapter
Cite this chapter
Sen, S., Higle, J.L., Ntaimo, L. (2003). A Summary and Illustration of Disjunctive Decomposition with Set Convexification. In: Woodruff, D.L. (eds) Network Interdiction and Stochastic Integer Programming. Operations Research/Computer Science Interfaces Series, vol 22. Springer, Boston, MA. https://doi.org/10.1007/0-306-48109-X_6
Download citation
DOI: https://doi.org/10.1007/0-306-48109-X_6
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4020-7302-1
Online ISBN: 978-0-306-48109-3
eBook Packages: Springer Book Archive