In applied mathematics, Graver bases enable iterative solutions of linear and various nonlinear integer programming problems in polynomial time.
[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.
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.
, the problem with linear and various nonlinear objective functions can be solved in polynomial time as explained next.
The most studied case, treated thoroughly in,[5] 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.
, the ILP can be solved in polynomial time using the following simple iterative algorithm.
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 can be solved using the Graver basis
in polynomial time for several nonlinear objective functions including[citation needed]: Consider the following optimization problem over three-dimensional tables with prescribed line sums, with
nonnegative integers (whose maximum value implicitly bounds all variables from above).
the (lm + ln + mn) × (lmn) defining matrix of this system.
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
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: 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.
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.
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.
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.
with typically large degree g which is 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