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
    Aug 3 '20 at 12:29
  • $\begingroup$ Yes I do have, $ \sum_{k}x_{i,j,k} <= 1$ for each $i$ and $j$ $\endgroup$ 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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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