Exploiting Structure in Integer Linear Programs

a doctoral dissertation to be submitted by Jakub Marecek <jakub at marecek dot cz> (www),
supervised by Prof. Edmund K. Burke <ekb at cs dot nott dot ac dot uk> (www)
and Dr. Andrew J. Parkes <ajp at cs dot nott dot ac dot uk> (www).

An Overview

This dissertation argues the case for exploiting certain structures in integer linear programs. Integer linear programming is a well-known optimisation problem, which seeks the optimum of a linear function of variables, whose values are required to be integral as well as to satisfy certain linear equalities and inequalities. The state of the art in solvers for this problem is the branch and cut approach. The performance of such solvers depends crucially on four types of in-built heuristics: primal, improvement, branching, and cut-separation or, more generally, bounding heuristics. Such heuristics in general-purpose solvers have not, until recently, exploited structure in integer linear programs beyond the recognition of certain types of single-row constraints.

Many alternative approaches to integer linear programming can be cast in the following, novel framework. Structure in any integer linear program is a class of an equivalence among triples of algorithms: deriving combinatorial objects from the input, adapting them, and transforming the adapted object to solutions of the original integer linear program. Such alternative approaches are, however, inherently incompatible with branch and bound solvers.

This dissertation defines such a structure to be useful, only when it extracts submatrices, which allow for the implementation of more than one of the four types of heuristics required in the branch and bound approach. Three examples of such useful structures are presented: aggregations of variables, mutual-exclusion components, and precedence-constrained components. On instances from complex timetabling problems, where such structures are prevalent, a general-purpose solver, based on this approach, closes the gap between primal and dual bounds to under five percent, orders of magnitude faster than using state-of-the-art general-purpose solvers.

In three appendices, we (A) show that some of the structure (such as aggregations and graph colouring components) could be preserved, if solvers could work directly with an algebraic model of the problem, and (B) that auto-tuning of a complex enough solvers provides means of exploiting a wide range of unknown structures, and (C) provide computational results.

A draft is available.

Go back to Jakub's homepage if you want.