MODEL:

SETS:

nodes:y,p,z,zz;

arcs(nodes,nodes)|&1#LT#&2:x,c,cap1,cap2,v1,v2;

subtours;

subinaa(subtours,arcs):aa;
subinbb(subtours,nodes):bb;

ENDSETS

DATA:

nodenumber=40;
nodes=1..nodenumber;

maxsubtours=40;
subtours=1..maxsubtours;

!dati per  10 nodi;

 !c =      4  7 10 20  9  10 15 10  11
             5  7 15  5   4 11  7  14
                7 10  6   6  9 12  10
                   6  9  13 10  9   4
                     12  13  9 11   7
                          6 14 15  20
                            10  7   8
                                5  13
                                    2;

!p= 0 4 8 3 9 8 3 6 7 20;

!dati per 30 nodi;

!c= 47, 61, 50, 54, 43, 50, 54, 43, 70, 26, 32, 52, 20, 24, 63, 23, 29, 57, 47, 
38, 31, 62, 62, 16, 8, 26, 85, 13, 55, 22, 35, 90, 13, 69, 56, 69, 57, 72, 
42, 75, 37, 46, 52, 69, 66, 23, 89, 57, 29, 16, 40, 59, 55, 55, 68, 59, 36, 
56, 110, 18, 91, 78, 90, 78, 88, 64, 97, 57, 67, 73, 81, 73, 42, 107, 58, 33, 
22, 60, 76, 69, 60, 87, 72, 57, 70, 46, 41, 23, 45, 24, 66, 22, 48, 30, 32, 
17, 72, 78, 19, 74, 79, 53, 39, 12, 51, 54, 71, 37, 63, 6, 93, 32, 53, 25, 
75, 35, 50, 25, 53, 43, 69, 53, 71, 87, 14, 89, 84, 103, 80, 37, 48, 77, 86, 
53, 75, 75, 66, 73, 69, 70, 48, 81, 40, 50, 63, 63, 58, 37, 89, 45, 18, 26, 
53, 58, 51, 45, 81, 54, 48, 21, 10, 43, 47, 27, 7, 37, 28, 37, 62, 76, 60, 
41, 88, 73, 78, 49, 38, 48, 77, 54, 57, 45, 29, 22, 61, 22, 29, 35, 30, 16, 
72, 83, 42, 61, 89, 69, 62, 28, 48, 55, 80, 34, 65, 26, 51, 37, 26, 9, 33, 
23, 45, 52, 68, 63, 32, 81, 69, 79, 55, 29, 40, 69, 63, 48, 50, 82, 38, 50, 
50, 48, 7, 91, 99, 36, 83, 102, 77, 57, 18, 68, 74, 94, 14, 83, 21, 44, 45, 
38, 34, 74, 18, 36, 79, 24, 55, 57, 87, 79, 15, 18, 43, 95, 20, 72, 33, 13, 
10, 31, 52, 61, 37, 52, 67, 48, 53, 34, 30, 35, 57, 53, 44, 28, 41, 32, 45, 
61, 76, 67, 35, 90, 77, 85, 57, 38, 49, 78, 61, 57, 53, 9, 43, 41, 48, 41, 
51, 54, 36, 51, 43, 23, 24, 44, 65, 32, 36, 41, 42, 52, 46, 44, 61, 45, 59, 
44, 19, 25, 50, 62, 34, 38, 83, 92, 32, 77, 95, 70, 53, 15, 60, 66, 86, 22, 
75, 16, 18, 81, 41, 39, 47, 85, 84, 24, 17, 28, 105, 10, 78, 83, 59, 22, 40, 
82, 90, 38, 28, 13, 114, 19, 83, 90, 78, 50, 21, 18, 64, 64, 73, 45, 71, 16, 
79, 79, 103, 85, 31, 40, 67, 95, 44, 80, 28, 72, 89, 53, 42, 12, 116, 35, 83, 
43, 63, 47, 38, 27, 90, 39, 57, 39, 73, 70, 70, 66, 75, 37, 64, 67, 82, 28, 
75, 6, 11, 41, 82, 18, 57, 30, 88, 9, 60, 108, 23, 76, 97, 33, 68;

