An exploratory computational analysis of dual degeneracy in mixed-integer programming
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2020-10-01
|
| Series: | EURO Journal on Computational Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192440621001295 |
| _version_ | 1818841816999395328 |
|---|---|
| author | Gerald Gamrath Timo Berthold Domenico Salvagnin |
| author_facet | Gerald Gamrath Timo Berthold Domenico Salvagnin |
| author_sort | Gerald Gamrath |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-19T04:32:06Z |
| format | Article |
| id | doaj.art-02acf5f02ecf4593a8b6c0599764c3ca |
| institution | Directory Open Access Journal |
| issn | 2192-4406 |
| language | English |
| last_indexed | 2024-12-19T04:32:06Z |
| publishDate | 2020-10-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Computational Optimization |
| spelling | doaj.art-02acf5f02ecf4593a8b6c0599764c3ca2022-12-21T20:35:50ZengElsevierEURO Journal on Computational Optimization2192-44062020-10-0183241261An exploratory computational analysis of dual degeneracy in mixed-integer programmingGerald Gamrath0Timo Berthold1Domenico Salvagnin2Zuse Institute Berlin, 14195, Berlin, Germany.; I²DAMO GmbH, Englerallee 19, 14195, Berlin, Germany.Fair Isaac Germany GmbH, Stubenwald-Allee 19, 64625, Bensheim, Germany.DEI, Via Gradenigo, 6/B, 35131, Padua, Italy.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.http://www.sciencedirect.com/science/article/pii/S219244062100129590C1090C1190C57 |
| spellingShingle | Gerald Gamrath Timo Berthold Domenico Salvagnin An exploratory computational analysis of dual degeneracy in mixed-integer programming EURO Journal on Computational Optimization 90C10 90C11 90C57 |
| title | An exploratory computational analysis of dual degeneracy in mixed-integer programming |
| title_full | An exploratory computational analysis of dual degeneracy in mixed-integer programming |
| title_fullStr | An exploratory computational analysis of dual degeneracy in mixed-integer programming |
| title_full_unstemmed | An exploratory computational analysis of dual degeneracy in mixed-integer programming |
| title_short | An exploratory computational analysis of dual degeneracy in mixed-integer programming |
| title_sort | exploratory computational analysis of dual degeneracy in mixed integer programming |
| topic | 90C10 90C11 90C57 |
| url | http://www.sciencedirect.com/science/article/pii/S2192440621001295 |
| work_keys_str_mv | AT geraldgamrath anexploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT timoberthold anexploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT domenicosalvagnin anexploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT geraldgamrath exploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT timoberthold exploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming AT domenicosalvagnin exploratorycomputationalanalysisofdualdegeneracyinmixedintegerprogramming |