5

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?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Psyndrom Ventura
  • 315
  • 1
  • 7

1 Answers1

3

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 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 01 '20 at 10:29
  • If you want to not enforce that implication, just omit the constraint. – RobPratt Sep 01 '20 at 12:49
  • Is there any other way to achieve the above? – Psyndrom Ventura Sep 01 '20 at 13:00
  • I don't want this kind of changes to affect the objective function that's why I am asking.. – Psyndrom Ventura Sep 01 '20 at 13:08
  • If you omit the second $y_{i,j} \ge$ constraint I proposed, the same objective function $\sum_{i,j} y_{i,j}$ will penalize occurrences of $(x_{i,j-1,k},x_{i,j,k})=(0,1)$ only. – RobPratt Sep 01 '20 at 14:24