Hilbert basis (linear programming): Difference between revisions

Revision as of 05:06, 29 November 2006

Latest revision as of 01:14, 20 May 2025

(46 intermediate revisions by 28 users not shown)

Line 1:

The '''Hilbert basis''' of a [[convex cone]] ''C'' is a minimal set of integer [[vector (mathematics)|vector]]s in ''C'' such that every [[integer]] vector in ''C'' is a [[conical combination]] of the vectors in the Hilbert basis with integer coefficients.

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

=== ReferencesDefinition ===

[[File:Hilbert basis.gif|thumb|Hilbert basis visualization. Two rays in the plane define an infinite cone of all the points lying between them. The unique Hilbert basis points of the cone are circled in yellow. Every integer point in the cone can be written as a sum of these basis elements. As you change the cone by moving one of the rays, the Hilbert basis also changes.]]

Given a [[Lattice (group)|lattice]] <math>L\subset\mathbb{Z}^d</math> and a convex polyhedral cone with generators <math>a_1,\ldots,a_n\in\mathbb{Z}^d</math>

:<math>C=\{ \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}\}\subset\mathbb{R}^d,</math>

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

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

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

we consider the [[monoid]] <math>C\cap L</math>. By [[Gordan's lemma]], this monoid is finitely generated, i.e., there exists a [[finite set]] of lattice points <math>\{x_1,\ldots,x_m\}\subset C\cap L</math> such that every lattice point <math>x\in C\cap L</math> is an integer conical combination of these points:

{{mathstub}}

:<math>\{ x=\lambda_1 a_1 x_1+ \ldots + \lambda_nlambda_m a_nx_m, \mid quad\lambda_1,\ldots,\lambda_n lambda_m\geq 0in\mathbb{Z}, \lambda_1,\ldots,\lambda_n lambda_m\mbox{ integer}\}geq0.</math>.

The cone ''C'' is called pointed if <math>x,-x\in C</math> implies <math>x=0</math>. In this case there exists a unique minimal generating set of the monoid <math>C\cap L</math>—the '''Hilbert basis''' of ''C''. It is given by the set of irreducible lattice points: An element <math>x\in C\cap L</math> is called irreducible if it can not be written as the sum of two non-zero elements, i.e., <math>x=y+z</math> implies <math>y=0</math> or <math>z=0</math>.

== 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]] | volume=1999 | pages=179–185 | issue=510}}

* {{Citation | last1=Cook | first1=William John | last2=Fonlupt | first2=Jean | last3=Schrijver | first3=Alexander | authorlink3=Alexander Schrijver|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 | volume=40 | issue=1 | pages=63–70| doi-access=free }}

* {{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 | volume=34 | issue=5 | pages=564–568| url=http://infoscience.epfl.ch/record/121640 }}

* {{cite journal |author = D. V. Pasechnik |title=On computing the Hilbert bases via the Elliott—MacMahon algorithm |journal=Theoretical Computer Science |volume=263 |issue=1–2 |year=2001 |pages=37–46 |doi=10.1016/S0304-3975(00)00229-2|doi-access=free |hdl=10220/8240 |hdl-access=free }}

[[Category:Linear programming]]

[[Category:Discrete geometry]]

[[Category:Eponyms in geometry]]

{{mathapplied-stub}}