Hilbert basis (linear programming) explained
The Hilbert basis of a convex cone C is a minimal set of integer vectors in C such that every integer vector in C is a conical combination of the vectors in the Hilbert basis with integer coefficients.
Definition
and a convex polyhedral cone with generators
C=\{λ1a1+\ldots+λnan\midλ1,\ldots,λn\geq0,λ1,\ldots,λn\inR\}\subsetRd,
. By
Gordan's lemma, this monoid is finitely generated, i.e., there exists a finite set of lattice points
\{x1,\ldots,xm\}\subsetC\capL
such that every lattice point
is an integer conical combination of these points:
x=λ1x1+\ldots+λmxm, λ1,\ldots,λm\inZ,λ1,\ldots,λm\geq0.
The cone C is called pointed if
implies
. In this case there exists a unique minimal generating set of the monoid
—the
Hilbert basis of
C. It is given by the set of irreducible lattice points: An element
is called irreducible if it can not be written as the sum of two non-zero elements, i.e.,
implies
or
.
References
- D. V. Pasechnik . On computing the Hilbert bases via the Elliott—MacMahon algorithm . Theoretical Computer Science . 263 . 1–2 . 2001 . 37–46 . 10.1016/S0304-3975(00)00229-2. free . 10220/8240 . free .
