Hilbert basis (linear programming): Difference between revisions

Revision as of 10:02, 11 September 2011

Revision as of 20:46, 8 November 2011

Line 1:

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

== Definition ==

A set <math>\{a_1,\ldots,a_n\}</math> of integer vectors is a Hilbert basis if every integer vector in its convex cone

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 \mboxin\mathbb{ realR}\}</math>

is also in its integer cone

:<math>\{ \lambda_1alpha_1 a_1 + \ldots + \lambda_nalpha_n a_n \mid \lambda_1alpha_1,\ldots,\lambda_nalpha_n \geq 0, \lambda_1alpha_1,\ldots,\lambda_nalpha_n \mboxin\mathbb{ integerZ}\}.</math>

== References ==