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. Stein W. Wallace, 2000. "Decision Making Under Uncertainty: Is Sensitivity Analysis of Any Use?," Operations Research, INFORMS, vol. 48(1), pages 20-25, February.
    3. 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.
    4. 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.
    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. 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.
    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. 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. 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. 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. 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.

    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. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    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. 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).
    14. 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.
    15. 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.
    16. Crema, Alejandro, 1995. "Average shadow price in a mixed integer linear programming problem," European Journal of Operational Research, Elsevier, vol. 85(3), pages 625-635, September.
    17. Jonathan D Linton & Julian Scott Yeomans & Reena Yoogalingam, 2002. "Policy Planning Using Genetic Algorithms Combined with Simulation: The Case of Municipal Solid Waste," Environment and Planning B, , vol. 29(5), pages 757-778, October.
    18. van Riessen, B. & Negenborn, R.R. & Dekker, R., 2016. "Real-time Container Transport Planning with Decision Trees based on Offline Obtained Optimal Solutions," Econometric Institute Research Papers EI2016-14, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    19. Thapalia, Biju K. & Crainic, Teodor Gabriel & Kaut, Michal & Wallace, Stein W., 2012. "Single-commodity network design with random edge capacities," European Journal of Operational Research, Elsevier, vol. 220(2), pages 394-403.
    20. Shuming Wang & Tsan Sheng Ng & Manyu Wong, 2016. "Expansion planning for waste‐to‐energy systems using waste forecast prediction sets," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(1), pages 47-70, February.

    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.