Lattice based extended formulations for integer linear equality systems

摘要

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. Keywords Integer programming - Lattice basis reduction - Integer width - Frobenius number Mathematics Subject Classification (2000) 90C10 - 45A05 - 11Y50 This work was partly carried out within the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract no. MRTN-CT-2003-504438. The first author is financed in part by the Dutch BSIK/BRICKS project. The research was carried out in part while the second author visited CWI, Amsterdam with the support of the NWO visitor grant number B 61-556.