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

Mathematical programming approaches for generating p-efficient points

Author

Listed:
  • Lejeune, Miguel
  • Noyan, Nilay

Abstract

Probabilistically constrained problems, in which the random variables are finitely distributed, are non-convex in general and hard to solve. The p-efficiency concept has been widely used to develop efficient methods to solve such problems. Those methods require the generation of p-efficient points (pLEPs) and use an enumeration scheme to identify pLEPs. In this paper, we consider a random vector characterized by a finite set of scenarios and generate pLEPs by solving a mixed-integer programming (MIP) problem. We solve this computationally challenging MIP problem with a new mathematical programming framework. It involves solving a series of increasingly tighter outer approximations and employs, as algorithmic techniques, a bundle preprocessing method, strengthening valid inequalities, and a fixing strategy. The method is exact (resp., heuristic) and ensures the generation of pLEPs (resp., quasi pLEPs) if the fixing strategy is not (resp., is) employed, and it can be used to generate multiple pLEPs. To the best of our knowledge, generating a set of pLEPs using an optimization-based approach and developing effective methods for the application of the p-efficiency concept to the random variables described by a finite set of scenarios are novel. We present extensive numerical results that highlight the computational efficiency and effectiveness of the overall framework and of each of the specific algorithmic techniques.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:207:y:2010:i:2:p:590-600
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00381-4
    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. Darinka Dentcheva & Bogumila Lai & Andrzej Ruszczyński, 2004. "Dual methods for probabilistic optimization problems ," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 60(2), pages 331-346, October.
    2. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    3. 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.
    4. 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.
    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. Miguel A. Lejeune, 2012. "Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems," Operations Research, INFORMS, vol. 60(6), pages 1356-1372, December.
    2. 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.
    3. Edmonds, Lawryn & Derby, Melanie & Hill, Mary & Wu, Hongyu, 2021. "Coordinated operation of water and electricity distribution networks with variable renewable energy and distribution locational marginal pricing," Renewable Energy, Elsevier, vol. 177(C), pages 1438-1450.
    4. Lukáš Adam & Martin Branda & Holger Heitsch & René Henrion, 2020. "Solving joint chance constrained problems using regularization and Benders’ decomposition," Annals of Operations Research, Springer, vol. 292(2), pages 683-709, September.
    5. Darinka Dentcheva & Gabriela Martinez, 2012. "Augmented Lagrangian method for probabilistic optimization," Annals of Operations Research, Springer, vol. 200(1), pages 109-130, November.
    6. 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.
    7. Lejeune, Miguel A., 2013. "Probabilistic modeling of multiperiod service levels," European Journal of Operational Research, Elsevier, vol. 230(2), pages 299-312.
    8. András Prékopa & Merve Unuvar, 2015. "Single Commodity Stochastic Network Design Under Probabilistic Constraint with Discrete Random Variables," Operations Research, INFORMS, vol. 63(6), pages 1512-1527, December.
    9. Miguel Lejeune, 2012. "Pattern definition of the p-efficiency concept," Annals of Operations Research, Springer, vol. 200(1), pages 23-36, November.
    10. 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.
    11. Faqiry, M. Nazif & Edmonds, Lawryn & Wu, Hongyu & Pahwa, Anil, 2020. "Distribution locational marginal price-based transactive day-ahead market with variable renewable generation," Applied Energy, Elsevier, vol. 259(C).

    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. Miguel Lejeune, 2012. "Pattern definition of the p-efficiency concept," Annals of Operations Research, Springer, vol. 200(1), pages 23-36, November.
    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. 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.
    4. 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.
    5. Escudero, Laureano F. & Garín, M. Araceli & Monge, Juan F. & Unzueta, Aitziber, 2020. "Some matheuristic algorithms for multistage stochastic optimization models with endogenous uncertainty and risk management," European Journal of Operational Research, Elsevier, vol. 285(3), pages 988-1001.
    6. 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.
    7. Cooper, W. W. & Hemphill, H. & Huang, Z. & Li, S. & Lelas, V. & Sullivan, D. W., 1997. "Survey of mathematical programming models in air pollution management," European Journal of Operational Research, Elsevier, vol. 96(1), pages 1-35, January.
    8. 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.
    9. M. C. Campi & S. Garatti, 2011. "A Sampling-and-Discarding Approach to Chance-Constrained Optimization: Feasibility and Optimality," Journal of Optimization Theory and Applications, Springer, vol. 148(2), pages 257-280, February.
    10. 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.
    11. L. Jeff Hong & Yi Yang & Liwei Zhang, 2011. "Sequential Convex Approximations to Joint Chance Constrained Programs: A Monte Carlo Approach," Operations Research, INFORMS, vol. 59(3), pages 617-630, June.
    12. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    13. Hang Li & Zhe Zhang & Xianggen Yin & Buhan Zhang, 2020. "Preventive Security-Constrained Optimal Power Flow with Probabilistic Guarantees," Energies, MDPI, vol. 13(9), pages 1-13, May.
    14. René Henrion & Andris Möller, 2012. "A Gradient Formula for Linear Chance Constraints Under Gaussian Distribution," Mathematics of Operations Research, INFORMS, vol. 37(3), pages 475-488, August.
    15. Wu, Dexiang & Wu, Desheng Dash, 2020. "A decision support approach for two-stage multi-objective index tracking using improved lagrangian decomposition," Omega, Elsevier, vol. 91(C).
    16. Fan, Yingjie & Schwartz, Frank & Voß, Stefan, 2017. "Flexible supply chain planning based on variable transportation modes," International Journal of Production Economics, Elsevier, vol. 183(PC), pages 654-666.
    17. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    18. Glover, Fred & Sueyoshi, Toshiyuki, 2009. "Contributions of Professor William W. Cooper in Operations Research and Management Science," European Journal of Operational Research, Elsevier, vol. 197(1), pages 1-16, August.
    19. Andreatta, Giovanni & Dell'Olmo, Paolo & Lulli, Guglielmo, 2011. "An aggregate stochastic programming model for air traffic flow management," European Journal of Operational Research, Elsevier, vol. 215(3), pages 697-704, December.
    20. Huang, Edward & Mital, Pratik & Goetschalckx, Marc & Wu, Kan, 2016. "Optimal assignment of airport baggage unloading zones to outgoing flights," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 110-122.

    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:2:p:590-600. 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.