A generalization of the integer linear infeasibility problem

Does a given system of linear equations Ax=b have a non-negative integer solution? This is a fundamental question in many areas, such as operations research, number theory, and statistics. In terms of optimization, this is called an integer feasibility problem. A generalized integer feasibility problem   is to find b such that there does not exist a non-negative integral solution in the system with a given AA. One such problem is the well-known Frobenius problem  . In this paper we study the generalized integer feasibility problem and also the multi-dimensional Frobenius problem. To study a family of systems with no non-negative integer solution, we focus on a commutative semigroup generated by a finite subset of ZdZd and its saturation. An element in the difference between the semigroup and its saturation is called a “hole”. We show the necessary and sufficient conditions for the finiteness of the set of holes. Also we define fundamental holes and saturation points of a commutative semigroup. Then, we show the simultaneous finiteness of the set of holes, the set of non-saturation points, and the set of generators for saturation points. As examples we consider some three- and four-way contingency tables from statistics and apply our results to them. Then we discuss the time complexities of our algorithms.