We study different extended formulations for the set with in order to tackle the feasibility problem for the set Pursuing the work of Aardal, Lenstra et al. using the reformulation , our aim is to derive reformulations of the form with 0 = s = n - m where preferably all the coefficients of P are small compared to the coefficients of A and T. In such cases the new variables µ appear to be good branching directions, and in certain circumstances permit one to deduce rapidly that the instance is infeasible. We give a polynomial time algorithm for identifying such P, T if possible, and for the case that A has one row a we analyze the reformulation when s = 1, that is, one µ-variable is introduced. In particular, we determine the integer width of the extended formulations in the direction of the µ-variable, and derive a lower bound on the Frobenius number of a. We conclude with some preliminary tests to see if the reformulations are effective when the number s of additional constraints and variables is limited.