Integer programming: Minimize objective $\bmod q$

Question

Assume we have the following objective: $$\min \sum_{i=1}^N (a_i x_i \bmod q)$$ subject to a set of constraints, where the $a_i$ are known and we want to solve for the $x_i$. Is it possible to formulate this via integer programming? Or would this not work because $\bmod q$ is a non-linear objective?

Answer 1

Introduce integer variables $q_i$ and $r_i$ to represent the quotient and remainder, respectively. Now minimize $\sum_i r_i$ subject to linear constraints \begin{align} a_i x_i &= q \cdot q_i + r_i \\ q_i &\ge 0 \\ 0 \le r_i &\le q - 1 \end{align} and your other constraints.

---

For your modified objective, instead introduce integer variables $q_0$ and $r_0$ to represent the quotient and remainder, respectively. Now minimize $r_0$ subject to linear constraints \begin{align} \sum_i a_i x_i &= q \cdot q_0 + r_0 \\ q_0 &\ge 0 \\ 0 \le r_0 &\le q - 1 \end{align} and your other constraints.

Answer 2

Let's start with the first problem -- working modulo $q$, you have infinitely many answers and this set of answers has no minimum.

Consider $2 \pmod{7}$ this is the residue class containing $\{\dots, -19, -12, -5, 2, 9, 16, \dots \}$ Every residue class contains infinitely many members and these collections do not have a minimum.

The usual way to address this is to make a function that takes a residue class and maps it to one of its members. For instance, define $$ \left[ a \pmod{b} \right] = \min \left( (a \pmod{b}) \cap \Bbb{Z}_{\geq 0} \right) \text{,} $$ the least nonnegative member of the residue class. Many people think that this is what happens when working "modulo $b$" anyway, so this is a less surprising choice.

However, it is not the only choice. Sometimes it is preferable to pick the member of the residue class that is closest to $0$, so we would take $5 \pmod{7}$ to $-2$. Which rule one should pick to go from each residue classes to a representative member of that class depends on what you actually want to compute.

W've made progress, now we are trying to minimze a value instead of select a minimum element of a set. Do you want to reduce the residue for each summand then add all those representative up, or add up all the residue classes to get a new residue class, then reduce? (The former can give results much larger than the latter. Both values are in the same residue class.) $$ \min \left[ \sum_i (a_i x_i \pmod{q}) \right] $$ or $$ \min \sum_i \left[ a_i x_i \pmod{q} \right] \text{?} $$ These are not the same thing and the minimum of one is not automatically the minimum of the other.

Having made the above choices, there is now a definite process that produces a definite number that we are trying to minimize. Now we come to part of your Question: Can we apply integer programming?

Yes, we can. You seem to have identified "integer programming" with "integer linear programming". They are not the same thing. (Although, integer linear programming is already NP-hard, so allowing more complicated objectives or more complicated constraints does not produce systems that are solvable in reasonable time.) The nonlinear objective ensures this is not an instance of an integer linear programming problem, but it is an integer programming problem.