Determine if adding y to x caused x to go over or arrive at a certain interval i

Question

How can I know that, by adding y to x, x has crossed or arrived at an integer value dividable by i?

I might be using the wrong terminology, so let me explain with an example:

Say:

• we have an interval i = 3
• we have a integer variable y = 3
• we have a integer variable x that is the result of x' + y, let's say the current value of x = 5, so the previous value of x x' = 2

Because x went from 2 to 5, x crossed 3, so the condition should be true. The condition should be true whenever x crosses or arrives at the whole number 3 (i), 6 (2i), 9 (3i), 12 (4i), etc. The condition should be false when we do not cross or arrive at a whole number dividable by i (so when x goes from 3 to 5, condition should be false).

The condition I'm using now is (I'm using integer divisions which work as a floor):

floor(x / i) > floor((x - y) / i)

It works, but I have the feeling that it can be simplified. But the floor is making it hard for me. Any help would be appreciated.

Answer 1

We need to clarify what happens if either $x$ or $x'$ is a multiple of $i$. I take it from your use of the floor function that (with $i=3$ and $y=2$, say) you would consider $x$ changing from 4 to 6 to be a crossing but $x$ changing from 6 to 8 not to be a crossing.

Assuming that you can put bounds on $x$ and $y$, you can model this by adding a gaggle of binary variables and big-M constraints. Let's assume that, based on problem information, you know that the only possible multiples of $i$ that could be crossed are $i, 2i, \dots, K i$. Create binary variables $s_k$, $w_k$ and $z_k$ and consider the following constraints (all defined $\forall k\in \{1,\dots,K\}$): $$\begin{eqnarray*} x & \ge & k\cdot i-M(1-z_{k})\\ x & \le & k\cdot i-1+Mz_{k}\\ x' & \ge & k\cdot i-Mw_{k}\\ x' & \le & k\cdot i-1+M(1-w_{k})\\ s_{k} & \le & z_{k}\\ s_{k} & \le & w_{k}\\ s_{k} & \ge & z_{k}+w_{k}-1 \end{eqnarray*} $$ $M$ is a sufficiently large constant (and need not be the same in every constraint; I'm just running low on symbols). The first two constraints ensure $z_k=1\iff x\ge k\cdot i$; the next two ensure $w_k=1\iff x'\lt k\cdot i$. So you have a crossing at $k\cdot i$ if and only if both $z_k$ and $w_k$ are 1. The last two constraints force $s_k=1$ if $z_k=1=w_k$ and $s_k=0$ otherwise.