Hilbert basis (linear programming)

In integer linear programming, 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]