[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] reincarnation of tspsol
From: |
Heinrich Schuchardt |
Subject: |
Re: [Help-glpk] reincarnation of tspsol |
Date: |
Wed, 14 Oct 2015 01:11:50 +0200 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Icedove/31.8.0 |
Hello Andrew,
I tried to solve
http://www.math.uwaterloo.ca/tsp/data/usa/usa115475.tsp
When I adjusted usa115475.tsp to run with the current version of tspsol
(removing 2nd comment, adding EOF) I got a memory access error on a
64bit machine with 6 GB memory.
==3493== Warning: set address range perms: large range [0x3a04c040,
0x6f992110) (undefined)
==3493== Invalid write of size 4
==3493== at 0x401B26: read_data (main.c:144)
==3493== by 0x40160A: main (main.c:486)
==3493== Address 0x6f992110 is 0 bytes after a block of size
898,916,560 alloc'd
==3493== at 0x4C28C20: malloc (vg_replace_malloc.c:296)
==3493== by 0x4ED2AEF: dma (alloc.c:89)
==3493== by 0x401ADE: read_data (main.c:141)
==3493== by 0x40160A: main (main.c:486)
With n = 115474
loc(115474, 115473) should return 6,667,064,601
which does not fit into int32.
Please, add a check like
n < SQRT(INT_MAX / sizeof(int) * 2)
140 n = tsp->dimension;
141 if(n >= sqrt(INT_MAX / sizeof(int) * 2))
142 { xprintf("Problem is too big to solve.\n");
143 exit(EXIT_FAILURE);
144 }
145 xassert(n >= 2);
The TSPLIB file format is defined in:
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/DOC.PS
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/DOC.PS
states:
EOF: This entry is optional.
tspsol throws an error if EOF is missing.
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/DOC.PS
says:
COMMENTS: Additional comments ...
Please, observe the plural form. tspsol throws a error when reaching a
second comment where it should not.
Please, adjust tspsol to accept the TSPLIB format.
Best regards
Heinrich Schuchardt
On 13.10.2015 12:29, Andrew Makhorin wrote:
> Please see the attachment that contains an example application program,
> TSPSOL, which is a stand-alone solver intended to solve the Symmetric
> Traveling Salesman Problem (TSP) on a complete graph with the GLPK
> integer optimizer. More detailed information is given in README file.
>
> This example was introduced in glpk 3.2.1 (August 2002), however, later
> in glpk 4.20 (July 2007) it was removed because of significant changes
> in api. Now TSPSOL is again available and will be included in a next
> release of the package.
>
> Any comments are appreciated.
>
>
> Andrew Makhorin
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk
>