MODEL:

SETS:

nodes:y;

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

subtours;

subin(subtours,arcs):aa;

ENDSETS

DATA:

!nodenumber=10;nodenumber=50;
nodes=1..nodenumber;

maxsubtours=30;
subtours=1..maxsubtours;

!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;

!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;

!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;

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

ENDDATA

SUBMODEL MASTER:

[MASTEROBJ]  min=@SUM(arcs: c*x) ;

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

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

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

ENDSUBMODEL

SUBMODEL INTEGER_MASTER:

[INTMASTEROBJ]  min=@SUM(arcs: c*x) ;

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

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

@FOR(arcs:@BIN(x));

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;
@SUM(nodes(i)|i#NE#source:y(i))>1;
@FOR(nodes(i):@BIN(y(i)));
@FOR(arcs(i,j):@BIN(v1(i,j));@BIN(v2(i,j)));

ENDSUBMODEL

CALC:

cutnumb=0;oldcutnumb=-1;
source=1;
! esegue il loop finche' non trova una soluzione che non viola le diseguaglianze di sottocircuito;
@WHILE((cutnumb #GT# oldcutnumb) #AND# (cutnumb #LT#maxsubtours):
    @WHILE((cutnumb #GT# oldcutnumb) #AND# (cutnumb #LT#maxsubtours):
         @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));
         oldcutnumb=cutnumb; 
         @DIVERT( 'LINGO.LOG');
         @SOLVE(CUT_GENERATOR) ;
         @DIVERT();
         @IFC(mincut #LT# 2 :
                    cutnumb = cutnumb + 1;
                    @WRITE('mincut = ',mincut,@NEWLINE(1));
                    @FOR(arcs(i,j):aa(cutnumb,i,j)=@ABS(y(i)-y(j)));
              );
        );
     @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));
     oldcutnumb=cutnumb; 
     @DIVERT( 'LINGO.LOG');
     @SOLVE(CUT_GENERATOR) ;
     @DIVERT();
     @IFC(mincut #LT# 2 :
          cutnumb = cutnumb + 1;
          @WRITE('mincut = ',mincut,@NEWLINE(1));
          @FOR(arcs(i,j):aa(cutnumb,i,j)=v1(i,j)+v2(i,j));
          );
    );
@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))));
!@WRITE('Final Integer Master Problem value = ',INTMASTEROBJ,@NEWLINE(1));
!@FOR(arcs(i,j):@IFC(x(i,j)#GT# 0:@WRITE('(',i,',',j,')-> ',x(i,j),@NEWLINE(1))));

ENDCALC

END