IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v72y2019i3d10.1007_s10589-018-00055-9.html
   My bibliography  Save this article

An algorithm for binary linear chance-constrained problems using IIS

Author

Listed:
  • Gianpiero Canessa

    (Universidad Adolfo Ibañez)

  • Julian A. Gallego

    (AT Kearney Inc)

  • Lewis Ntaimo

    (Texas A&M University)

  • Bernardo K. Pagnoncelli

    (Universidad Adolfo Ibañez
    IEMS Department, Northwestern University)

Abstract

We propose an algorithm based on infeasible irreducible subsystems to solve binary linear chance-constrained problems with random technology matrix. By leveraging on the problem structure we are able to generate good quality upper bounds to the optimal value early in the algorithm, and the discrete domain is used to guide us efficiently in the search of solutions. We apply our methodology to individual and joint binary linear chance-constrained problems, demonstrating the ability of our approach to solve those problems. Extensive numerical experiments show that, in some cases, the number of nodes explored by our algorithm is drastically reduced when compared to a commercial solver.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:coopap:v:72:y:2019:i:3:d:10.1007_s10589-018-00055-9
    DOI: 10.1007/s10589-018-00055-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-018-00055-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-018-00055-9?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. 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.
    2. 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.
    3. Miguel A. Lejeune, 2012. "Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems," Operations Research, INFORMS, vol. 60(6), pages 1356-1372, December.
    4. John Gleeson & Jennifer Ryan, 1990. "Identifying Minimally Infeasible Subsystems of Inequalities," INFORMS Journal on Computing, INFORMS, vol. 2(1), pages 61-63, February.
    5. Lejeune, Miguel & Noyan, Nilay, 2010. "Mathematical programming approaches for generating p-efficient points," European Journal of Operational Research, Elsevier, vol. 207(2), pages 590-600, December.
    6. Zhu, Minkang & Taylor, Daniel B. & Sarin, Subhash C. & Kramer, Randall A., 1994. "Chance Constrained Programming Models For Risk-Based Economic And Policy Analysis Of Soil Conservation," Agricultural and Resource Economics Review, Northeastern Agricultural and Resource Economics Association, vol. 23(1), pages 1-8, April.
    7. A. Charnes & W. W. Cooper & G. H. Symonds, 1958. "Cost Horizons and Certainty Equivalents: An Approach to Stochastic Programming of Heating Oil," Management Science, INFORMS, vol. 4(3), pages 235-263, April.
    8. Shabbir Ahmed & Dimitri J. Papageorgiou, 2013. "Probabilistic Set Covering with Correlations," Operations Research, INFORMS, vol. 61(2), pages 438-452, April.
    9. Patrizia Beraldi & Andrzej Ruszczyński, 2002. "The Probabilistic Set-Covering Problem," Operations Research, INFORMS, vol. 50(6), pages 956-967, December.
    10. Abdelaziz, Fouad Ben & Aouni, Belaid & Fayedh, Rimeh El, 2007. "Multi-objective stochastic programming for portfolio selection," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1811-1823, March.
    11. 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.
    12. Beasley, J. E., 1987. "An algorithm for set covering problem," European Journal of Operational Research, Elsevier, vol. 31(1), pages 85-93, July.
    Full references (including those not matched with items on IDEAS)

    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. Xiaodi Bai & Jie Sun & Xiaojin Zheng, 2021. "An Augmented Lagrangian Decomposition Method for Chance-Constrained Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1056-1069, July.
    2. Miguel Lejeune, 2012. "Pattern definition of the p-efficiency concept," Annals of Operations Research, Springer, vol. 200(1), pages 23-36, November.
    3. Jianqiang Cheng & Richard Li-Yang Chen & Habib N. Najm & Ali Pinar & Cosmin Safta & Jean-Paul Watson, 2018. "Chance-constrained economic dispatch with renewable energy and storage," Computational Optimization and Applications, Springer, vol. 70(2), pages 479-502, June.
    4. Xiao Liu & Simge Küçükyavuz, 2018. "A polyhedral study of the static probabilistic lot-sizing problem," Annals of Operations Research, Springer, vol. 261(1), pages 233-254, February.
    5. 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.
    6. Miguel A. Lejeune, 2012. "Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems," Operations Research, INFORMS, vol. 60(6), pages 1356-1372, December.
    7. 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.
    8. Giada Spaccapanico Proietti & Mariagiulia Matteucci & Stefania Mignani & Bernard P. Veldkamp, 2024. "Chance-Constrained Automated Test Assembly," Journal of Educational and Behavioral Statistics, , vol. 49(1), pages 92-120, February.
    9. 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.
    10. 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.
    11. 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.
    12. Ran Ji & Miguel A. Lejeune, 2018. "Risk-budgeting multi-portfolio optimization with portfolio and marginal risk constraints," Annals of Operations Research, Springer, vol. 262(2), pages 547-578, March.
    13. Timo Berthold & Jakob Witzig, 2021. "Conflict Analysis for MINLP," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 421-435, May.
    14. Lukáš Adam & Martin Branda, 2016. "Nonlinear Chance Constrained Problems: Optimality Conditions, Regularization and Solvers," Journal of Optimization Theory and Applications, Springer, vol. 170(2), pages 419-436, August.
    15. 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.
    16. Miguel A. Lejeune & Andrzej Ruszczyński, 2007. "An Efficient Trajectory Method for Probabilistic Production-Inventory-Distribution Problems," Operations Research, INFORMS, vol. 55(2), pages 378-394, April.
    17. René Brandenberg & Paul Stursberg, 2021. "Refined cut selection for benders decomposition: applied to network capacity expansion problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 94(3), pages 383-412, December.
    18. Junhong Guo & William Pozehl & Amy Cohn, 2023. "A two-stage partial fixing approach for solving the residency block scheduling problem," Health Care Management Science, Springer, vol. 26(2), pages 363-393, June.
    19. Wang, Tingsong & Meng, Qiang & Wang, Shuaian & Tan, Zhijia, 2013. "Risk management in liner ship fleet deployment: A joint chance constrained programming model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 60(C), pages 1-12.
    20. Mahdi Noorizadegan & Abbas Seifi, 2018. "An efficient computational method for large scale surgery scheduling problems with chance constraints," Computational Optimization and Applications, Springer, vol. 69(2), pages 535-561, March.

    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:coopap:v:72:y:2019:i:3:d:10.1007_s10589-018-00055-9. 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.