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

Multiparametric linear programming: Support set and optimal partition invariancy

Author

Listed:
  • Hladík, Milan

Abstract

Traditional sensitivity and parametric analysis in linear optimization was based on preserving optimal basis. Interior point methods, however, do not converge to a basic solution (vertex) in general. Recently, there appeared new techniques in sensitivity analysis, which consist in preserving so called support set invariancy and optimal partition invariancy. This paper reflects the renascence of sensitivity and parametric analysis and extends single-parametric results to the case when there are multiple parameters in the objective function and in the right-hand side of equations. Multiparametric approach enables us to study more complex perturbation occurring in linear programs than the simpler sensitivity analysis does. We present a description of the set of admissible parameters under the mentioned invariances, and compare them with the classical optimal basis concept.

Suggested Citation

  • Hladík, Milan, 2010. "Multiparametric linear programming: Support set and optimal partition invariancy," European Journal of Operational Research, Elsevier, vol. 202(1), pages 25-31, April.
    • Handle: RePEc:eee:ejores:v:202:y:2010:i:1:p:25-31
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00292-6
    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. Hadigheh, Alireza Ghaffari & Terlaky, Tamas, 2006. "Sensitivity analysis in linear optimization: Invariant support set intervals," European Journal of Operational Research, Elsevier, vol. 169(3), pages 1158-1175, March.
    2. Jansen, B. & de Jong, J. J. & Roos, C. & Terlaky, T., 1997. "Sensitivity analysis in linear programming: just be careful!," European Journal of Operational Research, Elsevier, vol. 101(1), pages 15-28, August.
    3. Richard E. Wendell, 2004. "Tolerance Sensitivity and Optimality Bounds in Linear Programming," Management Science, INFORMS, vol. 50(6), pages 797-803, June.
    4. F. Borrelli & A. Bemporad & M. Morari, 2003. "Geometric Algorithm for Multiparametric Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 118(3), pages 515-540, September.
    5. Alireza Ghaffari-Hadigheh & Habib Ghaffari-Hadigheh & Tamás Terlaky, 2008. "Bi-parametric optimal partition invariancy sensitivity analysis in linear optimization," 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. 16(2), pages 215-238, June.
    6. C. Filippi, 2004. "An Algorithm for Approximate Multiparametric Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 120(1), pages 73-95, January.
    7. A. Ghaffari Hadigheh & K. Mirnia & T. Terlaky, 2007. "Active Constraint Set Invariancy Sensitivity Analysis in Linear Optimization," Journal of Optimization Theory and Applications, Springer, vol. 133(3), pages 303-315, June.
    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. Hladík, Milan & Sitarz, Sebastian, 2013. "Maximal and supremal tolerances in multiobjective linear programming," European Journal of Operational Research, Elsevier, vol. 228(1), pages 93-101.
    2. Ma, Kang-Ting & Lin, Chi-Jen & Wen, Ue-Pyng, 2013. "Type II sensitivity analysis of cost coefficients in the degenerate transportation problem," European Journal of Operational Research, Elsevier, vol. 227(2), pages 293-300.
    3. Borgonovo, Emanuele & Buzzard, Gregery T. & Wendell, Richard E., 2018. "A global tolerance approach to sensitivity analysis in linear programming," European Journal of Operational Research, Elsevier, vol. 267(1), pages 321-337.

    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. Ma, Kang-Ting & Lin, Chi-Jen & Wen, Ue-Pyng, 2013. "Type II sensitivity analysis of cost coefficients in the degenerate transportation problem," European Journal of Operational Research, Elsevier, vol. 227(2), pages 293-300.
    2. Curry, Stewart & Lee, Ilbin & Ma, Simin & Serban, Nicoleta, 2022. "Global sensitivity analysis via a statistical tolerance approach," European Journal of Operational Research, Elsevier, vol. 296(1), pages 44-59.
    3. Iosif Pappas & Nikolaos A. Diangelakis & Efstratios N. Pistikopoulos, 2021. "The exact solution of multiparametric quadratically constrained quadratic programming problems," Journal of Global Optimization, Springer, vol. 79(1), pages 59-85, January.
    4. A. Ghaffari Hadigheh & K. Mirnia & T. Terlaky, 2007. "Active Constraint Set Invariancy Sensitivity Analysis in Linear Optimization," Journal of Optimization Theory and Applications, Springer, vol. 133(3), pages 303-315, June.
    5. Martina Wittmann-Hohlbein & Efstratios Pistikopoulos, 2013. "On the global solution of multi-parametric mixed integer linear programming problems," Journal of Global Optimization, Springer, vol. 57(1), pages 51-73, September.
    6. Efstratios Pistikopoulos & Luis Dominguez & Christos Panos & Konstantinos Kouramas & Altannar Chinchuluun, 2012. "Theoretical and algorithmic advances in multi-parametric programming and control," Computational Management Science, Springer, vol. 9(2), pages 183-203, May.
    7. Koltai, Tamás & Tatay, Viola, 2011. "A practical approach to sensitivity analysis in linear programming under degeneracy for management decision making," International Journal of Production Economics, Elsevier, vol. 131(1), pages 392-398, May.
    8. M. A. Goberna & T. Terlaky & M. I. Todorov, 2010. "Sensitivity Analysis in Linear Semi-Infinite Programming via Partitions," Mathematics of Operations Research, INFORMS, vol. 35(1), pages 14-26, February.
    9. Goberna, M.A. & Gomez, S. & Guerra, F. & Todorov, M.I., 2007. "Sensitivity analysis in linear semi-infinite programming: Perturbing cost and right-hand-side coefficients," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1069-1085, September.
    10. Kavitha K. & Pandian ponnaiah, 2012. "Type II Sensitivity Analysis in Solid Assignment Problems," Modern Applied Science, Canadian Center of Science and Education, vol. 6(12), pages 1-22, December.
    11. Illes, Tibor & Terlaky, Tamas, 2002. "Pivot versus interior point methods: Pros and cons," European Journal of Operational Research, Elsevier, vol. 140(2), pages 170-190, July.
    12. Ehsan Salari & H. Edwin Romeijn, 2012. "Quantifying the Trade-off Between IMRT Treatment Plan Quality and Delivery Efficiency Using Direct Aperture Optimization," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 518-533, November.
    13. Borgonovo, E., 2010. "Sensitivity analysis with finite changes: An application to modified EOQ models," European Journal of Operational Research, Elsevier, vol. 200(1), pages 127-138, January.
    14. Scott E. Sampson, 2008. "OR PRACTICE---Optimization of Vacation Timeshare Scheduling," Operations Research, INFORMS, vol. 56(5), pages 1079-1088, October.
    15. Xuefei Lu & Alessandro Rudi & Emanuele Borgonovo & Lorenzo Rosasco, 2020. "Faster Kriging: Facing High-Dimensional Simulators," Operations Research, INFORMS, vol. 68(1), pages 233-249, January.
    16. Terlaky, Tamas, 2001. "An easy way to teach interior-point methods," European Journal of Operational Research, Elsevier, vol. 130(1), pages 1-19, April.
    17. J. Spjøtvold & P. Tøndel & T. A. Johansen, 2007. "Continuous Selection and Unique Polyhedral Representation of Solutions to Convex Parametric Quadratic Programs," Journal of Optimization Theory and Applications, Springer, vol. 134(2), pages 177-189, August.
    18. Georgios Saharidis & Marianthi Ierapetritou, 2013. "Speed-up Benders decomposition using maximum density cut (MDC) generation," Annals of Operations Research, Springer, vol. 210(1), pages 101-123, November.
    19. Hadigheh, Alireza Ghaffari & Terlaky, Tamas, 2006. "Sensitivity analysis in linear optimization: Invariant support set intervals," European Journal of Operational Research, Elsevier, vol. 169(3), pages 1158-1175, March.
    20. E. A. Yıldırım, 2003. "An Interior-Point Perspective on Sensitivity Analysis in Semidefinite Programming," Mathematics of Operations Research, INFORMS, vol. 28(4), pages 649-676, 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:eee:ejores:v:202:y:2010:i:1:p:25-31. 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.