IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v207y2010i1p290-296.html
   My bibliography  Save this article

IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation

Author

Listed:
  • Tanner, Matthew W.
  • Ntaimo, Lewis

Abstract

We present a new method for solving stochastic programs with joint chance constraints with random technology matrices and discretely distributed random data. The problem can be reformulated as a large-scale mixed 0-1 integer program. We derive a new class of optimality cuts called IIS cuts and apply them to our problem. The cuts are based on irreducibly infeasible subsystems (IIS) of an LP defined by requiring that all scenarios be satisfied. We propose a method for improving the upper bound of the problem when no cut can be found. We derive and implement a branch-and-cut algorithm based on IIS cuts, and refer to this algorithm as the IIS branch-and-cut algorithm. We report on computational results with several test instances from optimal vaccine allocation. The computational results are promising as the IIS branch-and-cut algorithm gives better results than a state-of-the-art commercial solver on one class of problems.

Suggested Citation

  • Tanner, Matthew W. & Ntaimo, Lewis, 2010. "IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation," European Journal of Operational Research, Elsevier, vol. 207(1), pages 290-296, November.
    • Handle: RePEc:eee:ejores:v:207:y:2010:i:1:p:290-296
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00338-3
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. van Loon, J. N. M., 1981. "Irreducibly inconsistent systems of linear inequalities," European Journal of Operational Research, Elsevier, vol. 8(3), pages 283-288, November.
    2. John Gleeson & Jennifer Ryan, 1990. "Identifying Minimally Infeasible Subsystems of Inequalities," INFORMS Journal on Computing, INFORMS, vol. 2(1), pages 61-63, February.
    3. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    4. B. K. Pagnoncelli & S. Ahmed & A. Shapiro, 2009. "Sample Average Approximation Method for Chance Constrained Programming: Theory and Applications," Journal of Optimization Theory and Applications, Springer, vol. 142(2), pages 399-416, August.
    5. Hyunhee An & J. Wayland Eheart, 2007. "A Screening Technique for Joint Chance-Constrained Programming for Air-Quality Management," Operations Research, INFORMS, vol. 55(4), pages 792-798, August.
    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. Minjiao Zhang & Simge Küçükyavuz & Saumya Goel, 2014. "A Branch-and-Cut Method for Dynamic Decision Making Under Joint Chance Constraints," Management Science, INFORMS, vol. 60(5), pages 1317-1333, May.
    2. Miguel A. Lejeune, 2012. "Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems," Operations Research, INFORMS, vol. 60(6), pages 1356-1372, December.
    3. Miguel A. Lejeune & Janne Kettunen, 2017. "Managing Reliability and Stability Risks in Forest Harvesting," Manufacturing & Service Operations Management, INFORMS, vol. 19(4), pages 620-638, October.
    4. B. K. Pagnoncelli & D. Reich & M. C. Campi, 2012. "Risk-Return Trade-off with the Scenario Approach in Practice: A Case Study in Portfolio Selection," Journal of Optimization Theory and Applications, Springer, vol. 155(2), pages 707-722, November.
    5. Reich, Daniel, 2013. "A linear programming approach for linear programs with probabilistic constraints," European Journal of Operational Research, Elsevier, vol. 230(3), pages 487-494.
    6. Rey, David & Hammad, Ahmed W. & Saberi, Meead, 2023. "Vaccine allocation policy optimization and budget sharing mechanism using reinforcement learning," Omega, Elsevier, vol. 115(C).
    7. Miguel A. Lejeune & François Margot, 2016. "Solving Chance-Constrained Optimization Problems with Stochastic Quadratic Inequalities," Operations Research, INFORMS, vol. 64(4), pages 939-957, August.
    8. Feng Qiu & Shabbir Ahmed & Santanu S. Dey & Laurence A. Wolsey, 2014. "Covering Linear Programming with Violations," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 531-546, August.
    9. Muckstadt, John A. & Klein, Michael G. & Jackson, Peter L. & Gougelet, Robert M. & Hupert, Nathaniel, 2023. "Efficient and effective large-scale vaccine distribution," International Journal of Production Economics, Elsevier, vol. 262(C).
    10. Hosseini-Motlagh, Seyyed-Mahdi & Samani, Mohammad Reza Ghatreh & Homaei, Shamim, 2023. "Design of control strategies to help prevent the spread of COVID-19 pandemic," European Journal of Operational Research, Elsevier, vol. 304(1), pages 219-238.
    11. Duijzer, Lotty Evertje & van Jaarsveld, Willem & Dekker, Rommert, 2018. "Literature review: The vaccine supply chain," European Journal of Operational Research, Elsevier, vol. 268(1), pages 174-192.
    12. Thul, Lawrence & Powell, Warren, 2023. "Stochastic optimization for vaccine and testing kit allocation for the COVID-19 pandemic," European Journal of Operational Research, Elsevier, vol. 304(1), pages 325-338.
    13. Youssouf A. F. Toukourou & Franc{c}ois Dufresne, 2015. "ON Integrated Chance Constraints in ALM for Pension Funds," Papers 1503.05343, arXiv.org.
    14. Ece Zeliha Demirci & Nesim Kohen Erkip, 2020. "Designing intervention scheme for vaccine market: a bilevel programming approach," Flexible Services and Manufacturing Journal, Springer, vol. 32(2), pages 453-485, June.
    15. Shanshan Wang & Jinlin Li & Sanjay Mehrotra, 2021. "Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1661-1677, October.
    16. Miguel A. Lejeune & Janne Kettunen, 2018. "A fractional stochastic integer programming problem for reliability-to-stability ratio in forest harvesting," Computational Management Science, Springer, vol. 15(3), pages 583-597, October.
    17. Gianpiero Canessa & Julian A. Gallego & Lewis Ntaimo & Bernardo K. Pagnoncelli, 2019. "An algorithm for binary linear chance-constrained problems using IIS," Computational Optimization and Applications, Springer, vol. 72(3), pages 589-608, April.
    18. Choudhury, Nishat Alam & Ramkumar, M. & Schoenherr, Tobias & Singh, Shalabh, 2023. "The role of operations and supply chain management during epidemics and pandemics: Potential and future research opportunities," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    19. Yongjia Song & James R. Luedtke & Simge Küçükyavuz, 2014. "Chance-Constrained Binary Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 735-747, November.

    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. Jérémy Omer & Michael Poss, 2021. "Identifying relatively irreducible infeasible subsystems of linear inequalities," Annals of Operations Research, Springer, vol. 304(1), pages 361-379, September.
    2. Dursun, Pınar & Taşkın, Z. Caner & Altınel, İ. Kuban, 2019. "The determination of optimal treatment plans for Volumetric Modulated Arc Therapy (VMAT)," European Journal of Operational Research, Elsevier, vol. 272(1), pages 372-388.
    3. Zheng Zhang & Brian T. Denton & Xiaolan Xie, 2020. "Branch and Price for Chance-Constrained Bin Packing," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 547-564, July.
    4. Gianpiero Canessa & Julian A. Gallego & Lewis Ntaimo & Bernardo K. Pagnoncelli, 2019. "An algorithm for binary linear chance-constrained problems using IIS," Computational Optimization and Applications, Springer, vol. 72(3), pages 589-608, April.
    5. Lihui Bai & Paul A. Rubin, 2009. "Combinatorial Benders Cuts for the Minimum Tollbooth Problem," Operations Research, INFORMS, vol. 57(6), pages 1510-1522, December.
    6. Kai Kellner & Marc E. Pfetsch & Thorsten Theobald, 2019. "Irreducible Infeasible Subsystems of Semidefinite Systems," Journal of Optimization Theory and Applications, Springer, vol. 181(3), pages 727-742, June.
    7. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    8. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2015. "Benders Decomposition for Production Routing Under Demand Uncertainty," Operations Research, INFORMS, vol. 63(4), pages 851-867, August.
    9. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    10. G. Pantuso & L. M. Hvattum, 2021. "Maximizing performance with an eye on the finances: a chance-constrained model for football transfer market decisions," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(2), pages 583-611, July.
    11. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    12. William B. Haskell & Wenjie Huang & Huifu Xu, 2018. "Preference Elicitation and Robust Optimization with Multi-Attribute Quasi-Concave Choice Functions," Papers 1805.06632, arXiv.org.
    13. Clavijo López, Christian & Crama, Yves & Pironet, Thierry & Semet, Frédéric, 2024. "Multi-period distribution networks with purchase commitment contracts," European Journal of Operational Research, Elsevier, vol. 312(2), pages 556-572.
    14. Hadi Karimi & Sandra D. Ekşioğlu & Michael Carbajales-Dale, 2021. "A biobjective chance constrained optimization model to evaluate the economic and environmental impacts of biopower supply chains," Annals of Operations Research, Springer, vol. 296(1), pages 95-130, January.
    15. David Bergman & Carlos H. Cardonha & Andre A. Cire & Arvind U. Raghunathan, 2019. "On the Minimum Chordal Completion Polytope," Operations Research, INFORMS, vol. 67(2), pages 532-547, March.
    16. Dell’Amico, Mauro & Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2019. "Mathematical models and decomposition methods for the multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 274(3), pages 886-899.
    17. Axel von Kamp & Steffen Klamt, 2014. "Enumeration of Smallest Intervention Strategies in Genome-Scale Metabolic Networks," PLOS Computational Biology, Public Library of Science, vol. 10(1), pages 1-13, January.
    18. Belieres, Simon & Hewitt, Mike & Jozefowiez, Nicolas & Semet, Frédéric & Van Woensel, Tom, 2020. "A Benders decomposition-based approach for logistics service network design," European Journal of Operational Research, Elsevier, vol. 286(2), pages 523-537.
    19. Daniel Baena & Jordi Castro & Antonio Frangioni, 2020. "Stabilized Benders Methods for Large-Scale Combinatorial Optimization, with Application to Data Privacy," Management Science, INFORMS, vol. 66(7), pages 3051-3068, July.
    20. Timo Berthold & Jakob Witzig, 2021. "Conflict Analysis for MINLP," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 421-435, 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:eee:ejores:v:207:y:2010:i:1:p:290-296. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.