On the Computation of Hilbert Bases and Extreme Rays of Cones

الأصل · EN

In this paper we present a novel project-and-lift approach to compute the set of minimal generators of the semigroup (Λ∩ⁿ+,+) for lattices Λⁿ. This problem class includes the computation of Hilbert bases of cones {z:Az=0,z∈ⁿ+} 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.