Hilbert basis (linear programming)

From Wikipedia, the free encyclopedia

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.

[edit] 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]
 This mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../h/i/l/Hilbert_basis_%28linear_programming%29.html"