[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Problems with TSPSOL
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Problems with TSPSOL |
Date: |
Fri, 9 Mar 2007 15:28:05 +0300 |
> I'm having some issues with tspsol. When I regenerate the cost function
> using the optimal tour I do not get the same result. Hence, I'm wondering
> if I'm possibly doing something stupid extracting the solution.
> (I'm using a symmetric TSP defined with a lower diagonal matrix)
>
> grep '*' example.out | cut -b 8-18 | cut -f 1 -d '*' | awk -F-
> '{printf("edge(%d) = %d <-> %d\n",NR,$1,$2);}'
See the routine tsp_distance (file src/glptsp.c) which computes the
distance between two nodes, or the report by G.Reinelt:
http://www.informatik.uni-heidelberg.de/groups/comopt/software/TSPLIB95/DOC.PS
Probably you are using wrong formulae.
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
>
> Another aspect: Can it possibly be overflow issues? I have fractional
> values < 50 that I multiply with 1e6 and round to get integers. Is there
> a limit on the number of bits for the edge weights?
Edge lengths are limited to 32-bit int's; however, big values (> 1e6)
can cause overflow or inexactness on solving the netflow problem to
generate subtour elimination constraints.