On the Computation of Hilbert Bases and Extreme Rays of Cones

Abstract

In this paper we present a novel project-and-lift approach to compute the set of minimal generators of the semigroup $(\Lambda \cap {\mathbb{R}}_{+}^n,+)$ for lattices $\Lambda \subseteq {\mathbb{Z}}^n$. This problem class includes the computation of Hilbert bases of cones $\{z:Az=0,z\in {\mathbb{R}}_{+}^n\}$ for integer matrices $A$. A similar approach can be used to compute only the extreme rays of such cones. Finally, some combinatorial applications and computational experience are presented.