[Scip] SCIP version 3.0.0 - example TSP

[Rostislav Stanek]

Dear Timo,

thank you. It is clear for me now. It takes a lot of time (8 h? - I 
don't know exactly) and first then the memory is out. But it is true 
that for smaller instances you can get the solution relatively quickly.

Thanks again.

Best regards

Rostislav




Dne 6.12.2012 14:38, Timo Berthold napsal(a):
> 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
>>