Graver Bases
Implement Graver basis computation for structured matrices and connect to Hilbert bases and integer programming augmentation.
- Suitable for
- Master's thesis
- Supervision
- Zafeirakis Zafeirakopoulos
The Graver basis of an integer matrix \(A \in \mathbb{Z}^{m \times n}\) is the finite set of all primitive elements of the integer kernel \(\ker_{\mathbb{Z}}(A) = \{z \in \mathbb{Z}^n : Az = 0\}\): vectors \(z\) that cannot be written as \(z = u + v\) with \(u, v \in \ker_{\mathbb{Z}}(A)\) nonzero and sign-compatible (\(u_i v_i \geq 0\) for all \(i\)).
Graver bases were introduced by Graver (1975) as a universal structure for integer linear programming: any optimal solution to any linear program over the feasible integer points of \(Ax = b,\, x \geq 0\) can be reached from any feasible point by augmenting along Graver basis elements.
Connection to Hilbert bases
The Graver basis contains the Hilbert basis (minimal generating set of the integer cone) as a subset, but is generally larger. It is the “maximum” generating set needed for augmentation-based optimization.
For a cone \(C = \{x \in \mathbb{R}^n : Ax \geq 0\}\), the Hilbert basis generates all integer points in \(C\) as nonneg. integer combinations. The Graver basis generates all sign-reversals as well.
Augmentation algorithm
Given a feasible point \(x^*\) for \(\min\{cx : Ax = b,\, x \in \mathbb{Z}_{\geq 0}^n\}\), the Graver augmentation step finds \(g\) in the Graver basis such that \(c \cdot g < 0\) and \(x^* + g \geq 0\). Repeating until no improving direction exists yields the optimum.
This is particularly powerful for \(N\)-fold integer programs (De Loera et al., 2008): matrices with a block-diagonal structure where the Graver basis has bounded size in fixed dimension, giving polynomial-time algorithms.
Goal
Implement Graver basis computation for small matrices (\(n \leq 10\)), verify against the Hilbert basis, and apply the augmentation algorithm to small integer programs, including an \(N\)-fold example.
References
-
J. E. Graver. On the foundations of linear and integer linear programming I. Mathematische Zeitschrift, 147(3):211–233, 1975. DOI 10.1007/bf01681344
-
J. A. De Loera, R. Hemmecke, S. Onn, and R. Weismantel. \(N\)-fold integer programming. Discrete Optimization, 5(2):231–241, 2008. DOI 10.1016/j.disopt.2006.06.006 · arXiv:math/0605242
-
A. I. Barvinok. A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed. Mathematics of Operations Research, 19(4):769–779, 1994. DOI 10.1287/moor.19.4.769