Hilbert basis (linear programming)

In linear programming, a Hilbert basis for a convex cone is a minimal set of integer vectors such that every integer vector in the convex cone is a linear combination of the vectors in the Hilbert basis with non-negative integer coefficients.

More precisely, a set $\{a_{1},\ldots ,a_{n}\}$ of integer vectors is a Hilbert basis if 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}}\}.$

References

• Bruns, Winfried; Gubeladze, Joseph; Henk, Martin; Martin, Alexander; Weismantel, Robert (1999), "A counterexample to an integer analogue of Carathéodory's theorem", Journal für die reine und angewandte Mathematik, 510: 179–185, doi:10.1515/crll.1999.045.
• Cook, William John; Fonlupt, Jean; Schrijver, Alexander (1986), "An integer analogue of Carathéodory's theorem", Journal of Combinatorial Theory. Series B, 40 (1): 63–70, doi:10.1016/0095-8956(86)90064-X.
• Eisenbrand, Friedrich; Shmonin, Gennady (2006), "Carathéodory bounds for integer cones", Operations Research Letters, 34 (5): 564–568, doi:10.1016/j.orl.2005.09.008.