Page 1 of 1

How to make subset of set in GAMS (A FLOW BASED FORMULATION of CVRP.

Posted: Tue Nov 14, 2017 12:19 pm
by figura
Hello,
I've got an issue about adding a constraint (subtour elimination) in GAMS from A FLOW BASED FORMULATION of CVRP.
The binary decision variable x(rij) is defined to indicate if the vehicle r, r ∈ {1, 2, . . . , p} traverses an arc (i, j) in an optimal solution.
I need to define subset S of set {1,...,n} from constraint (6) ->
Σ Σ Σ x(rij) ≤ |S|−1 ∀S ⊆ {1,...,n}
r=1 i∈S j∈S,i≠j

The integer linear programming model of the CVRP: Minimize:
p n n
Σ Σ Σ c(ij) x(rij) -> (1)
r=1 i=0 j=0,i≠j
Subject to
p n
Σ Σ x(rij)=1, ∀j ∈ {1,...,n} ->(2)
r=1 i=0,i≠j

n
Σ x(r0j)=1, ∀r ∈ {1,...,p}, -> (3)
j=1

n n
Σ x(rij)= Σ x(rji), ∀j ∈ {0,...,n}, r ∈ {1,...,p}, -> (4)
i=0, i≠j i=0

n n
Σ Σ d(j)x(rij)≤ Q, ∀r ∈ {1,...,p}, -> (5)
i=0 j=1,i≠j

p
Σ Σ Σ x(rij) ≤ |S|−1 ∀S ⊆ {1,...,n} -> (6)
r=1 i∈S j∈S,i≠j

xrij ∈{0,1}, ∀r ∈ {1,...,p}, i,j ∈ {0,...,n},i≠ j. -> (7)
I hope, that it is possible to make it in GAMS. This is my formulation in GAMS (I tried to make it with adding sets manually), but it doesnt working (because subtour elimination doeasn't working).
$title CRZP (flow based).
Sets
i /0*4/
subi(i) /1*4/
r /1*4/
alias (i,j)
alias (subi,subj);
Sets offdiag0(i,j)
offdiag1(i,j)
offdiag2(i,j)
offdiag3(i,j)
offdiag4(i,j);

offdiag0(i,j)=yes;
offdiag0(i,i)=no;
offdiag1(i,j)=offdiag0(i,j);
offdiag1(i,'0')=no;
offdiag1('0',j)=no;
offdiag2(i,j)=offdiag1(i,j);
offdiag2(i,'1')=no;
offdiag2('1',j)=no;
offdiag3(i,j)=offdiag2(i,j);
offdiag3(i,'2')=no;
offdiag3('2',j)=no;
offdiag4(i,j)=offdiag3(i,j);
offdiag4(i,'3')=no;
offdiag4('3',j)=no;

display offdiag1, offdiag2;
Table d(i,j)
0 1 2 3 4
0 0 1 2 2 4
1 1 0 3 3 5
2 2 3 0 4 6
3 2 3 4 0 2
4 4 5 6 2 0;
Parameters q(j) /1 5,2 5,3 4,4 5/;
parameter g / 20 /;
Binary variables x(i,j,r);
Free variable f;
Equations
ohr1(j),ohr2(r),ohr3(j,r),ohr4(r),ohrx1,ohrx2,ohrx3,ohrx4,ucel;
ucel.. f=e=sum((i,j,r),d(i,j)*x(i,j,r)$offdiag0(i,j));
ohr1(subj(j)).. sum((i,r),x(i,j,r)$offdiag0(i,j))=e=1;
ohr2(r).. sum(j,x('0',j,r))=e=1;
ohr3(j,r).. sum(i,x(i,j,r)$offdiag0(i,j))=e= sum(i,x(j,i,r)$offdiag0(i,j));
ohr4(r).. sum((i,j),q(j)*x(i,j,r)$offdiag0(i,j))=l=g;
ohrx1.. sum((r,i,j)$offdiag1(i,j),x(i,j,r))=l=3;
ohrx2.. sum((r,i,j)$offdiag2(i,j),x(i,j,r))=l=2;
ohrx3.. sum((r,i,j)$offdiag3(i,j),x(i,j,r))=l=1;
ohrx4.. sum((r,i,j)$offdiag4(i,j),x(i,j,r))=l=0;
Model fsvrp /all/;
Solve fsvrp using mip minimizing f;
display x.l,f.l;

Thank you for any help. :)