Hilbert basis (linear programming): Difference between revisions

Revision as of 04:47, 23 August 2008

Revision as of 13:53, 29 August 2008

Line 1:

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.

{{Wikify|date=July 2008}}

InMore [[linear programming]]precisely, a '''Hilbert basis''' is a minimal set of integer vectors <math>\{a_1,\ldots,a_n\}</math> suchof integer vectors is a Hilbert basis thatif

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>

Line 8:

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 ==

* {{Citation | last1=Bruns | first1=Winfried | last2=Gubeladze | first2=Joseph | last3=Henk | first3=Martin | last4=Martin | first4=Alexander | last5=Weismantel | first5=Robert | title=A counterexample to an integer analogue of Carathéodory's theorem | doi=10.1515/crll.1999.045 | year=1999 | journal=[[Journal für die reine und angewandte Mathematik]] | issn=0075-4102 | volume=510 | pages=179–185}}.

* Carathéodory bounds for integer cones [http://dx.doi.org/10.1016/j.orl.2005.09.008]

* {{Citation | last1=Cook | first1=William John | last2=Fonlupt | first2=Jean | last3=Schrijver | first3=Alexander | title=An integer analogue of Carathéodory's theorem | doi=10.1016/0095-8956(86)90064-X | year=1986 | journal=Journal of Combinatorial Theory. Series B | issn=0095-8956 | volume=40 | issue=1 | pages=63–70}}.

* An Integer Analogue of Carathéodory's Theorem [http://repos.project.cwi.nl:8888/cwi_repository/docs/I/10/10058A.pdf]

* {{Citation | last1=Eisenbrand | first1=Friedrich | last2=Shmonin | first2=Gennady | title=Carathéodory bounds for integer cones | doi=10.1016/j.orl.2005.09.008 | year=2006 | journal=Operations Research Letters | issn=0167-6377 | volume=34 | issue=5 | pages=564–568}}.

* A Counterexample to an Integer Analogue of Carathéodory's Theorem [http://page.mi.fu-berlin.de/~chaase/lehre/bghmw.pdf]

[[Category:Mathematical optimization]]

[[Category:Operations research]]

{{mathsmathapplied-stub}}

{{Uncategorizedstub|date=July 2008}}

[[Category:Mathematical optimization]]

{{maths-stub}}

[[Category:Operations research]]