IDEAS home Printed from https://ideas.repec.org/a/spr/eurjco/v8y2020i3d10.1007_s13675-020-00130-z.html
   My bibliography  Save this article

An exploratory computational analysis of dual degeneracy in mixed-integer programming

Author

Listed:
  • Gerald Gamrath

    (Zuse Institute Berlin
    I²DAMO GmbH)

  • Timo Berthold

    (Fair Isaac Germany GmbH)

  • Domenico Salvagnin

    (DEI)

Abstract

Dual degeneracy, i.e., the presence of multiple optimal bases to a linear programming (LP) problem, heavily affects the solution process of mixed integer programming (MIP) solvers. Different optimal bases lead to different cuts being generated, different branching decisions being taken and different solutions being found by primal heuristics. Nevertheless, only a few methods have been published that either avoid or exploit dual degeneracy. The aim of the present paper is to conduct a thorough computational study on the presence of dual degeneracy for the instances of well-known public MIP instance collections. How many instances are affected by dual degeneracy? How degenerate are the affected models? How does branching affect degeneracy: Does it increase or decrease by fixing variables? Can we identify different types of degenerate MIPs? As a tool to answer these questions, we introduce a new measure for dual degeneracy: the variable–constraint ratio of the optimal face. It provides an estimate for the likelihood that a basic variable can be pivoted out of the basis. Furthermore, we study how the so-called cloud intervals—the projections of the optimal face of the LP relaxations onto the individual variables—evolve during tree search and the implications for reducing the set of branching candidates.

Suggested Citation

  • Gerald Gamrath & Timo Berthold & Domenico Salvagnin, 2020. "An exploratory computational analysis of dual degeneracy in mixed-integer programming," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 241-261, October.
    • Handle: RePEc:spr:eurjco:v:8:y:2020:i:3:d:10.1007_s13675-020-00130-z
    DOI: 10.1007/s13675-020-00130-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13675-020-00130-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13675-020-00130-z?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. C. E. Lemke, 1954. "The dual method of solving the linear programming problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(1), pages 36-47, March.
    2. Wm. Orchard-Hays, 1958. "Evolution of Linear Programming Computing Techniques," Management Science, INFORMS, vol. 4(2), pages 183-190, 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. Arie M. C. A. Koster & Clemens Thielen, 2020. "Special issue on: Computational discrete optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 201-203, October.

    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. Timo Berthold & Jakob Witzig, 2021. "Conflict Analysis for MINLP," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 421-435, May.
    2. Anh Ninh & Honggang Hu & David Allen, 2019. "Robust newsvendor problems: effect of discrete demands," Annals of Operations Research, Springer, vol. 275(2), pages 607-621, April.
    3. Anh Ninh, 2021. "Robust newsvendor problems with compound Poisson demands," Annals of Operations Research, Springer, vol. 302(1), pages 327-338, July.
    4. Thomas L. Magnanti, 2021. "Optimization: From Its Inception," Management Science, INFORMS, vol. 67(9), pages 5349-5363, September.

    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:eurjco:v:8:y:2020:i:3:d:10.1007_s13675-020-00130-z. 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.