Smallest Integer Linear Programming Formulations

We study the minimum number of variables and constraints of Integer Linear Programming (ILP) formulations for discrete optimisation problems with a fixed set of solutions. The number of variables and minimum number of constraints are determined by the encoding of the solutions.

We find that all relevant encodings with respect to minimising the number of variables and constraints generate the full integer lattice, leading to various characterisations of relevant encodings. We further derive lower bounds on the number of variables and, assuming rational coefficients, on the number of constraints.

Applying these results to parity-constrained optimisation, the Uncapacitated Facility Location Problem, and the Asymmetric Traveling Salesperson Problem, we derive nondominated encodings with the minimum number of variables and, for the first two, provably smallest ILP formulations.

Finally, we extend known exponential lower bounds on the relaxation complexity and extension complexity of standard encodings of classic optimisation problems to other encodings.

Coordinators

Ruben van Beesten