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

Parametric mixed-integer 0-1 linear programming: The general case for a single parameter

Author

Listed:
  • Mitsos, Alexander
  • Barton, Paul I.

Abstract

Two algorithms for the general case of parametric mixed-integer linear programs (MILPs) are proposed. Parametric MILPs are considered in which a single parameter can simultaneously influence the objective function, the right-hand side and the matrix. The first algorithm is based on branch-and-bound on the integer variables, solving a parametric linear program (LP) at each node. The second algorithm is based on the optimality range of a qualitatively invariant solution, decomposing the parametric optimization problem into a series of regular MILPs, parametric LPs and regular mixed-integer nonlinear programs (MINLPs). The number of subproblems required for a particular instance is equal to the number of critical regions. For the parametric LPs an improvement of the well-known rational simplex algorithm is presented, that requires less consecutive operations on rational functions. Also, an alternative based on predictor-corrector continuation is proposed. Numerical results for a test set are discussed.

Suggested Citation

  • Mitsos, Alexander & Barton, Paul I., 2009. "Parametric mixed-integer 0-1 linear programming: The general case for a single parameter," European Journal of Operational Research, Elsevier, vol. 194(3), pages 663-686, May.
    • Handle: RePEc:eee:ejores:v:194:y:2009:i:3:p:663-686
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00133-1
    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. Crema, Alejandro, 1998. "A procedure to verify the completeness of the right-hand-side parametric analysis for a mixed integer linear programming problem," European Journal of Operational Research, Elsevier, vol. 108(3), pages 684-695, August.
    2. Harvey J. Greenberg, 1999. "Matrix Sensitivity Analysis from an Interior Solution of a Linear Program," INFORMS Journal on Computing, INFORMS, vol. 11(3), pages 316-327, August.
    3. Vivek Dua & Efstratios Pistikopoulos, 2000. "An Algorithm for the Solution of Multiparametric Mixed Integer Linear Programming Problems," Annals of Operations Research, Springer, vol. 99(1), pages 123-139, December.
    4. Stein W. Wallace, 2000. "Decision Making Under Uncertainty: Is Sensitivity Analysis of Any Use?," Operations Research, INFORMS, vol. 48(1), pages 20-25, February.
    5. Larry Jenkins, 1982. "Parametric Mixed Integer Programming: An Application to Solid Waste Management," Management Science, INFORMS, vol. 28(11), pages 1270-1284, November.
    6. A. M. Geoffrion & R. Nauss, 1977. "Exceptional Paper--Parametric and Postoptimality Analysis in Integer Linear Programming," Management Science, INFORMS, vol. 23(5), pages 453-466, January.
    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. 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.
    2. Richard Oberdieck & Martina Wittmann-Hohlbein & Efstratios Pistikopoulos, 2014. "A branch and bound method for the solution of multiparametric mixed integer linear programming problems," Journal of Global Optimization, Springer, vol. 59(2), pages 527-543, July.
    3. Cristina Bazgan & Arne Herzel & Stefan Ruzika & Clemens Thielen & Daniel Vanderpooten, 2022. "An approximation algorithm for a general class of parametric optimization problems," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1328-1358, July.
    4. 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.

    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. 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.
    2. Mukherjee, Saral & Chatterjee, A.K., 2006. "The average shadow price for MILPs with integral resource availability and its relationship to the marginal unit shadow price," European Journal of Operational Research, Elsevier, vol. 169(1), pages 53-64, February.
    3. Crema, Alejandro, 2002. "An algorithm to perform a complete parametric analysis relative to the constraint matrix for a 0-1-integer linear program," European Journal of Operational Research, Elsevier, vol. 138(3), pages 484-494, May.
    4. Li, Lei & Zabinsky, Zelda B., 2011. "Incorporating uncertainty into a supplier selection problem," International Journal of Production Economics, Elsevier, vol. 134(2), pages 344-356, December.
    5. Jenkins, Larry, 1996. "A comment on "Grey integer programming: an application to waste management planning under uncertainty" by Guo H. Huang, Brian W. Baetz, Gilles G. Patry : European Journal of Operational Rese," European Journal of Operational Research, Elsevier, vol. 89(3), pages 671-670, March.
    6. Crema, Alejandro, 1998. "A procedure to verify the completeness of the right-hand-side parametric analysis for a mixed integer linear programming problem," European Journal of Operational Research, Elsevier, vol. 108(3), pages 684-695, August.
    7. Tcha, Dong-wan & Myung, Young-soo & Chung, Ki-ho, 1995. "Parametric uncapacitated facility location," European Journal of Operational Research, Elsevier, vol. 86(3), pages 469-479, November.
    8. Wang, Hsiao-Fan & Horng, Jyh-Shing, 1996. "Structural approach to parametric analysis of an IP on the case of the right-hand side," European Journal of Operational Research, Elsevier, vol. 92(1), pages 148-156, July.
    9. Huang, G. H. & Baetz, B. W. & Patry, G. G., 1997. "A response to "A comment on 'Grey integer programming: An application to waste management planning under uncertainty"' by Larry Jenkins," European Journal of Operational Research, Elsevier, vol. 100(3), pages 638-641, August.
    10. Crema, Alejandro, 2002. "The multiparametric 0-1-integer linear programming problem: A unified approach," European Journal of Operational Research, Elsevier, vol. 139(3), pages 511-520, June.
    11. Crema, Alejandro, 2000. "An algorithm for the multiparametric 0-1-integer linear programming problem relative to the objective function," European Journal of Operational Research, Elsevier, vol. 125(1), pages 18-24, August.
    12. Myung, Young-Soo & Kim, Hu-gon & Tcha, Dong-wan, 1997. "A bi-objective uncapacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 100(3), pages 608-616, August.
    13. Xin Wang & Stein W. Wallace, 2016. "Stochastic scheduled service network design in the presence of a spot market for excess capacity," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 5(4), pages 393-413, December.
    14. Baker, Erin & Bosetti, Valentina & Salo, Ahti, 2016. "Finding Common Ground when Experts Disagree: Belief Dominance over Portfolios of Alternatives," MITP: Mitigation, Innovation and Transformation Pathways 243147, Fondazione Eni Enrico Mattei (FEEM).
    15. Zukui Li & Marianthi Ierapetritou, 2010. "A method for solving the general parametric linear complementarity problem," Annals of Operations Research, Springer, vol. 181(1), pages 485-501, December.
    16. Lars M. Hvattum & Arne Løkketangen & Gilbert Laporte, 2006. "Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic," Transportation Science, INFORMS, vol. 40(4), pages 421-438, November.
    17. Bergen, Matías & Muñoz, Francisco D., 2018. "Quantifying the effects of uncertain climate and environmental policies on investments and carbon emissions: A case study of Chile," Energy Economics, Elsevier, vol. 75(C), pages 261-273.
    18. 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.
    19. Yifei Zhao & Stein W. Wallace, 2014. "Integrated Facility Layout Design and Flow Assignment Problem Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 798-808, November.
    20. Erin Baker & Valentina Bosetti & Ahti Salo, 2017. "Finding common ground when experts disagree: Robust portfolio decision analysis," Working Papers 2017/11, Institut d'Economia de Barcelona (IEB).

    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:194:y:2009:i:3:p:663-686. 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.