2 %> Write the Traveling Salesman Problem (TSP) as an integer optimization problem in standard form. See Section 25.2.3 of \cite Bier15-book
4 %> @note Tested with \ref run2512.m
5 %> @note Tested with \ref run2703.m
7 %> @author Michel Bierlaire
8 %> @date Tue Apr 14 10:42:27 2015
12 %> Write the TSP as an integer optimization problem in standard form
13 %> @param dist distance matrix
18 if (columns(dist) != n)
19 error(
"Distance matrix must be square") ;
22 % Numbering of variables
24 vtype1 = repmat('I',1,n*(n-1)) ;
25 % n(n-1) + 1 --> n(n-1) + n-1 u_i (for the subtour elimination constraint)
26 vtype2 = repmat('I',1,n-1) ;
27 % n(n-1) + n-1 + 1 --> n(n-1) + n-1 + n(n-1) slack variables for x_ij <= 1
28 vtype3 = repmat('C',1,n*(n-1)) ;
29 % n(n-1) + n-1 + n(n-1) + 1 --> n(n-1) + n-1 + n(n-1) + (n-1)*(n-2) slack variables for subrout constraints
30 vtype4 = repmat('C',1,(n-1)*(n-2)) ;
31 vtype = [vtype1 vtype2 vtype3 vtype4] ;
33 indices = zeros(size(dist)) ;
38 indices(i,j) = index ;
43 numberOfVariables = (n-1) * (3*n-1) ;
47 c = zeros(numberOfVariables,1) ;
51 c(indices(i,j))= dist(i,j) ;
57 % Each city has exactly one predecessor
58 A1 = zeros(n,numberOfVariables) ;
60 ctype1 = repmat('S',1,n) ;
64 A1(j,indices(i,j)) = 1 ;
69 % Each city has exactly one successor
70 A2 = zeros(n,numberOfVariables) ;
72 ctype2 = repmat('S',1,n) ;
76 A2(i,indices(i,j)) = 1 ;
83 A3 = zeros((n-1)*(n-2),numberOfVariables) ;
84 b3 = zeros((n-1)*(n-2),1) ;
85 ctype3 = repmat('S',1,(n-1)*(n-2)) ;
90 A3(index,n*(n-1) + i-1) = 1 ;
91 A3(index,n*(n-1) + j-1) = -1 ;
92 A3(index,indices(i,j)) = n-1 ;
93 A3(index,n*(n-1) + n-1 + n*(n-1) + index) = 1 ;
102 A4 = zeros(n*(n-1),numberOfVariables) ;
103 b4 = ones(n*(n-1),1) ;
104 ctype4 = repmat('S',1,n*(n-1)) ;
108 A4(indices(i,j),indices(i,j)) = 1 ;
109 A4(indices(i,j),n * (n-1) + n + indices(i,j)-1) = 1 ;
115 A = [A1 ; A2 ; A3 ; A4] ;
116 b = [b1 ; b2 ; b3 ; b4] ;
119 lb = zeros(numberOfVariables,1) ;
120 ub = 1000*ones(numberOfVariables,1) ;
121 ctype = [ctype1 ctype2 ctype3 ctype4] ;
122 [x_min,tot_cost,errnum,extra] = glpk(c,A,b,lb,ub,ctype,vtype,1) ;
126 if (x_min(indices(i,j)) == 1)
127 printf("%d --> %d\n",i,j)
133 printf("%d cities\n",n) ;
134 printf("Total cost: %f\n",tot_cost) ;
140 if (x_min(indices(currentcity,j)) == 1)
142 tour = [tour ; currentcity ] ;
147 until(currentcity == 1)
function tspExact(in dist)
Write the TSP as an integer optimization problem in standard form.