!p=0, 18, 6, 42, 3, 21, 29, 36, 27, 4, 37, 29, 28, 4, 37, 12, 2, 38, 27, 13,
16, 17, 17, 15, 6, 31, 44, 37, 33, 46;

! dati per 40 nodi;

c=47, 61, 50, 54, 43, 50, 54, 43, 70, 26, 32, 52, 20, 24, 63, 23, 29, 57, 47, 
38, 31, 62, 62, 16, 8, 26, 85, 13, 55, 63, 31, 58, 33, 20, 46, 35, 74, 39, 
60, 22, 35, 90, 13, 69, 56, 69, 57, 72, 42, 75, 37, 46, 52, 69, 66, 23, 89, 
57, 29, 16, 40, 59, 55, 55, 68, 59, 36, 100, 41, 29, 78, 27, 13, 37, 65, 60, 
72, 56, 110, 18, 91, 78, 90, 78, 88, 64, 97, 57, 67, 73, 81, 73, 42, 107, 58, 
33, 22, 60, 76, 69, 60, 87, 72, 57, 120, 44, 49, 95, 44, 34, 38, 86, 82, 94, 
70, 46, 41, 23, 45, 24, 66, 22, 48, 30, 32, 17, 72, 78, 19, 74, 79, 53, 39, 
12, 51, 54, 71, 37, 63, 6, 78, 64, 13, 70, 35, 22, 63, 30, 36, 40, 93, 32, 
53, 25, 75, 35, 50, 25, 53, 43, 69, 53, 71, 87, 14, 89, 84, 103, 80, 37, 48, 
77, 86, 53, 75, 10, 85, 83, 29, 66, 82, 89, 72, 33, 41, 75, 66, 73, 69, 70, 
48, 81, 40, 50, 63, 63, 58, 37, 89, 45, 18, 26, 53, 58, 51, 45, 81, 54, 48, 
103, 30, 42, 77, 26, 25, 25, 77, 66, 81, 21, 10, 43, 47, 27, 7, 37, 28, 37, 
62, 76, 60, 41, 88, 73, 78, 49, 38, 48, 77, 54, 57, 45, 39, 79, 55, 46, 51, 
58, 81, 40, 11, 12, 29, 22, 61, 22, 29, 35, 30, 16, 72, 83, 42, 61, 89, 69,
62, 28, 48, 55, 80, 34, 65, 26, 60, 77, 36, 62, 47, 44, 77, 21, 22, 17, 51, 
37, 26, 9, 33, 23, 45, 52, 68, 63, 32, 81, 69, 79, 55, 29, 40, 69, 63, 48, 
50, 33, 73, 59, 36, 48, 59, 75, 49, 8, 22, 82, 38, 50, 50, 48, 7, 91, 99, 36, 
83, 102, 77, 57, 18, 68, 74, 94, 14, 83, 21, 81, 88, 29, 83, 58, 44, 87, 8, 
44, 35, 44, 45, 38, 34, 74, 18, 36, 79, 24, 55, 57, 87, 79, 15, 18, 43, 95, 
20, 72, 43, 54, 78, 7, 45, 69, 59, 82, 39, 59, 33, 13, 10, 31, 52, 61, 37, 
52, 67, 48, 53, 34, 30, 35, 57, 53, 44, 28, 59, 55, 34, 48, 26, 32, 56, 41, 
18, 33, 41, 32, 45, 61, 76, 67, 35, 90, 77, 85, 57, 38, 49, 78, 61, 57, 53, 
31, 82, 62, 43, 56, 65, 84, 47, 15, 16, 9, 43, 41, 48, 41, 51, 54, 36, 51, 
43, 23, 24, 44, 65, 32, 36, 62, 42, 40, 42, 14, 31, 44, 54, 26, 45, 41, 42, 
52, 46, 44, 61, 45, 59, 44, 19, 25, 50, 62, 34, 38, 53, 51, 44, 38, 24, 38, 
53, 51, 17, 36, 83, 92, 32, 77, 95, 70, 53, 15, 60, 66, 86, 22, 75, 16, 76, 
81, 25, 76, 51, 39, 80, 13, 38, 32, 18, 81, 41, 39, 47, 85, 84, 24, 17, 28, 
105, 10, 78, 61, 41, 81, 24, 43, 69, 47, 93, 52, 73, 83, 59, 22, 40, 82, 90, 
38, 28, 13, 114, 19, 83, 79, 30, 84, 42, 44, 69, 36, 103, 66, 87, 90, 78, 50, 
21, 18, 64, 64, 73, 45, 71, 16, 96, 62, 7, 83, 38, 13, 59, 44, 54, 59, 79, 
79, 103, 85, 31, 40, 67, 95, 44, 80, 20, 77, 87, 17, 63, 83, 82, 81, 39, 52, 
28, 72, 89, 53, 42, 12, 116, 35, 83, 98, 16, 82, 62, 43, 64, 20, 107, 77, 98, 
43, 63, 47, 38, 27, 90, 39, 57, 94, 12, 54, 64, 22, 36, 9, 83, 62, 81, 39, 
73, 70, 70, 66, 75, 37, 112, 56, 28, 93, 42, 20, 51, 65, 71, 79, 64, 67, 82, 
28, 75, 6, 88, 74, 11, 82, 46, 27, 72, 26, 47, 46, 11, 41, 82, 18, 57, 47, 
47, 63, 19, 31, 54, 51, 69, 28, 49, 30, 88, 9, 60, 57, 37, 64, 25, 27, 53, 
42, 76, 38, 59, 108, 23, 76, 86, 16, 76, 50, 36, 59, 22, 98, 66, 87, 97, 33, 
92, 101, 39, 97, 72, 56, 100, 14, 57, 45, 68, 62, 34, 71, 27, 33, 59, 40, 85, 
47, 68, 83, 68, 10, 76, 40, 23, 66, 29, 42, 43, 95, 92, 37, 76, 92, 99, 78, 
42, 47, 66, 61, 30, 48, 6, 93, 68, 87, 82, 40, 18, 63, 37, 50, 53, 51, 74, 
67, 83, 39, 58, 26, 30, 64, 41, 59, 46, 52, 50, 60, 93, 70, 89, 44, 31, 21;

