  We study different extended formulations for the set $X = \{x\in\mathbb{Z}^n
\mid Ax = Ax^0\}$ in order to tackle the feasibility problem for the set $X_+=X
\cap \mathbb{Z}^n_+$. 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 permit one to deduce rapidly that the instance is infeasible. For
the case that $A$ has one row $a$ we analyze the reformulations in more detail.
In particular, we determine the integer width of the extended formulations in
the direction of the last coordinate, and derive a lower bound on the Frobenius
number of $a$. We also suggest how a decomposition of the vector $a$ can be
obtained that will provide a useful extended formulation. Our theoretical
results are accompanied by a small computational study.

Optimization and Control;Number Theory