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.
Contents
- Formal definition
- Solving integer programming using Graver bases
- Linear integer programming
- Nonlinear integer programming
- Multi dimensional tables
- Multi commodity flows
- Other applications
- Universality and parametrization
- Hierarchy of approximations for integer programming
- Fixed parameter tractability from polynomial to cubic time complexity
- References
Formal definition
The Graver basis of an m × n integer matrix
under a well partial order on
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:
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
Linear integer programming
The most studied case, treated thoroughly in, is that of linear integer programming,
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, given the Graver basis
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
can be solved using the Graver basis
Multi-dimensional tables
Consider the following optimization problem over three-dimensional tables with prescribed line sums,
with
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, and disclosure control in statistical databases. 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
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