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

Cell-and-bound algorithm for chance constrained programs with discrete distributions

Author

Listed:
  • Zheng, Xiaojin
  • Wu, Baiyi
  • Cui, Xueting

Abstract

Chance constrained programing (CCP) is often encountered in real-world applications when there is uncertainty in the data and parameters. We consider in this paper a special case of CCP with finite discrete distributions. We propose a novel approach for solving CCP. The methodology is based on the connection between CCP and arrangement of hyperplanes. By involving cell enumeration methods for an arrangement of hyperplanes in discrete geometry, we develop a cell-and-bound algorithm to identify an exact solution to CCP, which is much more efficient than branch-and-bound algorithms especially in the worst case. Furthermore, based on the cell-and-bound algorithm, a new polynomial solvable subclass of CCP is discovered. We also find that the probabilistic version of the classical transportation problem is polynomially solvable when the number of customers is fixed. We report preliminary computational results to demonstrate the effectiveness of our algorithm.

Suggested Citation

  • Zheng, Xiaojin & Wu, Baiyi & Cui, Xueting, 2017. "Cell-and-bound algorithm for chance constrained programs with discrete distributions," European Journal of Operational Research, Elsevier, vol. 260(2), pages 421-431.
    • Handle: RePEc:eee:ejores:v:260:y:2017:i:2:p:421-431
    DOI: 10.1016/j.ejor.2017.01.046
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717300814
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.01.046?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. Fama, Eugene F & French, Kenneth R, 1992. "The Cross-Section of Expected Stock Returns," Journal of Finance, American Finance Association, vol. 47(2), pages 427-465, June.
    2. Bruce L. Miller & Harvey M. Wagner, 1965. "Chance Constrained Programming with Joint Constraints," Operations Research, INFORMS, vol. 13(6), pages 930-945, December.
    3. William F. Sharpe, 1963. "A Simplified Model for Portfolio Analysis," Management Science, INFORMS, vol. 9(2), pages 277-293, January.
    4. Gren, Ing-Marie, 2008. "Adaptation and mitigation strategies for controlling stochastic water pollution: An application to the Baltic Sea," Ecological Economics, Elsevier, vol. 66(2-3), pages 337-347, June.
    5. Zheng, Xiaojin & Sun, Xiaoling & Li, Duan & Cui, Xueting, 2012. "Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs," European Journal of Operational Research, Elsevier, vol. 221(1), pages 38-48.
    6. 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.
    7. Lejeune, Miguel A. & Shen, Siqian, 2016. "Multi-objective probabilistically constrained programs with variable risk: Models for multi-portfolio financial optimization," European Journal of Operational Research, Elsevier, vol. 252(2), pages 522-539.
    8. C. van de Panne & W. Popp, 1963. "Minimum-Cost Cattle Feed Under Probabilistic Protein Constraints," Management Science, INFORMS, vol. 9(3), pages 405-430, April.
    9. Fama, Eugene F & French, Kenneth R, 1995. "Size and Book-to-Market Factors in Earnings and Returns," Journal of Finance, American Finance Association, vol. 50(1), pages 131-155, March.
    10. 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.
    11. Harry Markowitz, 1952. "Portfolio Selection," Journal of Finance, American Finance Association, vol. 7(1), pages 77-91, March.
    12. 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.
    13. Miguel A. Lejeune, 2012. "Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems," Operations Research, INFORMS, vol. 60(6), pages 1356-1372, December.
    14. Júlíus Atlason & Marina Epelman & Shane Henderson, 2004. "Call Center Staffing with Simulation and Cutting Plane Methods," Annals of Operations Research, Springer, vol. 127(1), pages 333-358, March.
    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. 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.

    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. 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.
    2. 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.
    3. Fernando Rubio, 2005. "Eficiencia De Mercado, Administracion De Carteras De Fondos Y Behavioural Finance," Finance 0503028, University Library of Munich, Germany, revised 23 Jul 2005.
    4. Miguel A. Lejeune, 2012. "Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems," Operations Research, INFORMS, vol. 60(6), pages 1356-1372, December.
    5. 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.
    6. L. Jeff Hong & Zhiyuan Huang & Henry Lam, 2021. "Learning-Based Robust Optimization: Procedures and Statistical Guarantees," Management Science, INFORMS, vol. 67(6), pages 3447-3467, June.
    7. Trabelsi, Mohamed Ali, 2010. "Choix de portefeuille: comparaison des différentes stratégies [Portfolio selection: comparison of different strategies]," MPRA Paper 82946, University Library of Munich, Germany, revised 01 Dec 2010.
    8. Miguel Lejeune, 2012. "Pattern definition of the p-efficiency concept," Annals of Operations Research, Springer, vol. 200(1), pages 23-36, November.
    9. T.J. Flavin & M.R. Wickens, 2003. "Macroeconomic influences on optimal asset allocation," Review of Financial Economics, John Wiley & Sons, vol. 12(2), pages 207-231.
    10. Zura Kakushadze & Willie Yu, 2016. "Multifactor Risk Models and Heterotic CAPM," Papers 1602.04902, arXiv.org, revised Mar 2016.
    11. Frankfurter, George M. & Phillips, Herbert E., 1996. "Normative implications of equilibrium models: Homogeneous expectations and other artificialities," Journal of Economic Behavior & Organization, Elsevier, vol. 31(1), pages 67-83, October.
    12. Los, Cornelis A., 1999. "Galton's Error and the under-representation of systematic risk," Journal of Banking & Finance, Elsevier, vol. 23(12), pages 1793-1829, December.
    13. Tóth, M. & Lančarič, D. & Piterková, A. & Savov, R., 2014. "Systematic Risk in Agriculture: A Case of Slovakia," AGRIS on-line Papers in Economics and Informatics, Czech University of Life Sciences Prague, Faculty of Economics and Management, vol. 6(4), pages 1-9, December.
    14. Yan, Cheng & Zhang, Huazhu, 2017. "Mean-variance versus naïve diversification: The role of mispricing," Journal of International Financial Markets, Institutions and Money, Elsevier, vol. 48(C), pages 61-81.
    15. 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.
    16. James W. Kolari & Jianhua Z. Huang & Wei Liu & Huiling Liao, 2022. "Further Tests of the ZCAPM Asset Pricing Model," JRFM, MDPI, vol. 15(3), pages 1-23, March.
    17. İhsan Yanıkoğlu & Dick den Hertog, 2013. "Safe Approximations of Ambiguous Chance Constraints Using Historical Data," INFORMS Journal on Computing, INFORMS, vol. 25(4), pages 666-681, November.
    18. John B. Guerard, 2024. "Sir David Hendry: An Appreciation from Wall Street and What Macroeconomics Got Right," Working Papers 2024-001, The George Washington University, Department of Economics, H. O. Stekler Research Program on Forecasting, revised Feb 2024.
    19. M. Ariff & Vijaya B. Marisetty, 2012. "Panel data approach to identify factors correlated with equity market risk premiums in developed and emerging markets," Quantitative Finance, Taylor & Francis Journals, vol. 12(1), pages 107-118, April.
    20. Dimson, Elroy & Mussavian, Massoud, 1999. "Three centuries of asset pricing," Journal of Banking & Finance, Elsevier, vol. 23(12), pages 1745-1769, December.

    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:260:y:2017:i:2:p:421-431. 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.