Integer programming is one of the most fundamental problems in discrete optimization. While integer programming is computationally hard in general, there exist efficient algorithms for special instances. In particular, integer programming is fixed parameter tractable when parameterized by the primal or dual tree-depth of the constraint matrix and its entry complexity. However, constraint matrices describing the same instance of integer programming may have differ tree-depth. We use tools from matroid theory to design efficient algorithms that find an equivalent instance of smallest possible tree-depth. Our main algorithm is based on the notion of contraction*-depth, which is the matroid analogue of graph tree-depth. We start with introducing the notion and other matroid width and depth parameters and survey their structural properties. We then relate the contraction*-depth of the column matroid of a matrix to the smallest tree-depth of a row-equivalent matrix, and exploit our structural results to design algorithms of relevance in integer programming.

The talk is based on results jointly obtained with Marcin Briański, Jacob Cooper, Timothy F. N. Chan, Martin Koutecký, Ander Lamaison, Kristýna Pekárková and Felix Schröder.