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

Question

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?

Answer 1

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