Graver basis

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

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

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 ${\displaystyle G(A)}$ of ${\displaystyle A}$ has the following property. For every feasible point x:

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

Therefore, given the Graver basis ${\displaystyle G(A)}$, the ILP can be solved in polynomial time using the following simple iterative algorithm.[3][6] Assume first that some initial feasible point x is given. While possible, repeat the following iteration: find positive integer q and element g in ${\displaystyle G(A)}$ 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.

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 [7]), 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

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

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

• Separable-convex functions of the form ${\displaystyle f(x)=\sum _{i=1}^{n}f_{i}(x_{i})}$;
• In particular the p-norm ${\displaystyle f(x)=\|x\|_{p}}$ 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.

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

${\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}\}\ ,}

with ${\displaystyle a_{j,k}}$, ${\displaystyle b_{i,k}}$, ${\displaystyle c_{i,j}}$ nonnegative integers (whose maximum value implicitly bounds all variables from above). Denote by ${\displaystyle A}$ the (lm + ln + mn) × (lmn) defining matrix of this system. Note that this matrix is generally not totally unimodular. Nonetheless, it was shown in [8] that for every fixed l and m, its Graver basis ${\displaystyle G(A)}$ 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.[9] More generally, similar positive results hold for higher-dimensional table problems (introduced in [10]): for every fixed d and ${\displaystyle m_{1},\dots ,m_{d}}$, (non)-linear optimization over ${\displaystyle m_{1}\times \cdots \times m_{d}\times n}$ 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.

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.

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

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

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.