Problem with binary decision variable constraints in VRP

Question

I would like to create non-linear violation costs in my VRP. I already created my whole VRP with time windows in which I have these decision variable:

dvar float+ w[N][D]; // violation time for late arrivals for every node and every day

These dvars are working, but now I want to make a link with the violation costs decision variables, which are:

dvar boolean a1[N][D];// no violation 
dvar boolean a2[N][D];// soft violation of 0-5 minutes
dvar boolean a3[N][D];// soft violation of 6-10 minutes
dvar boolean a4[N][D];// soft violation of 11 -15 minutes 
dvar boolean a5[N][D];// soft violation of 15+ minutes

I want to force:

a1[N][D] to be 1, when w[N][D] <=0, 0 otherwise
a2[N][D] to be 1, when w[N][D] >0 & <=5, 0 otherwise
a3[N][D] to be 1, when w[N][D] >5 & <=10, 0 otherwise
a4[N][D] to be 1, when w[N][D] >10 & <=15, 0 otherwise
a5[N][D] to be 1, when w[N][D] >=16, 0 otherwise

Then I have:

  forall(i in N, d in D)
  (a1[i][d] + a2[i][d] + a3[i][d] + a4[i][d] + a5[i][d]) == 1;

There is still something wrong with these constraints though.

forall(i in N, d in D)
  (a1[i][d] + a2[i][d] + a3[i][d] + a4[i][d] + a5[i][d]) == 1; //sum of all a's = 1

forall(i in N, d in D)
  w[n][d]<= (5*a2[i][d]) + 1000*(1-a2[i][d]); // a2 == 1 when w[n][d]>0 & <=5

forall(i in N, d in D)
  (6*a3[i][d] - 1000*(a3[i][d]-1))<= w[i][d]; // a3

forall(i in N, d in D)
   w[i][d] <= (10*a3[i][d]) + 1000*(1-a3[i][d]); // a3

forall(i in N, d in D)
  (11*a4[i][d] - 1000*(a4[i][d]-1))<= w[i][d]; //a4

forall(i in N, d in D)
   w[i][d] <= (15*a4[i][d]) + 1000*(1-a4[i][d]); // a4

forall(i in N, d in D)
  (16*a5[i][d] - 1000*(a5[i][d]-1))<= w[i][d]; //a5

it sets a5==1 for all constraints.

Furthermore, w is used in the model as:

forall (i in N, d in D:q[i][d]>=1)
y[i][d] - w[i][d] <= sl[i][d]; // late arrival time soft

where y[i][d] is the arrival time variable and sl the soft time window

RobPratt · Answer 1 · 2020-05-08T14:02:16.423

Here's a stronger formulation that uses the same variables and fewer constraints, assuming $L \le w_{i,d} \le U$: \begin{align} \sum_{k=1}^5 a_{k,i,d} &= 1 &&\text{for all $i$ and $d$}\\ L a_{1,i,d} + 1 a_{2,i,d} + 6 a_{3,i,d} + 11 a_{4,i,d} + 16 a_{5,i,d} &\le w_{i,d} &&\text{for all $i$ and $d$}\\ 0 a_{1,i,d} + 5 a_{2,i,d} + 10 a_{3,i,d} + 15 a_{4,i,d} + U a_{5,i,d} &\ge w_{i,d} &&\text{for all $i$ and $d$} \end{align}

Kuifje · Answer 2 · 2020-05-08T10:45:07.277

3

You can impose $$ a_{nd} + b_{nd} + f_{nd} + g_{nd} =1 $$ And link these variables with $\omega_{nd}$ as follows :

\begin{align*} &\omega_{nd} \le 5 a_{nd} +M(1-a_{nd})\\ 6 b_{nd} - M(1-b_{nd}) \le & \; \omega_{nd} \le 10 b_{nd} +M(1-b_{nd})\\ 11 f_{nd} - M(1-f_{nd}) \le & \; \omega_{nd} \le 15 f_{nd} +M(1-f_{nd}) \\ 16 g_{nd} - M(1-g_{nd}) \le & \; \omega_{nd} \\ \end{align*}

For example, if $\omega_{nd}=1$, only the first constraint will be active with $a_{nd} = 1$.

If $\omega_{nd}=7$, only the second one will be active with $b_{nd} = 1$, and so forth.

edited May 08 '20 at 10:45

answered May 08 '20 at 10:39

Kuifje

13,324
1
23
56

Thanks for your help! I added an extra boolean for the case of w[i][d] == 0. Then I imposed: a1 + a2 + a3 + a4 + a5 == 1 (see changed question). – Jeroen May 08 '20 at 11:21
It is still not working, I wonder what is wrong with the code posted above. – Jeroen May 08 '20 at 11:36
Can you show what is not working ? (what constraint/cost is not properly enforced for example) – Kuifje May 08 '20 at 11:37
It sets a1 == 1 for all nodes and all days and it changes my w[i][d] to my big M value (1000) – Jeroen May 08 '20 at 11:39
Are you sure you have constraints that activate the violation time correctly ? if the violation time takes value $1000$ maybe it is not well defined. – Kuifje May 08 '20 at 11:55
Let me add the other constraints in the question above as well. Maybe that could help? – Jeroen May 11 '20 at 08:18
yes indeed, the more (relevant) information, the better chances to get a good answer. – Kuifje May 11 '20 at 08:39
w[i][d] can be in a range of minumum 0 and 240 maximum – Jeroen May 12 '20 at 09:10
In your last equation, shouldn't it be $y+w \le s$ ? Since $w \ge 0$, it is activated when $y > s$, so you want $y \le s - w$. – Kuifje May 12 '20 at 09:18

score 1 · Answer 3 · answered May 11 '20 at 13:19

You could use logical constraints instead of big M with hard coded 1000

range N=1..2;
range D=1..3;

dvar boolean a1[N][D];
dvar int w[N][D] in -10..10;

subject to
{
// a1[N][D] to be 1, when w[N][D] <=0, 0 otherwise
forall(n in N,d in D) a1[n][d]==(w[n][n] <=0);
}

Problem with binary decision variable constraints in VRP

3 Answers3