Hilbert basis (linear programming)

In linear programming, a Hilbert basis is a minimal set of integer vectors $\{a_{1},\ldots ,a_{n}\}$ such that every integer vector in its convex cone

$\{\lambda _{1}a_{1}+\ldots +\lambda _{n}a_{n}\mid \lambda _{1},\ldots ,\lambda _{n}\geq 0,\lambda _{1},\ldots ,\lambda _{n}{\mbox{ real}}\}$

is also in its integer cone

$\{\lambda _{1}a_{1}+\ldots +\lambda _{n}a_{n}\mid \lambda _{1},\ldots ,\lambda _{n}\geq 0,\lambda _{1},\ldots ,\lambda _{n}{\mbox{ integer}}\}$.

In other words, if an integer vector is a non-negative combination of vectors in a Hilbert basis, then this vector is also in the integer non-negative combination of vectors in the Hilbert basis.

References

• Carathéodory bounds for integer cones [1]
• An Integer Analogue of Carathéodory's Theorem [2]
• A Counterexample to an Integer Analogue of Carathéodory's Theorem [3]