Hilbert basis (linear programming): Difference between revisions

Content deleted Content added
moved wl to earlier instance, also disambiguated and removed tag
No edit summary
Line 1:
In [[linear programming]], aThe '''Hilbert basis''' forof a [[convex cone]] ''C'' is an integer [[cone basis]]:a minimal set of integer [[vector (mathematics)|vector]]s such that every integer vector in ''C'' is a [[conical combination]] of the vectors in the Hilbert basis with integer coefficients.
 
== Definition ==
 
A set <math>A=\{a_1,\ldots,a_n\}</math> of integer vectors is a Hilbert basis of its [[convex cone]]
Given a [[Lattice (group)|lattice]] <math>L\subset\mathbb{Z}^n</math> and a convex polyhedral cone
 
:<math>C=\{ \lambda_1 a_1 + \ldots + \lambda_n a_n \mid \lambda_1,\ldots,\lambda_n \geq 0, \lambda_1,\ldots,\lambda_n \in\mathbb{R}\}</math>
 
we consider the [[monoid]] <math>C\cap L</math>. By [[Gordan's lemma]] this monoid is finetely 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:
if every integer vector from ''C'' belongs to the integer convex cone of ''A'':
 
:<math>\{ x=\alpha_1 a_1lambda_1 x_1+ \ldots + \alpha_nlambda_m a_nx_m, \mid quad\alpha_1lambda_1,\ldots,\alpha_n lambda_m\geq 0in\mathbb{Z}, \alpha_1lambda_1,\ldots,\alpha_n lambda_m\in\mathbb{Z}\},geq0</math>
 
The '''Hilbert basis''' of ''C'' is the minimal generating set of the monoid <math>C\cap L</math>. It is given by 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>.
and no vector from ''A'' belongs to the integer convex cone of the others.
 
== References ==
Line 24 ⟶ 25:
[[Category:Operations research]]
[[Category:Linear programming]]
[[Category:Discrete geometry]]
[[Category:Combinatorial algebra]]