  Given an integral $d \times n$ matrix $A$, the well-studied affine semigroup
$\mbox{ Sg} (A)=\{ b : Ax=b, \ x \in {\mathbb Z}^n, x \geq 0\}$ can be
stratified by the number of lattice points inside the parametric polyhedra
$P_A(b)=\{x: Ax=b, x\geq0\}$. Such families of parametric polyhedra appear in
many areas of combinatorics, convex geometry, algebra and number theory. The
key themes of this paper are: (1) A structure theory that characterizes
precisely the subset $\mbox{ Sg}_{\geq k}(A)$ of all vectors $b \in \mbox{
Sg}(A)$ such that $P_A(b) \cap {\mathbb Z}^n $ has at least $k$ solutions. We
demonstrate that this set is finitely generated, it is a union of translated
copies of a semigroup which can be computed explicitly via Hilbert bases
computations. Related results can be derived for those right-hand-side vectors
$b$ for which $P_A(b) \cap {\mathbb Z}^n$ has exactly $k$ solutions or fewer
than $k$ solutions. (2) A computational complexity theory. We show that, when
$n$, $k$ are fixed natural numbers, one can compute in polynomial time an
encoding of $\mbox{ Sg}_{\geq k}(A)$ as a multivariate generating function,
using a short sum of rational functions. As a consequence, one can identify all
right-hand-side vectors of bounded norm that have at least $k$ solutions. (3)
Applications and computation for the $k$-Frobenius numbers. Using Generating
functions we prove that for fixed $n,k$ the $k$-Frobenius number can be
computed in polynomial time. This generalizes a well-known result for $k=1$ by
R. Kannan. Using some adaptation of dynamic programming we show some practical
computations of $k$-Frobenius numbers and their relatives.
