Karen
Aardal
Title:
Using input structure to solve hard integer programs
Abstract:
Recently several hard integer programming feasibility problems
have
been successfully tackled using a lattice reformulation proposed by
Aardal et al. Pursuing this approach, we study the feasibility problem
for the set X = {x?¸ Z^n_+ | A x = A x0} and derive a variety of
extended formulations for this set and its polyhedral relaxation. Here
the goal is not to find an improved polyhedral relaxation of conv(X),
but rather to reformulate in such a way that the new variables
introduced provide good branching directions, and in certain
circumstances to deduce rapidly that the instance is infeasible. We
derive results on the integer width of a certain reformulation, and
also a lower bound on the Frobenius number in a more general setting
than Aardal
and Lenstra. Joint work with L.A. Wolsey