TY - JOUR

T1 - Lattice based extended formulations for integer linear equality systems

AU - Aardal, K.I.

AU - Wolsey, L.A.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1007/s10107-008-0236-7

DO - 10.1007/s10107-008-0236-7

M3 - Article

VL - 121

SP - 337

EP - 352

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -