Modulo Integer Programming, $m$ equations $n$ variables

Question

I am following 'Application of Number Theory to Numerical Analysis', and there is a section by G.H. Bradley called 'Modulo Optimization Problems and Integer Linear Programming'. There he explains that turns a modulo integer programming problem into an equivalent integer programming problem.

However, I can't follow one part. Given a modulo integer program $Ax=b \mod k$, we usually turn it into $Ax + Ky = b$, and thus from $m$ equations, $n$ variables we get $m$ equations, $m+n$ variables. He then outlines a procedure so that we only have $n$ variables instead of $m+n$, and this part is a bit unclear to me.

I don't necessarily have to follow Bradley's section, but I do not know much (yet) about operations research books. I would like to ask if someone knows an easier to read book/article where I can find this elimination of variables procedure.

Edit: I misquoted the number of variables and constraint change. It is from $m$ constraints and $n+m$ variables into $n$ variables $n$ constraints. Still very good in some cases.

Answer 1

Very briefly, what Bradley did was to consider $P=\small\begin{bmatrix} A&K\\Id&0 \end{bmatrix}$. We can then find a uni-modular matrix $Q=\small\begin{bmatrix} Q1&Q2\\Q3&Q4 \end{bmatrix}$, where the product $PQ$ will be a matrix in HNF, $PQ=\small\begin{bmatrix} R_1&0\\R_2&H \end{bmatrix}$.

Since $Q$ is uni-modular, we can then perform a substitution $\begin{bmatrix} x\\y\end{bmatrix}=\small\begin{bmatrix} Q1&Q2\\Q3&Q4 \end{bmatrix}\begin{bmatrix} u\\z\end{bmatrix}$.

When we substitute the above equation, we will have:

$$ \small\begin{bmatrix} R_1&0\\R_2&H \end{bmatrix}\begin{bmatrix} u\\z\end{bmatrix} \circ \begin{bmatrix} b\\1\end{bmatrix}, $$

where $\circ$ is an equality for $b$, and $\leq$ for $1$. We have the $\leq$ due to the fact that in Modulo Optimization Problem, $0 \leq x \leq 1$.

From here, we just take $u= R_1^{-1}b$, and substitute. We will see that we have a constant in the objective function that we can ignore, and that we have:

$$ 0 \leq R_2R_1^{-1}b + Hz \leq 1\\ z \ \texttt{integer}. $$

But really the constraints are now $-R_2R_1^{-1}b \leq Hz \leq -R_2R_1^{-1}b + 1$. You can verify that $H$ is $n \times n$. Bradley said that the initial system of modulo equations is consistent (solvable?) if and only if $u=R_1^{-1}b$ is integer, which I haven't figured out why (tho I was exhausted when I was doing this, wasn't really in my best form).