TY - JOUR A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Salvagnin, Domenico T1 - An exploratory computational analysis of dual degeneracy in mixed-integer programming JF - EURO Journal on Computational Optimization N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1007/s13675-020-00130-z IS - 8 SP - 241 EP - 246 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Hendel, Gregor A1 - Gamrath, Gerald A1 - Achterberg, Tobias A1 - Bastubbe, Michael A1 - Berthold, Timo A1 - Christophel, Philipp M. A1 - Jarck, Kati A1 - Koch, Thorsten A1 - Linderoth, Jeff A1 - Lübbecke, Marco A1 - Mittelmann, Hans A1 - Ozyurt, Derya A1 - Ralphs, Ted A1 - Salvagnin, Domenico A1 - Shinano, Yuji T1 - MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library JF - Mathematical Programming Computation N2 - We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data. Y1 - 2021 U6 - https://doi.org/10.1007/s12532-020-00194-3 VL - 13 IS - 3 SP - 443 EP - 490 ER -