On Fri, 9 Mar 2007, Andrew Makhorin wrote:
To check the tspsol's result you can solve your tsp with Concorde by
submitting it to the NEOS server:
http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html
I ended up with installing Concorde and running some examples.
What I came up with is the following:
tspsol prints the correct objective function in the .out-file, but the
solution provided seems to be the earlier obtained solution.
hod 326% /usr/local/bin/tspsol example1_0_1.tsp -o example1_0_1.out
tsp_read_data: reading TSP data from `example1_0_1.tsp'...
tsp_read_data: NAME: example1_0_1
tsp_read_data: TYPE: TSP
tsp_read_data: COMMENT: Generated by generatetsp.m [EMAIL PROTECTED]
tsp_read_data: DIMENSION: 41
tsp_read_data: EDGE_WEIGHT_TYPE: EXPLICIT
tsp_read_data: EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
tsp_read_data: 49 lines were read
Initial tour length: 4.65e+08
Solving initial LP relaxation...
lpx_adv_basis: size of triangular part = 40
0: objval = 3.740000000e+08 infeas = 1.000000000e+00 (0)
1: objval = 4.650000000e+08 infeas = 0.000000000e+00 (1)
* 1: objval = 4.650000000e+08 infeas = 0.000000000e+00 (1)
* 2: objval = 4.650000000e+08 infeas = 0.000000000e+00 (0)
FOUND OPTIMAL SOLUTION TO LP RELAXATION
Integer optimization begins...
+ 2: ip_obj = 4.650000000e+08 >= -inf (1; 0)
+ 262: ip_obj = 4.630000000e+08 >= 4.630000000e+08 (4; 0)
lpx_print_sol: writing LP problem solution to `example1_0_1.out'...
+ 262: ip_obj = 4.630000000e+08 >= tree is empty (0; 7)
INTEGER OPTIMAL SOLUTION FOUND
When I check this solution it has a cost of 465.
From Concorde (LK-heuristic)
hod 300% ./linkern -o example1_0_1.out
~/glpkmodels/FIRMAC/paperexample2/example1_0_1.tsp
Host: hod.isy.liu.se Current process id: 14421
./linkern -o example1_0_1.out
/home/tde/oscarg/glpkmodels/FIRMAC/paperexample2/example1_0_1.tsp
Chained Lin-Kernighan with seed 1173448614
Problem Name: example1_0_1
Problem Type: TSP
Generated by generatetsp.m [EMAIL PROTECTED]
Number of Nodes: 41
Explicit Lengths (CC_MATRIXNORM)
Using junk-norm nearest code
201 edges
Time to find 8 nearest: 0.00
Grow a Quick-Boruvka tour
Length of Quick-Boruvka Tour: 471000000.00
Time to grow tour: 0.00
linkern ...
Starting Cycle: 471000000
0 Steps Best: 463000000 0.00 seconds
41 Total Steps.
Best cycle length: 463000000
Lin-Kernighan Running Time: 0.16
Final Cycle: 463000000
Total Running Time: 0.16
For which the solution evaluates to 463.
This is true for other problems tested as well, so I guess that at least
occassionally this bug is triggered.
With best regards
Oscar Gustafsson
41 41
0 40 9000000
40 10 11000000
10 30 9000000
30 33 11000000
33 7 9000000
7 34 13000000
34 6 9000000
6 3 12000000
3 37 9000000
37 20 19000000
20 21 16000000
21 19 9000000
19 17 15000000
17 23 9000000
23 14 14000000
14 26 9000000
26 29 13000000
29 11 9000000
11 13 14000000
13 27 9000000
27 8 13000000
8 32 9000000
32 16 13000000
16 24 9000000
24 35 14000000
35 5 9000000
5 38 14000000
38 2 9000000
2 25 18000000
25 15 9000000
15 22 12000000
22 18 9000000
18 12 14000000
12 28 9000000
28 31 14000000
31 9 9000000
9 36 12000000
36 4 9000000
4 1 11000000
1 39 9000000
39 0 10000000
NAME: example1_0_1
TYPE: TSP
COMMENT: Generated by generatetsp.m [EMAIL PROTECTED]
DIMENSION: 41
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
EDGE_WEIGHT_SECTION
0
10000000 0
25000000 24000000 0
14000000 15000000 20000000 0
12000000 11000000 26000000 17000000 0
22000000 23000000 14000000 21000000 23000000 0
17000000 16000000 19000000 12000000 16000000 22000000 0
13000000 14000000 23000000 14000000 14000000 22000000 13000000 0
21000000 22000000 17000000 24000000 20000000 16000000 23000000 19000000 0
15000000 14000000 23000000 16000000 12000000 20000000 15000000 15000000
23000000 0
11000000 12000000 25000000 14000000 12000000 20000000 15000000 11000000
21000000 13000000 0
22000000 21000000 16000000 25000000 19000000 15000000 22000000 22000000
14000000 20000000 22000000 0
14000000 13000000 20000000 15000000 15000000 21000000 16000000 16000000
24000000 14000000 14000000 23000000 0
23000000 22000000 15000000 22000000 20000000 14000000 21000000 23000000
13000000 21000000 23000000 14000000 24000000 0
20000000 21000000 16000000 21000000 21000000 17000000 22000000 22000000
14000000 24000000 22000000 13000000 23000000 16000000 0
18000000 17000000 18000000 17000000 17000000 19000000 14000000 16000000
20000000 16000000 16000000 21000000 15000000 20000000 21000000 0
21000000 22000000 17000000 20000000 20000000 14000000 21000000 19000000
13000000 21000000 19000000 16000000 22000000 13000000 16000000 22000000 0
17000000 18000000 17000000 18000000 20000000 14000000 21000000 21000000
17000000 21000000 19000000 16000000 22000000 15000000 14000000 22000000
17000000 0
17000000 16000000 17000000 16000000 18000000 20000000 15000000 17000000
21000000 17000000 17000000 22000000 14000000 21000000 20000000 12000000
21000000 21000000 0
19000000 20000000 15000000 20000000 22000000 16000000 21000000 19000000
15000000 23000000 21000000 16000000 20000000 17000000 16000000 22000000
17000000 15000000 21000000 0
16000000 17000000 20000000 19000000 17000000 19000000 20000000 18000000
16000000 20000000 18000000 17000000 19000000 18000000 15000000 19000000
18000000 16000000 20000000 16000000 0
19000000 20000000 15000000 20000000 22000000 16000000 21000000 19000000
15000000 23000000 21000000 16000000 20000000 17000000 16000000 22000000
17000000 15000000 21000000 9000000 16000000 0
17000000 16000000 17000000 16000000 18000000 20000000 15000000 17000000
21000000 17000000 17000000 22000000 14000000 21000000 20000000 12000000
21000000 21000000 9000000 21000000 20000000 21000000 0
17000000 18000000 17000000 18000000 20000000 14000000 21000000 21000000
17000000 21000000 19000000 16000000 22000000 15000000 14000000 22000000
17000000 9000000 21000000 15000000 16000000 15000000 21000000 0
21000000 22000000 17000000 20000000 20000000 14000000 21000000 19000000
13000000 21000000 19000000 16000000 22000000 13000000 16000000 22000000 9000000
17000000 21000000 17000000 18000000 17000000 21000000 17000000 0
18000000 17000000 18000000 17000000 17000000 19000000 14000000 16000000
20000000 16000000 16000000 21000000 15000000 20000000 21000000 9000000 22000000
22000000 12000000 22000000 19000000 22000000 12000000 22000000 22000000 0
20000000 21000000 16000000 21000000 21000000 17000000 22000000 22000000
14000000 24000000 22000000 13000000 23000000 16000000 9000000 21000000 16000000
14000000 20000000 16000000 15000000 16000000 20000000 14000000 16000000
21000000 0
23000000 22000000 15000000 22000000 20000000 14000000 21000000 23000000
13000000 21000000 23000000 14000000 24000000 9000000 16000000 20000000 13000000
15000000 21000000 17000000 18000000 17000000 21000000 15000000 13000000
20000000 16000000 0
14000000 13000000 20000000 15000000 15000000 21000000 16000000 16000000
24000000 14000000 14000000 23000000 9000000 24000000 23000000 15000000 22000000
22000000 14000000 20000000 19000000 20000000 14000000 22000000 22000000
15000000 23000000 24000000 0
22000000 21000000 16000000 25000000 19000000 15000000 22000000 22000000
14000000 20000000 22000000 9000000 23000000 14000000 13000000 21000000 16000000
16000000 22000000 16000000 17000000 16000000 22000000 16000000 16000000
21000000 13000000 14000000 23000000 0
11000000 12000000 25000000 14000000 12000000 20000000 15000000 11000000
21000000 13000000 9000000 22000000 14000000 23000000 22000000 16000000 19000000
19000000 17000000 21000000 18000000 21000000 17000000 19000000 19000000
16000000 22000000 23000000 14000000 22000000 0
15000000 14000000 23000000 16000000 12000000 20000000 15000000 15000000
23000000 9000000 13000000 20000000 14000000 21000000 24000000 16000000 21000000
21000000 17000000 23000000 20000000 23000000 17000000 21000000 21000000
16000000 24000000 21000000 14000000 20000000 13000000 0
21000000 22000000 17000000 24000000 20000000 16000000 23000000 19000000 9000000
23000000 21000000 14000000 24000000 13000000 14000000 20000000 13000000
17000000 21000000 15000000 16000000 15000000 21000000 17000000 13000000
20000000 14000000 13000000 24000000 14000000 21000000 23000000 0
13000000 14000000 23000000 14000000 14000000 22000000 13000000 9000000 19000000
15000000 11000000 22000000 16000000 23000000 22000000 16000000 19000000
21000000 17000000 19000000 18000000 19000000 17000000 21000000 19000000
16000000 22000000 23000000 16000000 22000000 11000000 15000000 19000000 0
17000000 16000000 19000000 12000000 16000000 22000000 9000000 13000000 23000000
15000000 15000000 22000000 16000000 21000000 22000000 14000000 21000000
21000000 15000000 21000000 20000000 21000000 15000000 21000000 21000000
14000000 22000000 21000000 16000000 22000000 15000000 15000000 23000000
13000000 0
22000000 23000000 14000000 21000000 23000000 9000000 22000000 22000000 16000000
20000000 20000000 15000000 21000000 14000000 17000000 19000000 14000000
14000000 20000000 16000000 19000000 16000000 20000000 14000000 14000000
19000000 17000000 14000000 21000000 15000000 20000000 20000000 16000000
22000000 22000000 0
12000000 11000000 26000000 17000000 9000000 23000000 16000000 14000000 20000000
12000000 12000000 19000000 15000000 20000000 21000000 17000000 20000000
20000000 18000000 22000000 17000000 22000000 18000000 20000000 20000000
17000000 21000000 20000000 15000000 19000000 12000000 12000000 20000000
14000000 16000000 23000000 0
14000000 15000000 20000000 9000000 17000000 21000000 12000000 14000000 24000000
16000000 14000000 25000000 15000000 22000000 21000000 17000000 20000000
18000000 16000000 20000000 19000000 20000000 16000000 18000000 20000000
17000000 21000000 22000000 15000000 25000000 14000000 16000000 24000000
14000000 12000000 21000000 17000000 0
25000000 24000000 9000000 20000000 26000000 14000000 19000000 23000000 17000000
23000000 25000000 16000000 20000000 15000000 16000000 18000000 17000000
17000000 17000000 15000000 20000000 15000000 17000000 17000000 17000000
18000000 16000000 15000000 20000000 16000000 25000000 23000000 17000000
23000000 19000000 14000000 26000000 20000000 0
10000000 9000000 24000000 15000000 11000000 23000000 16000000 14000000 22000000
14000000 12000000 21000000 13000000 22000000 21000000 17000000 22000000
18000000 16000000 20000000 17000000 20000000 16000000 18000000 22000000
17000000 21000000 22000000 13000000 21000000 12000000 14000000 22000000
14000000 16000000 23000000 11000000 15000000 24000000 0
9000000 10000000 25000000 14000000 12000000 22000000 17000000 13000000 21000000
15000000 11000000 22000000 14000000 23000000 20000000 18000000 21000000
17000000 17000000 19000000 16000000 19000000 17000000 17000000 21000000
18000000 20000000 23000000 14000000 22000000 11000000 15000000 21000000
13000000 17000000 22000000 12000000 14000000 25000000 10000000 0
EOF
Problem: example1_0_1.tsp
Rows: 66
Columns: 103
Non-zeros: 547
Status: OPTIMAL
Objective: 463000000 (MINimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 (1) NS 2 2 = 4.5e+06
2 (2) NS 2 2 = 5.5e+06
3 (3) NS 2 2 = 7.5e+06
4 (4) NS 2 2 = 6.5e+06
5 (5) NS 2 2 = 5.5e+06
6 (6) NS 2 2 = 6.5e+06
7 (7) NS 2 2 = 5.5e+06
8 (8) NS 2 2 = 5.5e+06
9 (9) NS 2 2 = 6.5e+06
10 (10) NS 2 2 = 6.5e+06
11 (11) NS 2 2 = 5.5e+06
12 (12) NS 2 2 = 7.5e+06
13 (13) NS 2 2 = 7.5e+06
14 (14) NS 2 2 = 6.5e+06
15 (15) NS 2 2 = 5.5e+06
16 (16) NS 2 2 = 6.5e+06
17 (17) NS 2 2 = 6.5e+06
18 (18) NS 2 2 = 7.5e+06
19 (19) NS 2 2 = 5.5e+06
20 (20) NS 2 2 = 7.5e+06
21 (21) NS 2 2 = 8.5e+06
22 (22) NS 2 2 = 7.5e+06
23 (23) NS 2 2 = 5.5e+06
24 (24) NS 2 2 = 7.5e+06
25 (25) NS 2 2 = 6.5e+06
26 (26) NS 2 2 = 6.5e+06
27 (27) NS 2 2 = 5.5e+06
28 (28) NS 2 2 = 6.5e+06
29 (29) NS 2 2 = 7.5e+06
30 (30) NS 2 2 = 7.5e+06
31 (31) NS 2 2 = 5.5e+06
32 (32) NS 2 2 = 6.5e+06
33 (33) NS 2 2 = 6.5e+06
34 (34) NS 2 2 = 5.5e+06
35 (35) NS 2 2 = 5.5e+06
36 (36) NS 2 2 = 6.5e+06
37 (37) NS 2 2 = 5.5e+06
38 (38) NS 2 2 = 6.5e+06
39 (39) NS 2 2 = 7.5e+06
40 (40) NS 2 2 = 5.5e+06
41 (41) NS 2 2 = 4.5e+06
42 B 4 2
43 B 2 2
44 B 4 2
45 B 2 2
46 B 4 2
47 B 4 2
48 NL 2 2 3e+06
49 B 4 2
50 B 4 2
51 NL 2 2 < eps
52 B 2 2
53 B 4 2
54 B 2 2
55 B 4 2
56 B 2 2
57 B 4 2
58 B 4 2
59 B 2 2
60 NL 2 2 < eps
61 NL 2 2 1e+06
62 NL 2 2 1e+06
63 NL 2 2 < eps
64 NL 2 2 < eps
65 NL 2 2 1e+06
66 NL 2 2 1e+06
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 1-41* NS 1 1 = < eps
2 2-41* NS 1 1 = < eps
3 2-40* NU 1 0 1 -2e+06
4 5-40* B 1 0 1
5 5-37* NU 1 0 1 -2e+06
6 10-37* NS 1 1 = < eps
7 10-32* NU 1 0 1 -4e+06
8 11-32* B 1 0 1
9 11-31* NU 1 0 1 -2e+06
10 8-31* B 1 0 1
11 8-34* NU 1 0 1 -2e+06
12 7-34* B 1 0 1
13 7-35* NU 1 0 1 -2e+06
14 4-35* B 1 0 1
15 4-38* NU 1 0 1 -4e+06
16 13-38* B 1 0 1
17 13-29* NU 1 0 1 -6e+06
18 19-29* B 1 0 1
19 19-23* NU 1 0 1 -2e+06
20 16-23* B 1 0 1
21 16-26* NU 1 0 1 -4e+06
22 3-26* B 1 0 1
23 3-39* NU 1 0 1 -6e+06
24 6-39* NU 1 0 1 < eps
25 6-36* NU 1 0 1 -4e+06
26 14-36* B 1 0 1
27 14-28* NU 1 0 1 -4e+06
28 9-28* B 0 0 1
29 9-33* NU 1 0 1 -4e+06
30 17-33* NL 0 0 1 < eps
31 17-25* NU 1 0 1 -4e+06
32 12-25* NL 0 0 1 2e+06
33 12-30* NU 1 0 1 -6e+06
34 15-30* NU 1 0 1 < eps
35 15-27* NU 1 0 1 -2e+06
36 18-27* B 1 0 1
37 18-24* NU 1 0 1 -6e+06
38 20-24* B 1 0 1
39 20-22* NU 1 0 1 -6e+06
40 21-22* B 1 0 1
41 1-21* B 1 0 1
42 20-21 B 0 0 1
43 40-41 B 0 0 1
44 32-37 B 0 0 1
45 31-34 B 0 0 1
46 35-38 B 0 0 1
47 23-29 NL 0 0 1 < eps
48 26-39 NL 0 0 1 < eps
49 28-36 NL 0 0 1 < eps
50 25-33 B 1 0 1
51 27-30 B 0 0 1
52 13-26 NL 0 0 1 < eps
53 4-7 B 0 0 1
54 3-12 B 0 0 1
55 3-36 B 0 0 1
56 14-17 B 0 0 1
57 8-11 B 0 0 1
58 21-24 NL 0 0 1 < eps
59 10-29 B 0 0 1
60 12-39 B 0 0 1
61 19-26 B 0 0 1
62 1-13 NL 0 0 1 2e+06
63 10-13 B 0 0 1
64 5-32 B 0 0 1
65 6-18 NL 0 0 1 < eps
66 12-15 B 0 0 1
67 17-28 B 1 0 1
68 14-25 B 0 0 1
69 14-33 B 0 0 1
70 1-2 NL 0 0 1 < eps
71 3-20 NL 0 0 1 < eps
72 18-20 NL 0 0 1 < eps
73 18-21 NL 0 0 1 < eps
74 20-39 NL 0 0 1 < eps
75 12-27 NL 0 0 1 < eps
76 9-12 NU 1 0 1 < eps
77 1-8 NL 0 0 1 2e+06
78 3-22 B 0 0 1
79 1-11 B 0 0 1
80 2-13 B 0 0 1
81 7-16 B 0 0 1
82 18-22 NL 0 0 1 < eps
83 9-17 NL 0 0 1 < eps
84 2-21 NL 0 0 1 < eps
85 24-36 B 0 0 1
86 4-8 B 0 0 1
87 5-11 NL 0 0 1 < eps
88 3-16 NL 0 0 1 < eps
89 5-21 NL 0 0 1 < eps
90 11-41 B 0 0 1
91 2-29 NL 0 0 1 < eps
92 13-16 NL 0 0 1 < eps
93 13-21 B 0 0 1
94 23-26 B 0 0 1
95 8-21 B 0 0 1
96 21-34 NL 0 0 1 < eps
97 4-18 B 0 0 1
98 5-12 NL 0 0 1 2e+06
99 8-20 NL 0 0 1 2e+06
100 4-24 B 0 0 1
101 6-12 B 0 0 1
102 13-20 NL 0 0 1 2e+06
103 15-21 B 0 0 1
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
KKT.PB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
KKT.DE: max.abs.err. = 0.00e+00 on column 0
max.rel.err. = 0.00e+00 on column 0
High quality
KKT.DB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
End of output
_______________________________________________
Bug-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/bug-glpk
