Lattice based extended formulations for integer linear equality systems
(2010) Mathematical Programming — Vol. 121, n° 2, p. 337-353 (2010)
Files
Rep2192.pdf
Restricted Access - Adobe PDF
- 417 KB
Details
- Authors
- Abstract
- We study different extended formulations for the set $X = \{x \in Z^n \mid Ax = Ax^0\}$ with $A \in Z^{m\times n}$ in order to tackle the feasibility problem for the the $X \cap Z^n_+$. Pursuing the work of Aardal, Lenstra et al. using the reformulation $X = \{x \in Z^n \mid x - x^0 = Q\lambda, \lambda \in Z^{n-m}\}$, our aim is to derive reformulations of the form $\{x \in Z^n \mid P(x-x^0) = T\mu, \mu \in Z^s\}$ with $0 \le s \le 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 $\mu$ 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 analyse the reformulations when $s=1$, that is one $\mu$-variable is introduced. In particular, we determine the integer width of the extended formulations in the directions of the $\mu$-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.
- Affiliations
Technische Universiteit Eindhoven Faculteit Wiskunde en Informatica
Citations
Aardal, K. (2010). Lattice based extended formulations for integer linear equality systems. Mathematical Programming, 121(2), 337-353. https://doi.org/10.1007/s10107-008-0236-7 (Original work published 2010)