An exploratory computational analysis of dual degeneracy in mixed-integer programming
- PDF / 2,341,653 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 48 Downloads / 165 Views
An exploratory computational analysis of dual degeneracy in mixed-integer programming Gerald Gamrath1,2
· Timo Berthold3 · Domenico Salvagnin4
Received: 1 October 2019 / Accepted: 10 July 2020 © The Author(s) 2020
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. Keywords Mixed integer programming · Dual degeneracy · Linear programming · Branch-and-bound
B
Gerald Gamrath [email protected] Timo Berthold [email protected] Domenico Salvagnin [email protected]
1
Zuse Institute Berlin, 14195 Berlin, Germany
2
I2 DAMO GmbH, Englerallee 19, 14195 Berlin, Germany
3
Fair Isaac Germany GmbH, Stubenwald-Allee 19, 64625 Bensheim, Germany
4
DEI, Via Gradenigo, 6/B, 35131 Padua, Italy
123
G. Gamrath et al.
Mathematics Subject Classification 90C10 · 90C11 · 90C57
1 Introduction In this paper, we analyze dual degeneracy emerging in linear programming (LP) relaxations solved during the solution process of generic mixed-integer (linear) programs (MIPs) in standard form: min{c T x : Ax = b, x ≥ 0, x j ∈ Z ∀ j ∈ J } where x ∈ Rn is the solution vector, c ∈ Rn , A ∈ Rm×n , b ∈ Rm , and J ⊆ N = {1, . . . , n}. In the following, x may consist of both structural variables as well as artificial slack variables introduced to obtain this form. For the ease of presentation, we do not consider explicit upper bounds on the variables in our notation. However, all measures introduced in the following can be easily extended to that case. MIPs are typically solved with the LP-based branch-and-bound algorithm (Land and Doig 1960; Dakin 1965), which recursively splits the problem into subproblems until those are easy to solve or can be shown to not contain a solution that improves the best one found so far. In this process, LP relaxations of the subproblems—obtained by omi
Data Loading...
