IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v58y2010i1p229-243.html
   My bibliography  Save this article

Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Random Recourse

Author

Listed:
  • Lewis Ntaimo

    (Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas 77843)

Abstract

This paper introduces disjunctive decomposition for two-stage mixed 0-1 stochastic integer programs (SIPs) with random recourse. Disjunctive decomposition allows for cutting planes based on disjunctive programming to be generated for each scenario subproblem under a temporal decomposition setting of the SIP problem. A new class of valid inequalities for mixed 0-1 SIP with random recourse is presented. In particular, we derive valid inequalities that allow for scenario subproblems for SIP with random recourse but deterministic technology matrix and right-hand side vector to share cut coefficients. The valid inequalities are used to derive a disjunctive decomposition method whose derivation has been motivated by real-life stochastic server location problems with random recourse, which find many applications in operations research. Computational results with large-scale instances to demonstrate the potential of the method are reported.

Suggested Citation

  • Lewis Ntaimo, 2010. "Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Random Recourse," Operations Research, INFORMS, vol. 58(1), pages 229-243, February.
    • Handle: RePEc:inm:oropre:v:58:y:2010:i:1:p:229-243
    DOI: 10.1287/opre.1090.0693
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1090.0693
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1090.0693?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Shabbir Ahmed & Renan Garcia, 2003. "Dynamic Capacity Acquisition and Assignment under Uncertainty," Annals of Operations Research, Springer, vol. 124(1), pages 267-283, November.
    2. Willem Klein Haneveld & Maarten van der Vlerk, 1999. "Stochastic integer programming:General models and algorithms," Annals of Operations Research, Springer, vol. 85(0), pages 39-57, January.
    3. Rüdiger Schultz, 1993. "Continuity Properties of Expectation Functions in Stochastic Integer Programming," Mathematics of Operations Research, INFORMS, vol. 18(3), pages 578-589, August.
    4. Caroe, Claus C. & Tind, Jorgen, 1997. "A cutting-plane approach to mixed 0-1 stochastic integer programs," European Journal of Operational Research, Elsevier, vol. 101(2), pages 306-316, September.
    5. Egon Balas & Sebastián Ceria & Gérard Cornuéjols, 1996. "Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework," Management Science, INFORMS, vol. 42(9), pages 1229-1246, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. MacNeil, Moira & Bodur, Merve, 2024. "Leveraging decision diagrams to solve two-stage stochastic programs with binary recourse and logical linking constraints," European Journal of Operational Research, Elsevier, vol. 315(1), pages 228-241.
    2. Chao Li & Muhong Zhang & Kory Hedman, 2021. "Extreme Ray Feasibility Cuts for Unit Commitment with Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1037-1055, July.
    3. Onur Tavaslıoğlu & Oleg A. Prokopyev & Andrew J. Schaefer, 2019. "Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function," Operations Research, INFORMS, vol. 67(6), pages 1659-1677, November.
    4. Can Li & Ignacio E. Grossmann, 2019. "A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables," Journal of Global Optimization, Springer, vol. 75(2), pages 247-272, October.
    5. Andrew C. Trapp & Oleg A. Prokopyev & Andrew J. Schaefer, 2013. "On a Level-Set Characterization of the Value Function of an Integer Program and Its Application to Stochastic Programming," Operations Research, INFORMS, vol. 61(2), pages 498-511, April.
    6. Valicka, Christopher G. & Garcia, Deanna & Staid, Andrea & Watson, Jean-Paul & Hackebeil, Gabriel & Rathinam, Sivakumar & Ntaimo, Lewis, 2019. "Mixed-integer programming models for optimal constellation scheduling given cloud cover uncertainty," European Journal of Operational Research, Elsevier, vol. 275(2), pages 431-445.
    7. Nesbitt, Peter & Blake, Lewis R. & Lamas, Patricio & Goycoolea, Marcos & Pagnoncelli, Bernardo K. & Newman, Alexandra & Brickey, Andrea, 2021. "Underground mine scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 294(1), pages 340-352.
    8. Lawrence C. Leung & Gang Chen & Yer Van Hui & Wen He, 2016. "An Airfreight Forwarder’s Shipment Bidding and Logistics Planning," Transportation Science, INFORMS, vol. 50(1), pages 275-287, February.
    9. Li, Xiaohong & Yang, Dong & Hu, Mengqi, 2018. "A scenario-based stochastic programming approach for the product configuration problem under uncertainties and carbon emission regulations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 126-146.
    10. Liu, Bingqian & Bissuel, Côme & Courtot, François & Gicquel, Céline & Quadri, Dominique, 2024. "A generalized Benders decomposition approach for the optimal design of a local multi-energy system," European Journal of Operational Research, Elsevier, vol. 318(1), pages 43-54.
    11. Ward Romeijnders & Niels van der Laan, 2020. "Pseudo-Valid Cutting Planes for Two-Stage Mixed-Integer Stochastic Programs with Right-Hand-Side Uncertainty," Operations Research, INFORMS, vol. 68(4), pages 1199-1217, July.
    12. Brian Keller & Güzin Bayraksan, 2012. "Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Generalized Upper Bound Constraints," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 172-186, February.
    13. Zhen, Lu & He, Xueting & Zhuge, Dan & Wang, Shuaian, 2024. "Primal decomposition for berth planning under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 183(C).
    14. Fang, Yi-Ping & Sansavini, Giovanni, 2019. "Optimum post-disruption restoration under uncertainty for enhancing critical infrastructure resilience," Reliability Engineering and System Safety, Elsevier, vol. 185(C), pages 1-11.
    15. Qipeng Zheng & Jianhui Wang & Panos Pardalos & Yongpei Guan, 2013. "A decomposition approach to the two-stage stochastic unit commitment problem," Annals of Operations Research, Springer, vol. 210(1), pages 387-410, November.
    16. Qipeng P. Zheng & Panos M. Pardalos, 2010. "Stochastic and Risk Management Models and Solution Algorithm for Natural Gas Transmission Network Expansion and LNG Terminal Location Planning," Journal of Optimization Theory and Applications, Springer, vol. 147(2), pages 337-357, November.
    17. Fengqi You & Ignacio Grossmann, 2013. "Multicut Benders decomposition algorithm for process supply chain planning under uncertainty," Annals of Operations Research, Springer, vol. 210(1), pages 191-211, November.
    18. Saravanan Venkatachalam & Lewis Ntaimo, 2023. "Integer set reduction for stochastic mixed-integer programming," Computational Optimization and Applications, Springer, vol. 85(1), pages 181-211, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Brian Keller & Güzin Bayraksan, 2012. "Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Generalized Upper Bound Constraints," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 172-186, February.
    2. Maarten Vlerk, 2010. "Convex approximations for a class of mixed-integer recourse models," Annals of Operations Research, Springer, vol. 177(1), pages 139-150, June.
    3. repec:dgr:rugsom:02a21 is not listed on IDEAS
    4. repec:dgr:rugsom:03a14 is not listed on IDEAS
    5. repec:dgr:rugsom:04a28 is not listed on IDEAS
    6. R. Andrade & A. Lisser & N. Maculan & G. Plateau, 2005. "B&B Frameworks for the Capacity Expansion of High Speed Telecommunication Networks Under Uncertainty," Annals of Operations Research, Springer, vol. 140(1), pages 49-65, November.
    7. Klein Haneveld, Willem K. & Stougie, Leen & Vlerk, Maarten H. van der, 2004. "Simple Integer Recourse Models: Convexity and Convex Approximations," Research Report 04A21, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    8. Albareda-Sambola, Maria & Vlerk, Maarten H. van der & Fernandez, Elena, 2002. "Exact solutions to a class of stochastic generalized assignment problems," Research Report 02A11, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    9. repec:dgr:rugsom:02a11 is not listed on IDEAS
    10. Vlerk, Maarten H. van der, 2004. "Convex approximations for a class of mixed-integer recourse models," Research Report 04A28, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    11. repec:dgr:rugsom:04a21 is not listed on IDEAS
    12. Lewis Ntaimo, 2013. "Fenchel decomposition for stochastic mixed-integer programming," Journal of Global Optimization, Springer, vol. 55(1), pages 141-163, January.
    13. Vlerk, Maarten H. van der, 2002. "Convex approximations for complete integer recourse models," Research Report 02A21, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    14. Albareda-Sambola, Maria & van der Vlerk, Maarten H. & Fernandez, Elena, 2006. "Exact solutions to a class of stochastic generalized assignment problems," European Journal of Operational Research, Elsevier, vol. 173(2), pages 465-487, September.
    15. Ilke Bakir & Natashia Boland & Brian Dandurand & Alan Erera, 2020. "Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 145-163, January.
    16. Stougie, Leen & Vlerk, Maarten H. van der, 2003. "Approximation in stochastic integer programming," Research Report 03A14, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    17. Lars M. Hvattum & Arne Løkketangen & Gilbert Laporte, 2006. "Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic," Transportation Science, INFORMS, vol. 40(4), pages 421-438, November.
    18. repec:dgr:rugsom:00a52 is not listed on IDEAS
    19. Zhili Zhou & Yongpei Guan, 2013. "Two-stage stochastic lot-sizing problem under cost uncertainty," Annals of Operations Research, Springer, vol. 209(1), pages 207-230, October.
    20. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    21. Alves, Maria Joao & Climaco, Joao, 1999. "Using cutting planes in an interactive reference point approach for multiobjective integer linear programming problems," European Journal of Operational Research, Elsevier, vol. 117(3), pages 565-577, September.
    22. Manish Bansal & Yingqiu Zhang, 2021. "Scenario-based cuts for structured two-stage stochastic and distributionally robust p-order conic mixed integer programs," Journal of Global Optimization, Springer, vol. 81(2), pages 391-433, October.
    23. Riis, Morten & Andersen, Kim Allan, 2005. "Applying the minimax criterion in stochastic recourse programs," European Journal of Operational Research, Elsevier, vol. 165(3), pages 569-584, September.
    24. Drexl, Andreas & Nissen, Rudiger & Patterson, James H. & Salewski, Frank, 2000. "ProGen/[pi]x - An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions," European Journal of Operational Research, Elsevier, vol. 125(1), pages 59-72, August.
    25. Vipul Jain & Ignacio E. Grossmann, 2001. "Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 258-276, November.
    26. Hannes Schwarz & Valentin Bertsch & Wolf Fichtner, 2018. "Two-stage stochastic, large-scale optimization of a decentralized energy system: a case study focusing on solar PV, heat pumps and storage in a residential quarter," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(1), pages 265-310, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:58:y:2010:i:1:p:229-243. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.