MarketHilbert basis (linear programming)
Company Profile

Hilbert basis (linear programming)

The Hilbert basis of a convex cone C is a minimal set of integer vectors in C such that every integer vector in C is a conical combination of the vectors in the Hilbert basis with integer coefficients.

Definition
Given a lattice L\subset\mathbb{Z}^d and a convex polyhedral cone with generators a_1,\ldots,a_n\in\mathbb{Z}^d 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, we consider the monoid C\cap L. By Gordan's lemma, this monoid is finitely generated, i.e., there exists a finite set of lattice points \{x_1,\ldots,x_m\}\subset C\cap L such that every lattice point x\in C\cap L is an integer conical combination of these points: 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. The cone C is called pointed if x,-x\in C implies x=0. In this case there exists a unique minimal generating set of the monoid C\cap L—the Hilbert basis of C. It is given by the set of irreducible lattice points: An element x\in C\cap L is called irreducible if it can not be written as the sum of two non-zero elements, i.e., x=y+z implies y=0 or z=0. == References ==
tickerdossier.comtickerdossier.substack.com