# Minimize binary variable's distance with respect to the index values

For a given binary decision variable $$x[i,j,k]$$ my goal is to get as dense results in terms of k for successive values of j. Distance of k value to be kept as close as possible throughout j values:

$$d = \sum_{j=2}^n (|k\cdot x[1,j,k] - k\cdot x[1,j-1,k]) + |k\cdot x[1,n,k] - k\cdot x[1,1,k]|$$

e.g $$i = 1$$

j | 1 2 3 4 5

k | 3 3 3 3 3 - is the optimal, d = 0

k | 5 4 4 5 4 - is good enough d = 4

k | 1 6 9 2 5 - not good d = 22

How is that even possible to add this in the objective function since absolute function is introduced and linearity is diminished?

• Do you have constraints $\sum_k x_{i,j,k}=1$ for each $i$ and $j$? – RobPratt Aug 3 '20 at 12:29
• Yes I do have, $\sum_{k}x_{i,j,k} <= 1$ for each $i$ and $j$ – Psyndrom Ventura Aug 3 '20 at 12:54

Introduce a variable $$y_{i,j}$$ to represent $$\left|\sum_k k x_{i,j,k}-\sum_k k x_{i,j-1,k}\right|,$$ together with constraints \begin{align} y_{i,j} &\ge \sum_k k x_{i,j,k}-\sum_k k x_{i,j-1,k} &&\text{for all i and j} \\ y_{i,j} &\ge -\sum_k k x_{i,j,k}+\sum_k k x_{i,j-1,k} &&\text{for all i and j} \end{align} The objective is to minimize $$\sum_{i,j} y_{i,j}$$.
Alternatively, you might consider minimizing the range $$\sum_i \left(\max_j \sum_k k x_{i,j,k} - \min_j \sum_k k x_{i,j,k}\right),$$ which you can linearize with variables $$v_i$$ and $$w_i$$ and constraints \begin{align} v_i &\ge \sum_k k x_{i,j,k} &&\text{for all i and j} \\ w_i &\le \sum_k k x_{i,j,k} &&\text{for all i and j} \\ \end{align} The objective is to minimize $$\sum_i (v_i - w_i)$$.
• I have not managed to get a solution yet... I guess decision variables ($y_{i,j}$, $v_{i}$, $w_{i}$) should be integer but I'm not sure what their boundies should be. If I run the first suggestion it runs forever, if I use a different objective (minimize number of i) with the same constrains, $y_{i,j}$ get the upper bound consistently. What I am thinking is that there are many combinations capable to produce the minimum objective especially if I add the same constraints for last - first day (introducing circularity), I assume I should penalize any switch on top of minimizing distance. – Psyndrom Ventura Aug 26 '20 at 14:20
• You can relax $y,v,w$ to be nonnegative and they will automatically take integer values. Because $\sum_k x_{i,j,k} \le 1$, all of them are bounded above by $k$. – RobPratt Aug 26 '20 at 15:59
• In case that I want to discard any changes from $x_{i,j,k} = 1$ -> $x_{i,j+1,k} = 0$ is it sufficient to add extra constraints that automatically translate those cases as zero change:\begin{align} y_{i,j} &\ge \sum_k x_{i,j,k}-\sum_k x_{i,j-1,k} -2 &&\text{for all $i$ and $j$} \end{align} – Psyndrom Ventura Sep 1 '20 at 10:29