p=0, 18, 6, 42, 3, 21, 29, 36, 27, 4, 37, 29, 28, 4, 37, 12, 2, 38, 27, 13,
16, 17, 17, 15, 6, 31, 44, 37, 33, 46, 10, 12, 17, 28, 42, 43, 24, 25, 7, 19;

ENDDATA

SUBMODEL MASTER:

[MASTEROBJ]  min=@SUM(arcs: c*x) -@SUM(nodes:p*z);

@FOR(nodes(i):@SUM(arcs(i,j):x(i,j))+@SUM(arcs(j,i):x(j,i)) = 2*z(i) );
z(1)=1;

@FOR(subtours(h)|h#LE#cutnumb:   @SUM(arcs(i,j):aa(h,i,j)*x(i,j) ) > 2*@SUM(nodes(i):bb(h,i)*z(i))
     );

@FOR(arcs:@BND(0,x,1));
@FOR(nodes:@BND(0,z,1));

ENDSUBMODEL

SUBMODEL INTEGER_MASTER:

[INTMASTEROBJ]  min=@SUM(arcs: c*x) -@SUM(nodes:p*z);

@FOR(nodes(i):@SUM(arcs(i,j):x(i,j))+@SUM(arcs(j,i):x(j,i)) = 2*z(i) );
z(1)=1;

@FOR(subtours(h)|h#LE#cutnumb:   @SUM(arcs(i,j):aa(h,i,j)*x(i,j) ) > 2*@SUM(nodes(i):bb(h,i)*z(i))
     );

