IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v48y2000i4p623-634.html
   My bibliography  Save this article

Inference-Based Sensitivity Analysis for Mixed Integer/Linear Programming

Author

Listed:
  • M. W. Dawande

    (IBM, T. J. Watson Research Center, Yorktown Heights, New York 10598)

  • J. N. Hooker

    (Carnegie Mellon University, Pittsburgh, Pennsylvania 15213)

Abstract

A new method of sensitivity analysis for mixed integer/linear programming (MILP) is derived from the idea of inference duality. The inference dual of an optimization problem asks how the optimal value can be deduced from the constraints. In MILP, a deduction based on the resolution method oftheorem proving can be obtained from the branch-and-cut tree that solves the primal problem. One can then investigate which perturbations ofthe problem leave this proof intact. On this basis it is shown that, in a minimization problem, any perturbation that satisfies a certain system of linear inequalities will reduce the optimal value no more than a prespecified amount. One can also give an upper bound on the increase in the optimal value that results from a given perturbation. The method is illustrated on two realistic problems.

Suggested Citation

  • M. W. Dawande & J. N. Hooker, 2000. "Inference-Based Sensitivity Analysis for Mixed Integer/Linear Programming," Operations Research, INFORMS, vol. 48(4), pages 623-634, August.
    • Handle: RePEc:inm:oropre:v:48:y:2000:i:4:p:623-634
    DOI: 10.1287/opre.48.4.623.12420
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.48.4.623.12420
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.48.4.623.12420?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
    ---><---

    References listed on IDEAS

    as
    1. TIND, Jorgen & WOLSEY, Laurence A., 1981. "An elementary survey of general duality theory in mathematical programming," LIDAM Reprints CORE 474, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. WOLSEY, Laurence A., 1981. "Integer programming duality: price functions and sensitivity analysis," LIDAM Reprints CORE 431, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. L. F. G. De Cazaux, 1965. "On The Budget," Journal of Accounting Research, Wiley Blackwell, vol. 3(2), pages 264-265.
    4. WOLSEY, Laurence A., 1981. "The b-hull of an integer program," LIDAM Reprints CORE 446, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Linus Schrage & Laurence Wolsey, 1985. "Sensitivity Analysis for Branch and Bound Integer Programming," Operations Research, INFORMS, vol. 33(5), pages 1008-1023, October.
    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. Onur Tavaslıoğlu & Oleg A. Prokopyev & Andrew J. Schaefer, 2019. "Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function," Operations Research, INFORMS, vol. 67(6), pages 1659-1677, November.
    2. Gerdus Benadè & John N. Hooker, 2020. "Optimization Bounds from the Branching Dual," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 3-15, January.
    3. Michael A. Trick & Hakan Yildiz, 2011. "Benders' cuts guided large neighborhood search for the traveling umpire problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(8), pages 771-781, 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. Amitabh Basu & Kipp Martin & Christopher Thomas Ryan & Guanyi Wang, 2019. "Mixed-Integer Linear Representability, Disjunctions, and Chvátal Functions—Modeling Implications," Management Science, INFORMS, vol. 44(4), pages 1264-1285, November.
    2. Onur Tavaslıoğlu & Oleg A. Prokopyev & Andrew J. Schaefer, 2019. "Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function," Operations Research, INFORMS, vol. 67(6), pages 1659-1677, November.
    3. Aynur Pala, 2014. "The Effect of Valuation Ratios, Gold Price, and Petroleum Price on Equity Returns: A Comparison of Static Panel and Quantile Regressions," Asian Economic and Financial Review, Asian Economic and Social Society, vol. 4(1), pages 80-89, January.
    4. Stephanie Bell, 1999. "Functional Finance: What, Why, and How?," Economics Working Paper Archive wp_287, Levy Economics Institute.
    5. Bautista, M. A. & González, F. & Martínez, L. R. & Muñoz, P. & Prem, M., 2020. "Chile’s Missing Students: Dictatorship, Higher Education and Social Mobility," Documentos de Trabajo 18163, Universidad del Rosario.
    6. Lindemann, Henrik, 2015. "Regulatory Objectives and the Intensity of Unbundling in Electricity Markets," Hannover Economic Papers (HEP) dp-544, Leibniz Universität Hannover, Wirtschaftswissenschaftliche Fakultät.
    7. Jorge Núñez Ferrer & Jacques Le Cacheux & Giacomo Benedetto & Mathieu Saunier & Fabien Candau & Claude Emonnot & Florence Lachet-Touya & Jorgen Mortensen & Aymeric Potteau & Igor Taranic, 2016. "Study on the potential and limitations of reforming the financing of the EU budget [Perspectives et limites pour réformer le financement du budget de l’UE]," Working Papers hal-01848029, HAL.
    8. Marcel, Mario, 2001. "Balance Estructural del Gobierno Central. Metodología y Estimaciones para Chile [Structural Bazlance of Central Government. Methodology and estimates for Chile]," MPRA Paper 43338, University Library of Munich, Germany.
    9. Leandros, Panayota, 1997. "The Greek Economy and European Integration," MPRA Paper 93279, University Library of Munich, Germany.
    10. Yasuo Kofuji, 1984. "On the Efficacy of Fiscal Policy and Price Level Changes," Public Finance Review, , vol. 12(2), pages 167-181, April.
    11. Csillag, István, 2001. "Költségvetési összhangzattan. Diktatúrából a demokráciába? [Budgetary harmony. From dictatorship to democracy?]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(10), pages 824-843.
    12. R.C. Fordham, 1975. "Urban Land Use Change in the United Kingdom during the Second Half of the Twentieth Century," Urban Studies, Urban Studies Journal Limited, vol. 12(1), pages 71-84, February.
    13. Ponticelli, Jacopo & Voth, Hans-Joachim, 2020. "Austerity and anarchy: Budget cuts and social unrest in Europe, 1919–2008," Journal of Comparative Economics, Elsevier, vol. 48(1), pages 1-19.
    14. Willem H. Buiter, 1986. "Fiscal Prerequisites for a Viable Managed Exchange Rate Regime: A Non-technical Eclectic Introduction," NBER Working Papers 2041, National Bureau of Economic Research, Inc.
    15. Warren, Cline J. & Santmyer, Carolee, 1965. "Agriculture of Northern Africa," Miscellaneous Publications 316359, United States Department of Agriculture, Economic Research Service.
    16. Stephen J. Turnovsky, 2019. "Trends and fads in macroeconomic dynamics," Indian Economic Review, Springer, vol. 54(1), pages 179-197, December.
    17. Gordon Tang & Wai Cheong Shum, 2006. "Risk-return relationships in the Hong Kong stock market: revisit," Applied Financial Economics, Taylor & Francis Journals, vol. 16(14), pages 1047-1058.
    18. Gardner, B. Delworth & Abdou, Dyaa, 1982. "Food Consumption and Distribution: An Overview," Working Papers 233345, University of California, Davis, Agricultural Development Systems: Egypt Project.
    19. Ramteen Sioshansi and Ashlin Tignor, 2012. "Do Centrally Committed Electricity Markets Provide Useful Price Signals?," The Energy Journal, International Association for Energy Economics, vol. 0(Number 4).
    20. Haefner, Dr. Lonnie E., 1974. "Multimodal Transportation Needs At Port Sites - A Policy Programming Framework," Transportation Research Forum Proceedings 1970s 318393, Transportation Research Forum.

    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:inm:oropre:v:48:y:2000:i:4:p:623-634. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.