Computing holes in semi-groups and its applications to transportation problems

Raymond Hemmecke, Akimichi Takemura, Ruriko Yoshida

Abstract


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 $\Z^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\times 4\times 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$.

Full Text:

PDF


PID: http://hdl.handle.net/10515/sy5t14v39

Contributions to Discrete Mathematics. ISSN: 1715-0868