First-order representations for integer programming
James Cussens, University of York

Modelling languages such as ZIMPL are tremendously useful ways of
compactly writing down integer programs with large numbers of
variables and constraints. A ZIMPL statement such as "forall a in A
forall b in B: x[a] <= x[b]" expresses a (linear) constraint for
each pair (a,b). But prior to sending the problem to a solver such an
expression will be "propositionalised" into a (possibly large) set of
ground instances of the constraint. In this talk I aim to explore
whether this "grounding out" can be avoided, and whether there is any
advantage in so doing. I will be discussing cutting plane algorithms
(as a representation of sets of constraints) and column generation
algorithms (as a representation of sets of variables). My talk will
not assume any prior knowledge of integer programming.