5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Ok, so now I have an understanding how the described algorithm works, but a more detailed explanation would still be very nice. $\endgroup$ May 1 at 15:50
  • $\begingroup$ Can you see that Ax = b mod K = b - K floor(b/K) = b - Ky ? $\endgroup$ May 3 at 1:26
  • $\begingroup$ Concerning the procedure with only n variables, I am curious to know about it. $\endgroup$ May 3 at 1:27
  • 1
    $\begingroup$ @MatheusDiógenesAndrade no, it is not the method that you are describing. Bradley turned an augmented matrix into Hermite Normal Form, and turns out we can eliminate some variables this way. $\endgroup$ May 3 at 9:13
  • $\begingroup$ Thanks, @AyamGorendPedes. For those interesting in reading the cited chapter, follows a link (archive.org/details/applicationsofnu00zare/page/432/mode/2up). $\endgroup$ May 3 at 18:36

1 Answer 1

2
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ There are still some holes for me to fill in, as I do not have a 100% understanding of the algorithm yet. However, if one follows his technique to the letter then the algorithm is correct. I tried it, it worked. $\endgroup$ May 3 at 18:03
  • $\begingroup$ It works if one is careful with the size of $Q$. $\endgroup$ May 3 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.