Graver basis explained
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.[1] Their connection to the theory of Gröbner bases was discussed by Bernd Sturmfels.[2] The algorithmic theory of Graver bases and its application to integer programming is described by Shmuel Onn.[3] [4]
Formal definition
The Graver basis of an m × n integer matrix
is the finite set
of minimal elements in the set
under a well partial order on
defined by
when
and
for all i. For example, the Graver basis of
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:
min\{f(x) : x\inZn, Ax=b, l\leqx\lequ\} .
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
of
, 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,[5] is that of linear integer programming,
min\{wx : x\inZn, Ax=b, l\leqx\lequ\} .
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
of
has the following property. For every feasible point
x:
- Either x is optimal (i.e., minimizes
given the constraints);
- Or there exists a vector g in
, such that
x+
g is feasible and
(i.e.,
x can be improved by adding to it an element of the Graver basis).
Therefore, given the Graver basis
, the ILP
can be solved in polynomial time using the following simple iterative algorithm.
[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
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 [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
min\{f(x) : x\inZn, Ax=b, l\leqx\lequ\}
can be solved using the Graver basis
in polynomial time forseveral nonlinear objective functions including:
- Separable-convex functions of the form
;
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,
}_+^\,,\ \sum_i x_=a_ \,,\ \sum_j x_=b_\,,\ \sum_k x_=c_\}\,
with
,
,
nonnegative integers (whose maximum value implicitly bounds all variables from above). Denote by
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
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
, (non)-linear optimization over
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 functionminimized 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,[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.
Universality and parametrization
It was shown in [13] 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
the Graver basis of the matrix
defining the universal 3 ×
m ×
n table problem discussed above. The elements of
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
is at most
g(
m). It follows that the Graver basis
is the union of the
suitably embedded copies of the Graver basis
. 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
. At level
k of this hierarchy, let
be the subset of
consisting only of those elements of type at most
k; use this approximation
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
of the Graver basis has polynomial cardinality
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
with typically large degree
g whichis a suitable Graver complexity of the system. In
[14] a much faster algorithm is presented, which finds at each iteration the best improvement
x +
qg with
q positive integer and
g element in
without explicitly constructing the Graver basis, in cubic time
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.
Notes and References
- Jack E. Graver: On the foundations of linear and linear integer programming, Mathematical Programming 9:207–226, 1975
- [Bernd Sturmfels]
- http://ie.technion.ac.il/~onn Shmuel onn
- Shmuel Onn: Linear and nonlinear integer optimization, Online Video Lecture Series, Mathematical Sciences Research Institute, Berkeley, 2010
- [Alexander Schrijver]
- Raymond Hemmecke, Shmuel Onn, Robert Weismantel: A polynomial oracle-timealgorithm for convex integer minimization, Mathematical Programming126:97–117, 2011
- Yuri V. Matiyasevich: Hilbert's Tenth Problem, MIT Press, xxiv+264 pp., 1993
- [Jesús A. De Loera]
- [Jesús A. De Loera]
- Theodore S. Motzkin: The multi-index transportationproblem, Bulletin of the American Mathematical Society 58:494, 1952
- Raymond Hemmecke, Matthias Köppe, Robert Weismantel: A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, IPCO 14, 2010
- Book: Bredereck. Robert. Kaczmarczyk. Andrzej. Knop. Dušan. Niedermeier. Rolf. Proceedings of the 2019 ACM Conference on Economics and Computation . High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming . Rolf Niedermeier. 2019-06-17. https://doi.org/10.1145/3328526.3329649. EC '19. Phoenix, AZ, USA. Association for Computing Machinery. 505–523. 10.1145/3328526.3329649. 978-1-4503-6792-9. 195298520 .
- Jesus A. De Loera, Shmuel Onn: Alllinear and integer programs are slim 3-way transportation programs, SIAM Journal on Optimization, 17:806–821, 2006
- Raymond Hemmecke, Shmuel Onn, Lyubov Romanchuk: N-fold integer programming in cubic time, Mathematical Programming, 137:325–341, 2013