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?

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

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

  • $\begingroup$ 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. $\endgroup$ Commented Aug 26, 2020 at 14:20
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Commented Aug 26, 2020 at 15:59
  • $\begingroup$ 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} $\endgroup$ Commented Sep 1, 2020 at 10:29
  • $\begingroup$ If you want to not enforce that implication, just omit the constraint. $\endgroup$
    – RobPratt
    Commented Sep 1, 2020 at 12:49
  • $\begingroup$ Is there any other way to achieve the above? $\endgroup$ Commented Sep 1, 2020 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.