Department of
Applied
Mathematics

Recent Advances on the Parameterized Complexity of Integer Linear Programming

Sebastian Ordyniak

University of Sheffield

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 ILPunder 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 a brief overview about known tractability (and intractability) results w.r.t. well-known decompositional parameters such as treedepth, treewidth, and clique-width and their relation to the well known block-structured ILPs (e.g., n-fold, two-stage stochastic, 4-block N-fold, and tree-fold ILPs) we will focus on recent progress made towards resolving a long standing open problem, namely, the exact parameterized complexity of 4-block n-fold ILPs.