Hilbert basis (linear programming): Difference between revisions

Revision as of 22:37, 24 September 2023

Revision as of 22:38, 24 September 2023

Line 5:

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

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:

:<math> x=\lambda_1 x_1+\ldots+\lambda_m x_m, \quad\lambda_1,\ldots,\lambda_m\in\mathbb{Z}, \lambda_1,\ldots,\lambda_m\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 ==