IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v55y2013i1p141-163.html
   My bibliography  Save this article

Fenchel decomposition for stochastic mixed-integer programming

Author

Listed:
  • Lewis Ntaimo

Abstract

This paper introduces a new cutting plane method for two-stage stochastic mixed-integer programming (SMIP) called Fenchel decomposition (FD). FD uses a class of valid inequalities termed, FD cuts, which are derived based on Fenchel cutting planes from integer programming. First, we derive FD cuts based on both the first and second-stage variables, and devise an FD algorithm for SMIP and establish finite convergence for binary first-stage. Second, we derive FD cuts based on the second-stage variables only and use an idea from disjunctive programming to lift the cuts to the higher dimension space including the first-stage variables. We then devise an alternative algorithm (FD-L algorithm) based on the lifted FD cuts. Finally, we report on computational results based on several test instances from the literature involving the special structure of knapsack problems with nonnegative left-hand side coefficients. The results are promising and show that both algorithms can outperform a standard direct solver and a disjunctive decomposition algorithm on large-scale instances. Furthermore, the FD-L algorithm provides better performance than the FD algorithm in general. Since Fenchel cuts can be computationally expensive in general and are best suited for problems with special structure, both algorithms exploit the special structure of the test instances by reducing the size of the cut generation problems based on the number of nonzero components in the non-integer solution that needs to be cut off. Copyright Springer Science+Business Media, LLC. 2013

Suggested Citation

  • Lewis Ntaimo, 2013. "Fenchel decomposition for stochastic mixed-integer programming," Journal of Global Optimization, Springer, vol. 55(1), pages 141-163, January.
    • Handle: RePEc:spr:jglopt:v:55:y:2013:i:1:p:141-163
    DOI: 10.1007/s10898-011-9817-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-011-9817-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-011-9817-8?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    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. Merve Bodur & James R. Luedtke, 2017. "Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service-System Staffing and Scheduling with Arrival Rate Uncertainty," Management Science, INFORMS, vol. 63(7), pages 2073-2091, 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. 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.
    5. Cheng Guo & Merve Bodur & Dionne M. Aleman & David R. Urbach, 2021. "Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1551-1569, October.
    6. Kathryn M. Schumacher & Amy E. M. Cohn & Richard Li-Yang Chen, 2017. "Algorithm for the N -2 Security-Constrained Unit Commitment Problem with Transmission Switching," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 645-659, November.
    7. Rui Chen & James Luedtke, 2022. "On Generating Lagrangian Cuts for Two-Stage Stochastic Integer Programs," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2332-2349, July.
    8. Niels Laan & Ward Romeijnders & Maarten H. Vlerk, 2018. "Higher-order total variation bounds for expectations of periodic functions and simple integer recourse approximations," Computational Management Science, Springer, vol. 15(3), pages 325-349, October.
    9. van der Laan, Niels & Romeijnders, Ward & van der Vlerk, M.H., 2017. "Higher-order total variation bounds for expectations of periodic functions and simple integer recourse approximations," Research Report 2017-014-EEF, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    10. Merve Bodur & Sanjeeb Dash & Oktay Günlük & James Luedtke, 2017. "Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 77-91, February.
    11. Pavlo Glushko & Csaba I. Fábián & Achim Koberstein, 2022. "An L-shaped method with strengthened lift-and-project cuts," Computational Management Science, Springer, vol. 19(4), pages 539-565, October.
    12. 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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Bansal, Manish & Mehrotra, Sanjay, 2019. "On solving two-stage distributionally robust disjunctive programs with a general ambiguity set," European Journal of Operational Research, Elsevier, vol. 279(2), pages 296-307.
    7. repec:dgr:rugsom:03a14 is not listed on IDEAS
    8. José Emmanuel Gómez-Rocha & Eva Selene Hernández-Gress & Héctor Rivera-Gómez, 2021. "Production planning of a furniture manufacturing company with random demand and production capacity using stochastic programming," PLOS ONE, Public Library of Science, vol. 16(6), pages 1-26, June.
    9. 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).
    10. repec:dgr:rugsom:02a11 is not listed on IDEAS
    11. 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).
    12. Kibaek Kim & Sanjay Mehrotra, 2015. "A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management," Operations Research, INFORMS, vol. 63(6), pages 1431-1451, December.
    13. repec:dgr:rugsom:02a21 is not listed on IDEAS
    14. 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.
    15. Pavlo Glushko & Csaba I. Fábián & Achim Koberstein, 2022. "An L-shaped method with strengthened lift-and-project cuts," Computational Management Science, Springer, vol. 19(4), pages 539-565, October.
    16. repec:dgr:rugsom:04a28 is not listed on IDEAS
    17. 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.
    18. 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).
    19. Yan, Yongze & Hong, Liu & He, Xiaozheng & Ouyang, Min & Peeta, Srinivas & Chen, Xueguang, 2017. "Pre-disaster investment decisions for strengthening the Chinese railway system under earthquakes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 39-59.
    20. Eyyüb Y. Kıbış & İ. Esra Büyüktahtakın & Robert G. Haight & Najmaddin Akhundov & Kathleen Knight & Charles E. Flower, 2021. "A Multistage Stochastic Programming Approach to the Optimal Surveillance and Control of the Emerald Ash Borer in Cities," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 808-834, May.
    21. 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).
    22. Pascal Hentenryck & Russell Bent & Eli Upfal, 2010. "Online stochastic optimization under time constraints," Annals of Operations Research, Springer, vol. 177(1), pages 151-183, June.
    23. repec:dgr:rugsom:04a21 is not listed on IDEAS
    24. 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.
    25. 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.

    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:spr:jglopt:v:55:y:2013:i:1:p:141-163. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.