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

A

{\displaystyle A}

is the finite set

G

(

A

)

{\displaystyle G(A)}

of minimal elements in the set

{

x

∈

Z

n

:

A

x

=

0

,

x

≠

0

}

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

under a well partial order on

Z

n

{\displaystyle \mathbb {Z} ^{n}}

defined by

x

⊑

y

{\displaystyle x\sqsubseteq y}

when

x

i

y

i

≥

0

{\displaystyle x_{i}y_{i}\geq 0}

and

|

x

i

|

≤

|

y

i

|

{\displaystyle |x_{i}|\leq |y_{i}|}

for all i. For example, the Graver basis of

A

=

(

1

,

2

,

1

)

{\displaystyle A=(1,2,1)}

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

∈

Z

n

,

A

x

=

b

,

l

≤

x

≤

u

}

.

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

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

G

(

A

)

{\displaystyle G(A)}

of

A

{\displaystyle A}

, the problem with linear and various nonlinear objective functions can be solved in polynomial time as explained next.