[Scip] SCIP version 3.0.0 - example TSP

[Timo Berthold]

tl;dr: not a bug, SCIP needs a huge tree, instance is not that simple for
a non-TSP-specific solver

Hi Rostislav,

In my tests, it took quite a long time to reach even 1GB.
However, this is an instance with a medium number of variables (8000) and
relatively few time per node (200-300 nodes per sec on my desktop). Thus,
after some time, there will simply be a huge tree. Also cuts and conflicts
(> 30k within 10 min) contribute to the memory usage.

So, the question is why does SCIP need so much time and such a big tree to
solve that instance. The simple answer is: SCIP is not a TSP solver. The
example shall just illustrate how you can use SCIP for branch-and-cut. A
lot of important tricks to solve TSPs effciently are not implemented
therein.

Still, this simple implementation can solve instances at least one order
of magnitude larger than what a straight-forward MIP-formulation can do,
but also, e.g., Concorde can solve instances at least another order of
magnitude larger.

Just keep in mind that a plain MIP formulation would need a sextillion (or
for our American readers: an undecillion ;-) ) constraints. In that sense,
you are fair off with hitting 8GB after a while.

However, if you meant that after short time/few nodes, SCIP needs 8GB of
memory, I backpedal, and would like to ask you to give us more information
on this.

Best
Timo

PS: Current state of bier127 on my machine:
 1164s|229700 |142186 |544660 |   2.4 |1371M| 407 |   0 |8001 | 854 |8001
| 137 |1797 |  72k|  14k| 1.128730e+05 | 1.186800e+05 |   5.14%

The 142186 * (encoding length of basis information) plus 72k times
(average length of the conflict) contributes to the 1371MB memory.

> Dear SCIP users,
> I use SCIP to solve a TSP related problem (Orienteering Problem) and for
> this purpose I would like to reuse / adapt the subtour constraint
> handler of this example (files ConshdlrSubtour.h and
> ConshdlrSubtour.cpp). But if I tried to run the pure TSP example, the
> constraint handler needs a huge amount of memory also for relatively
> small instances (e.g. for the instance bier127.tsp). Is it correct so or
> is it a bug in this example?
> Thank you for your response.
> Best regards
> Rostislav Stanek
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>