Graver basis

In applied mathematics, Graver bases enable iterative solutions of linear and various nonlinear integer programming problems in polynomial time. They were introduced by Jack E. Graver. Their connection to the theory of Gröbner bases was discussed by Bernd Sturmfels. The algorithmic theory of Graver bases and its application to integer programming is described by Shmuel Onn.

Formal definition

The Graver basis of an m × n integer matrix [math]\displaystyle{ A }[/math] is the finite set [math]\displaystyle{ G(A) }[/math] of minimal elements in the set

[math]\displaystyle{ \{x\in\mathbb{Z}^n : Ax=0,\ x\neq 0\} \, }[/math]

under a well partial order on [math]\displaystyle{ \mathbb{Z}^n }[/math] defined by [math]\displaystyle{ x\sqsubseteq y }[/math] when [math]\displaystyle{ x_iy_i\geq 0 }[/math] and [math]\displaystyle{ |x_i|\leq |y_i| }[/math] for all i. For example, the Graver basis of [math]\displaystyle{ A=(1, 2, 1) }[/math] consists of the vectors (2,−1,0), (0,−1,2), (1,0,−1), (1,−1,1) and their negations.

Solving integer programming using Graver bases

Integer programming is the problem of optimizing a linear or nonlinear objective function over the set of integer points satisfying a system of linear inequalities. Formally, it can be written in standard form as follows:

[math]\displaystyle{ \min\{f(x)\ :\ x \in \mathbb{Z}^n,\ Ax=b,\ l\leq x\leq u\}\ . }[/math]

It is one of the most fundamental discrete optimization problems and has a very broad modeling power and numerous applications in a variety of areas, but is typically very hard computationally as noted below. However, given the Graver basis [math]\displaystyle{ G(A) }[/math] of [math]\displaystyle{ A }[/math], the problem with linear and various nonlinear objective functions can be solved in polynomial time as explained next.

Linear integer programming

The most studied case, treated thoroughly in, is that of linear integer programming,

[math]\displaystyle{ \min\{wx\ :\ x \in \mathbb{Z}^n,\ Ax=b,\ l\leq x\leq u\}\ . }[/math]

It may be assumed that all variables are bounded from below and above: such bounds either appear naturally in the application at hand, or can be enforced without losing any optimal solutions. But, even with linear objective functions the problem is NP-hard and hence presumably cannot be solved in polynomial time.

However, the Graver basis [math]\displaystyle{ G(A) }[/math] of [math]\displaystyle{ A }[/math] has the following property. For every feasible point x:

• Either x is optimal (i.e., minimizes [math]\displaystyle{ w\cdot x }[/math] given the constraints);
• Or there exists a vector g in [math]\displaystyle{ G(A) }[/math], such that x+g is feasible and [math]\displaystyle{ w\cdot(x+g) \lt w\cdot x }[/math] (i.e., x can be improved by adding to it an element of the Graver basis).

Therefore, given the Graver basis [math]\displaystyle{ G(A) }[/math], the ILP can be solved in polynomial time using the following simple iterative algorithm. Assume first that some initial feasible point x is given. While possible, repeat the following iteration: find positive integer q and element g in [math]\displaystyle{ G(A) }[/math] such that x + qg does not violate the bounds and gives best possible improvement; update x := x + qg and proceed to the next iteration. The last point x is optimal and the number of iterations is polynomial.

To find an initial feasible point, a suitable auxiliary program can be set up and solved in a similar fashion.

Nonlinear integer programming

Turning to the case of general objective functions f, if the variables are unbounded then the problem may in fact be uncomputable: it follows from the solution of Hilbert's 10th problem (see ), that there exists no algorithm which, given an integer polynomial f of degree 8 in 58 variables, decides if the minimum value of f over all 58-dimensional integer vectors is 0. However, when the variables are bounded, the problem

[math]\displaystyle{ \min\{f(x)\ :\ x \in \mathbb{Z}^n,\ Ax=b,\ l\leq x\leq u\} }[/math]

can be solved using the Graver basis [math]\displaystyle{ G(A) }[/math] in polynomial time for several nonlinear objective functions including:

• Separable-convex functions of the form [math]\displaystyle{ f(x)=\sum_{i=1}^n f_i(x_i) }[/math];
• In particular the p-norm [math]\displaystyle{ f(x)=\|x\|_p }[/math] for every positive integer p;
• Composite-concave functions f(x) = g(Wx), where W is a d × n integer matrix with d fixed, and where g is a d-variate concave function;
• Certain (in)-definite quadratic and higher degree polynomial functions.

Some applications

Multi-dimensional tables

Consider the following optimization problem over three-dimensional tables with prescribed line sums,

[math]\displaystyle{ \min\{wx\ :\ x\in{\mathbb{Z}}_+^{l\times m\times n}\,,\ \sum_i x_{i,j,k}=a_{j,k} \,,\ \sum_j x_{i,j,k}=b_{i,k}\,,\ \sum_k x_{i,j,k}=c_{i,j}\}\ , }[/math]

