Hilbert basis (linear programming): Difference between revisions

Revision as of 05:06, 29 November 2006

Revision as of 05:08, 29 November 2006

Line 1:

In [[integer linear programming]], a '''Hilbert basis''' is a minimal set of integer vectors <math>\{a_1,\ldots,a_n\}</math> such that

every integer vector in its [[convex cone]]

:<math>\{ \lambda_1 a_1 + \ldots + \lambda_n a_n \mid \lambda_1,\ldots,\lambda_n \geq 0, \lambda_1,\ldots,\lambda_n \mbox{ real}\}</math>

is also in its integer cone

:<math>\{ \lambda_1 a_1 + \ldots + \lambda_n a_n \mid \lambda_1,\ldots,\lambda_n \geq 0, \lambda_1,\ldots,\lambda_n \mbox{ integer}\}</math>.

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 [http://dx.doi.org/10.1016/j.orl.2005.09.008]