0

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.

Housy
  • 123
  • To be perfectly honest, $\lfloor\frac{x}{i}\rfloor\gt\lfloor\frac{x-y}{i}\rfloor$ looks simple enough. In some languages you would have an integer division operator (e.g. 'div') so you can write it as $x\operatorname{div}i \gt (x-y)\operatorname{div}i$ - the same formula. It is also understandable to a fellow programmer, which is in software development a bigger asset than being succint. –  Dec 12 '17 at 13:31

1 Answers1

0

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.

prubin
  • 4,923