with [math]\displaystyle{ a_{j,k} }[/math], [math]\displaystyle{ b_{i,k} }[/math], [math]\displaystyle{ c_{i,j} }[/math] nonnegative integers (whose maximum value implicitly bounds all variables from above). Denote by [math]\displaystyle{ A }[/math] the (lm + ln + mn) × (lmn) defining matrix of this system. Note that this matrix is generally not totally unimodular. Nonetheless, it was shown in that for every fixed l and m, its Graver basis [math]\displaystyle{ G(A) }[/math] can be computed in time which is polynomial in n. The results mentioned above allow then to solve this problem in polynomial time for fixed l and m and variable n. Note that if only one side l of the table is fixed (even with l = 3) while both m and n are variable, then the problem is NP hard, as shown in. More generally, similar positive results hold for higher-dimensional table problems (introduced in ): for every fixed d and [math]\displaystyle{ m_1, \dots, m_d }[/math], (non)-linear optimization over [math]\displaystyle{ m_1 \times \cdots \times m_d \times n }[/math] tables with variable n and prescribed margins can be done in polynomial time. This has further applications to entry security problems and privacy in statistical databases.

Multi-commodity flows

Consider the integer multi-commodity flow problem of routing k types of integer commodities from m suppliers to n consumers subject to supply, consumption, and capacity constraints, so as to minimize the sum of linear or congestion-dependent convex costs on the arcs. Then for every fixed k and m, the Graver basis of the defining system can be computed and the resulting separable-convex objective function minimized in time which is polynomial in the variable number n of consumers and in the rest of the data.

Other applications

The many applications of the algorithmic theory of Graver bases also include:

• stochastic integer programming,
• N-fold integer programming,
• N-fold 4-block decomposable integer programming,
• clustering,
• disclosure control in statistical databases,
• and fair allocation of indivisible objects.

In some of these applications the relevant Graver basis cannot be computed in polynomial time, but can be accessed in an indirect way that allows to use it in polynomial time.

Universality and parametrization

It was shown in that every (bounded) integer programming problem is precisely equivalent to the 3 × m × n table problem discussed above for some m and n and some line sums. Thus, such 3 × m × n table problems are universal for integer programming. Moreover, for each fixed m, the resulting class of integer programs can be solved in polynomial time by the iterative Graver basis method described above. So the table width m provides a parametrization of all integer programming problems.

Hierarchy of approximations for integer programming

Denote by [math]\displaystyle{ G(m,n) }[/math] the Graver basis of the matrix [math]\displaystyle{ A }[/math] defining the universal 3 × m × n table problem discussed above. The elements of [math]\displaystyle{ G(m,n) }[/math] are 3 × m × n tables with all line sums equal to 0. The type of such a table is the number of its nonzero 3 × m layers. It turns out that there is a finite Graver complexity function g(m) such that for any n, the type of any element of the Graver basis [math]\displaystyle{ G(m,n) }[/math] is at most g(m). It follows that the Graver basis [math]\displaystyle{ G(m,n) }[/math] is the union of the [math]\displaystyle{ {n\choose g(m)} }[/math] suitably embedded copies of the Graver basis [math]\displaystyle{ G(m,g(m)) }[/math]. To approximately solve in practice an arbitrary integer programming problem, proceed as follows. First embed it in a suitable 3 × m × n table problem as enabled by the universality noted above. Now apply the following hierarchy of approximations of [math]\displaystyle{ G(m,n) }[/math]. At level k of this hierarchy, let [math]\displaystyle{ G_k(m,n) }[/math] be the subset of [math]\displaystyle{ G(m,n) }[/math] consisting only of those elements of type at most k; use this approximation [math]\displaystyle{ G_k(m,n) }[/math] in the iterative algorithm as long as possible to obtain as good as possible feasible point for the integer programming problem embedded in the 3 × m × n table problem; if the objective function value of this point is satisfactory (say, as compared to the value of the linear programming relaxation), then use this point; otherwise increment k and proceed to the next level of the hierarchy. It can be shown that for any fixed level k, the approximation [math]\displaystyle{ G_k(m,n) }[/math] of the Graver basis has polynomial cardinality [math]\displaystyle{ O\left(m^{g(k)}n^k\right) }[/math] and can be computed in that much time.

Fixed parameter tractability: from polynomial to cubic time complexity

The time complexity of solving some of the applications discussed above, such as multi-dimensional table problems, multicommodity flow problems, and N-fold integer programming problems, is dominated by the cardinality of the relevant Graver basis, which is a polynomial [math]\displaystyle{ O\left(n^g\right) }[/math] with typically large degree g which is a suitable Graver complexity of the system. In a much faster algorithm is presented, which finds at each iteration the best improvement x + qg with q positive integer and g element in [math]\displaystyle{ G(A) }[/math] without explicitly constructing the Graver basis, in cubic time [math]\displaystyle{ O\left(n^3\right) }[/math] regardless of the system. In the terminology of parameterized complexity, this implies that all these problems suitably parameterized, and in particular l × m × n table problems parametrized by l and m, are fixed parameter tractable.

See also

• Gordan's lemma - another tool related to zero sets of integer matrices.