Hilbert basis (linear programming)
The Hilbert basis of a convex cone C is a minimal set of integer vectors such that every integer vector in C is a conical combination of the vectors in the Hilbert basis with integer coefficients.Definition
Given a lattice and a convex polyhedral cone with generators
we consider the monoid. By Gordan's lemma this monoid is finitely generated, i.e., there exists a finite set of lattice points such that every lattice point is an integer conical combination of these points:
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 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.
