IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v56y2013i2p343-368.html
   My bibliography  Save this article

Implementing the simplex method as a cutting-plane method, with a view to regularization

Author

Listed:
  • Csaba Fábián
  • Olga Papp
  • Krisztián Eretnek

Abstract

We show that the simplex method can be interpreted as a cutting-plane method, assuming that a special pricing rule is used. This approach is motivated by the recent success of the cutting-plane method in the solution of special stochastic programming problems. We focus on the special linear programming problem of finding the largest ball that fits into a given polyhedron. In a computational study we demonstrate that ball-fitting problems have such special characteristics which indicate their utility in regularization schemes. Copyright Springer Science+Business Media New York 2013

Suggested Citation

  • Csaba Fábián & Olga Papp & Krisztián Eretnek, 2013. "Implementing the simplex method as a cutting-plane method, with a view to regularization," Computational Optimization and Applications, Springer, vol. 56(2), pages 343-368, October.
    • Handle: RePEc:spr:coopap:v:56:y:2013:i:2:p:343-368
    DOI: 10.1007/s10589-013-9562-7
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-013-9562-7
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-013-9562-7?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. Mohammad R. Oskoorouchi & Hamid R. Ghaffari & Tamás Terlaky & Dionne M. Aleman, 2011. "An Interior Point Constraint Generation Algorithm for Semi-Infinite Optimization with Health-Care Application," Operations Research, INFORMS, vol. 59(5), pages 1184-1197, October.
    2. Peter Kall & János Mayer, 2005. "Stochastic Linear Programming," International Series in Operations Research and Management Science, Springer, number 978-0-387-24440-2, December.
    3. Alexandra Künzi-Bay & János Mayer, 2006. "Computational aspects of minimizing conditional value-at-risk," Computational Management Science, Springer, vol. 3(1), pages 3-27, January.
    4. Willem Haneveld & Maarten Vlerk, 2006. "Integrated Chance Constraints: Reduced Forms and an Algorithm," Computational Management Science, Springer, vol. 3(4), pages 245-269, September.
    5. István Maros, 2003. "A General Pricing Scheme for the Simplex Method," Annals of Operations Research, Springer, vol. 124(1), pages 193-203, November.
    6. Maros, Istvan, 2003. "A generalized dual phase-2 simplex algorithm," European Journal of Operational Research, Elsevier, vol. 149(1), pages 1-16, August.
    7. J. L. Goffin & A. Haurie & J. P. Vial, 1992. "Decomposition and Nondifferentiable Optimization with the Projective Algorithm," Management Science, INFORMS, vol. 38(2), pages 284-302, February.
    8. Robert E. Bixby, 2002. "Solving Real-World Linear Programs: A Decade and More of Progress," Operations Research, INFORMS, vol. 50(1), pages 3-15, February.
    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. Csaba Fábián & Krisztián Eretnek & Olga Papp, 2015. "A regularized simplex method," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(4), pages 877-898, December.

    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. Dirk Lorenz & Marc Pfetsch & Andreas Tillmann, 2014. "An infeasible-point subgradient method using adaptive approximate projections," Computational Optimization and Applications, Springer, vol. 57(2), pages 271-306, March.
    2. Juan Ma & Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Vladimir Boginski, 2016. "The Minimum Spanning k -Core Problem with Bounded CVaR Under Probabilistic Edge Failures," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 295-307, May.
    3. Ken Kobayashi & Yuichi Takano & Kazuhide Nakata, 2021. "Bilevel cutting-plane algorithm for cardinality-constrained mean-CVaR portfolio optimization," Journal of Global Optimization, Springer, vol. 81(2), pages 493-528, October.
    4. Fang, Yi & Post, Thierry, 2022. "Optimal portfolio choice for higher-order risk averters," Journal of Banking & Finance, Elsevier, vol. 137(C).
    5. Pu Huang & Dharmashankar Subramanian, 2012. "Iterative estimation maximization for stochastic linear programs with conditional value-at-risk constraints," Computational Management Science, Springer, vol. 9(4), pages 441-458, November.
    6. Berend Roorda, 2010. "An algorithm for sequential tail value at risk for path-independent payoffs in a binomial tree," Annals of Operations Research, Springer, vol. 181(1), pages 463-483, December.
    7. Willem Klein Haneveld & Matthijs Streutker & Maarten Vlerk, 2010. "An ALM model for pension funds using integrated chance constraints," Annals of Operations Research, Springer, vol. 177(1), pages 47-62, June.
    8. Elçi, Özgün & Noyan, Nilay, 2018. "A chance-constrained two-stage stochastic programming model for humanitarian relief network design," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 55-83.
    9. Daniel Espinoza & Eduardo Moreno, 2014. "A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs," Computational Optimization and Applications, Springer, vol. 59(3), pages 617-638, December.
    10. Fábián, Csaba I., 2008. "Handling CVaR objectives and constraints in two-stage stochastic models," European Journal of Operational Research, Elsevier, vol. 191(3), pages 888-911, December.
    11. Foad Mahdavi Pajouh & Esmaeel Moradi & Balabhaskar Balasundaram, 2017. "Detecting large risk-averse 2-clubs in graphs with random edge failures," Annals of Operations Research, Springer, vol. 249(1), pages 55-73, February.
    12. Maciej Rysz & Alexander Vinel & Pavlo Krokhmal & Eduardo L. Pasiliao, 2015. "A Scenario Decomposition Algorithm for Stochastic Programming Problems with a Class of Downside Risk Measures," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 416-430, May.
    13. Thiago Serra & Ryan J. O’Neil, 2020. "MIPLIBing: Seamless Benchmarking of Mathematical Optimization Problems and Metadata Extensions," SN Operations Research Forum, Springer, vol. 1(3), pages 1-6, September.
    14. Bach, Lukas & Hasle, Geir & Schulz, Christian, 2019. "Adaptive Large Neighborhood Search on the Graphics Processing Unit," European Journal of Operational Research, Elsevier, vol. 275(1), pages 53-66.
    15. Júlíus Atlason & Marina A. Epelman & Shane G. Henderson, 2008. "Optimizing Call Center Staffing Using Simulation and Analytic Center Cutting-Plane Methods," Management Science, INFORMS, vol. 54(2), pages 295-309, February.
    16. Roman, Diana & Mitra, Gautam & Zverovich, Victor, 2013. "Enhanced indexation based on second-order stochastic dominance," European Journal of Operational Research, Elsevier, vol. 228(1), pages 273-281.
    17. D. Kuhn, 2009. "Convergent Bounds for Stochastic Programs with Expected Value Constraints," Journal of Optimization Theory and Applications, Springer, vol. 141(3), pages 597-618, June.
    18. Kolos Ágoston, 2012. "CVaR minimization by the SRA algorithm," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 20(4), pages 623-632, December.
    19. Cristiano Arbex Valle & John E Beasley & Nigel Meade, 2024. "Subset second-order stochastic dominance for enhanced indexation with diversification enforced by sector constraints," Papers 2404.16777, arXiv.org, revised Nov 2024.
    20. Ole Bent Olesen & Niels Christian Petersen & Victor V. Podinovski, 2022. "Scale characteristics of variable returns-to-scale production technologies with ratio inputs and outputs," Annals of Operations Research, Springer, vol. 318(1), pages 383-423, November.

    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:56:y:2013:i:2:p:343-368. 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.