%0 Journal Article
%T Computing holes in semi-groups and its applications to transportation problems
%A Raymond Hemmecke
%A Akimichi Takemura
%A Ruriko Yoshida
%J Contributions to Discrete Mathematics
%D 2009
%I University of Calgary
%X An integer feasibility problem is a fundamental problem in many areas, such as operations research, number theory, and statistics. To study a family of systems with no nonnegative integer solution, we focus on a commutative semigroup generated by a finite set of vectors in $^d$ and its saturation. In this paper we present an algorithm to compute an explicit description for the set of holes which is the difference of a semi-group $Q$ generated by the vectors and its saturation. We apply our procedure to compute an infinite family of holes for the semi-group of the $3 imes 4 imes 6$ transportation problem. Furthermore, we give an upper bound for the entries of the holes when the set of holes is finite. Finally, we present an algorithm to find all $Q$-minimal saturation points of $Q$.
%U http://cdm.math.ucalgary.ca/cdm/index.php/cdm/article/view/149