On Solving Linear Diophantine Constraints

Ana Paula Tomás

Departamento de Ciência de Computadores & LIACC
Faculdade de Ciências, Universidade do Porto
Rua do Campo Alegre, 823, 4150-180 Porto, Portugal

March 1997


Abstract

This thesis is devoted to the study of algorithms that find a finite complete representation of the solution set of a system of linear Diophantine constraints over nonnegative integers. It presents the main results from our research, also giving a brief survey of previous relevant work on this theme. In the first part we describe two new algorithms for finding the minimal solutions of a system of homogeneous equations, so-called Slopes algorithm and Rectangles algorithm, the latter being a variant of the former. These algorithms compute the set of the minimal solutions in a monotonic way by exploring the faces of the cone of real nonnegative solutions of the system in increasing order of dimension. Their mathematical foundations consist of two major results. We give an exact characterization of the positive solutions $(X,y,z)$ of the system $aX=By+Cz+V$, that are minimal in the component-wise ordering, being $a\in
\mbox{\kern.1em \vrule width.04em height1.62ex
depth-0ex \kern-.02em \sf N}\backslash\{0\}$, $B,C\in \mbox{\kern.1em \vrule width.04em height1.62ex
depth-0ex \kern-.02em \sf N}^m$, $V\in\mbox{\sf Z\kern-.42em Z}^m$, and the variables $X\in\mbox{\kern.1em \vrule width.04em height1.62ex
depth-0ex \kern-.02em \sf N}^m$, $y,z\in\mbox{\kern.1em \vrule width.04em height1.62ex
depth-0ex \kern-.02em \sf N}$. We noticed and give a constructive proof of the fact that any system of Diophantine equations $AX=0$ whose solution cone has a $p$-dimensional face $\cal F$ with $p$ extremal rays is equivalent to $\;aX_1 = {\cal A}_{11}X_3+{\cal A}_{12} X_4\;\; \wedge \;\; aX_2 =
{\cal A}_{22} X_4 $, where ${\cal A}_{11}$ has $p$ columns and only nonnegative coefficients, $a>0$, and the variables are exactly the same as those of the given system, being $\mbox{support }{\cal F}=
\{i \;\vert\; \mbox{$x_i$\ occurs in $X_1$\ or $X_3$}\}$. As a consequence, the minimal solutions in any $2$-dimensional face are computed by the algorithms without generating superfluous candidate solutions. When exploring the interior of faces of higher dimensions, $X_4$ is given values through enumeration, so to reduce the problem to problems of the form $aX=By+Cz+V$. From the latter result we deduce a sufficient condition for the set of minimal solutions to be the set of minimal nonnegative integral tuples satisfying a system of congruences. In sum, this work suggests that the use of the geometric structure of solution set is a step towards identifying classes of problems for which one of the algorithms may be more adequate than the others. In addition, it may lead to improvements of the search strategy, for instance by providing sharper bounds on the minimal solutions. On the second part of this thesis, we study extensions of the Elliott-MacMahon algorithm for solving general linear Diophantine constraints. These extensions compute a finite unambiguous decomposition of the solution set. Further investigation on these methods is due, aiming at finding a simpler decomposition, and at solving several constraints at once rather than one at a time.