Degeneracy in MIP:
Mixed integer programs arising from practical applications typically feature highly degenerate solutions to their LP relaxation. Consequently, these LPs have multiple optimal solutions, often both in the primal and the dual space. This degeneracy is arguably the main reason for performance variability of
LP based MIP solvers.
In recent years, various authors have investigated different aspects of LP degeneracy in MIP solving. One line of research is to try to exploit degeneracy in order to improve the performance of MIP solvers or to reduce the solvers' variability. Examples are Zanette's, Fischetti's, and Balas' work on using the
lexicographic simplex for Gomory cuts, the "pump reduce" step in CPLEX, or the "degenerate reduced cost fixing" implemented in the SAS/OR solver. Most recently, Bajgiran, Cire, and Rousseau presented a more systematic way to pick dual optimal LP solutions in order to improve reduced cost fixing.
This talk provides a survey of some of these approaches and explains how Gurobi is exploiting LP degeneracy. Computational results assess the practical impact
of the various techniques.
****************************************************
The Aussois Shortest Path Problem:
The ASSP means to find the shortest path from the bar to ones bedroom. Due to the layout of the conference building, this is a challenging task for human beings.
The underlying graph is connected and does not contain negative cycles, which means that the problem is in theory easy to solve by a polynomial algorithm. Nevertheless, the problem remained unsolved for 22 years.
The main issue, as in most practical applications, is the lack of data. The slide deck at hand provides a first step to tackle the problem by providing a graph with edge lengths that models the building. As usual, the data are certainly incomplete and errorprone. Moreover, it comes (as always in realworld applications) in a completely unusable format, in this case a pdf file derived from a Powerpoint presentation.
We hope to encourage research for this important problem so that we can see some interesting results on the topic in upcoming Aussois workshops.
