Recent Advances on the Parameterized Complexity of Integer Linear Programming

Abstract:

Integer Linear Programming (ILP) is probably the archetypical NP-complete optimisation problem, allowing for the efficient solution of many otherwise intractable optimisation problems in computer science by a translation to ILP. Surprisingly, until very recently, only few tractable classes of ILP had been identified, i.e., ILP is known to be solvable in polynomial-time if the constraint matrix is totally uni-modular (Papadimitriou, Steiglitz 1982) and if the number of variables (or constraints) is constant (Lenstra, 1983). In particular, in contrast to SAT and CSP, ILP had not been studied w.r.t. structural restrictions on the constraint matrix.

The aim of this talk is to survey recent results on the (parameterized) complexity of ILP under structural restrictions on the constraint matrix. Namely, we consider structural restrictions on two graphical models of the constraint matrix (that have had a huge impact for our understanding of SAT and CSP): (1) the primal graph having a vertex for every variable and an edge between every two variables occurring together in a constraint and (2) the incidence graph having a vertex for every variable and every constraint and an edge between a variable and a constraint if the variable occurs (with a non-zero coefficient) in the constraint. After providing an overview about known tractability (and intractability) results w.r.t. well-known decompositional parameters such as treedepth, treewidth, and clique-width, we will show that the well known block-structured ILPs (e.g., n-fold, two-stage stochastic, 4-block N-fold, and tree-fold ILPs) can be modelled (and generalised) in terms of certain structural parameters on the primal and incidence graph.