@FOR(arcs:@BIN(x));
@FOR(nodes:@Bin(z));

ENDSUBMODEL

SUBMODEL CUT_GENERATOR:

[mincut] MIN= @SUM(arcs(i,j):v1(i,j)*cap1(i,j)+v2(i,j)*cap2(i,j));

@FOR(arcs(i,j): v1(i,j) > y(j)-y(i); v2(i,j)>y(i)-y(j));

y(source)=0;
y(sink)=1;

ENDSUBMODEL

CALC:

cutnumb=0;oldcutnumb=-1; tolerance=0.00001;
source=1;
@WHILE((cutnumb #GT# oldcutnumb) #AND# (cutnumb #LT#30):
	sink=source;
	@DIVERT( 'LINGO.LOG');
	@SOLVE(MASTER);
	@DIVERT();
	@WRITE('Master Problem value = ',MASTEROBJ,@NEWLINE(1));
	@FOR(arcs(i,j):cap1(i,j)=x(i,j);cap2(i,j)=x(i,j));
	@FOR(nodes(i):zz(i)=z(i));
	notfound=1;
	oldcutnumb=cutnumb; 
	@WHILE((notfound#EQ#1) #AND#  (sink#LT# nodenumber):  
		sink=sink+1;
  		@IFC(zz(sink) #GT# 0:
    			@DIVERT( 'LINGO.LOG');
    			@SOLVE(CUT_GENERATOR) ;
    			@DIVERT();
    			@IFC(mincut #LT# (2*zz(sink)-tolerance) :
                  	notfound=0;
                  	cutnumb = cutnumb + 1;
                  	@WRITE('mincut ',mincut,' between ',source,' and ',sink,' with z= ',zz(sink),@NEWLINE(1));
                 	@FOR(arcs(i,j):aa(cutnumb,i,j)=v1(i,j)+v2(i,j));
                 	@FOR(nodes(i): bb(cutnumb,i)=0);bb(cutnumb,sink)=1;
         		);
  		); 
	);
);
@DIVERT( 'LINGO.LOG');
@SOLVE(MASTER);
@DIVERT();
@WRITE('Final Relaxed Master Problem value = ',MASTEROBJ,@NEWLINE(1));

oldcutnumb=cutnumb-1;
@WHILE((cutnumb #GT# oldcutnumb) #AND# (cutnumb #LT#30):
	sink=source;
	@DIVERT( 'LINGO.LOG');
	@SOLVE(INTEGER_MASTER);
	@DIVERT();
	@WRITE('Integer Master Problem value = ',INTMASTEROBJ,@NEWLINE(1));
	@FOR(arcs(i,j):cap1(i,j)=x(i,j);cap2(i,j)=x(i,j));
	notfound=1;
	oldcutnumb=cutnumb; 
	@WHILE((notfound#EQ#1) #AND#  (sink#LT# nodenumber):  
		sink=sink+1;
  		@IFC(zz(sink) #GT#  0:
    			@DIVERT( 'LINGO.LOG');
    			@SOLVE(CUT_GENERATOR) ;
    			@DIVERT();
    			@IFC(mincut #LT# (2*zz(sink)-tolerance) :
                  	notfound=0;
                  	cutnumb = cutnumb + 1;
                  	@WRITE('mincut ',mincut,' between ',source,' and ',sink,@NEWLINE(1));
                 	@FOR(arcs(i,j):aa(cutnumb,i,j)=v1(i,j)+v2(i,j));
                  	@FOR(nodes(i): bb(cutnumb,i)=0);bb(cutnumb,sink)=1;
         		);
   		);
	);
);
@DIVERT( 'LINGO.LOG');
@SOLVE(INTEGER_MASTER);
@DIVERT();
@WRITE('Final Integer Master Problem value = ',INTMASTEROBJ,@NEWLINE(1));
@FOR(arcs(i,j):@IFC(x(i,j)#GT# 0:@WRITE('(',i,',',j,')',@NEWLINE(1))));

ENDCALC

END