[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] reincarnation of tspsol
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] reincarnation of tspsol |
Date: |
Wed, 14 Oct 2015 09:41:32 +0300 |
Hi Heinrich,
Thank you for your comments.
> I tried to solve
> http://www.math.uwaterloo.ca/tsp/data/usa/usa115475.tsp
Wow!
>
> 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);
>
Probably n should be limited, say, by 1000. Tspsol doesn't use column
generation, so the problem object includes *all* (n**2/2-n) binary
variables; e.g. for n = 1000 it is about 500,000 variables.
>
>
> 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.
>
Will fix that.
Andrew Makhorin