Lattice based extended formulations for integer linear equality systems |
| |
Authors: | Karen Aardal Laurence A Wolsey |
| |
Institution: | (1) Centrum voor Wiskunde en Informatica, Postbus 94079, 1090 GB Amsterdam, The Netherlands;(2) Faculteit Wiskunde en Informatica, Technische Universiteit Eindhoven, Postbus 513, 5600 MB Eindhoven, The Netherlands;(3) CORE and INMA Université Catholique de Louvain, 34 Voie du Roman Pays, 1348 Louvain-la-Neuve, Belgium |
| |
Abstract: | 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.
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. |
| |
Keywords: | Integer programming Lattice basis reduction Integer width Frobenius number |
本文献已被 SpringerLink 等数据库收录! |
|