Experiments on huge instances

[jcoupey]

Discussion initiated from PR #22. Related commits to be found in branch experimental_huge_instances.

[jcoupey]

@frodrigo: Thanks for pointing this out.

I've been paying closer attention to memory while solving big TSPLIB instances. On my laptop the load starts to be significant around 10000 locations. usa13509.tsp is still ok but all bigger instances fail...

The heuristic phase gives a peek for memory usage due to this, a sub-matrix is actually copied from the existing matrix...

[frodrigo]

So, maybe the first step is avoiding to instantiate submatrix by create a virtual matrix using index to access original matrix data.

[jcoupey]

After copy, the sub_matrix is actually modified before being passed to minimum_weight_perfect_matching. So I should check on the best way to do this without breaking the original matrix.

This is not actually a problem with your approach as only a part of the locations vector would be copied.

[jcoupey]

I removed the initial matrix implementation and replaced it by the one you suggested (this is the only one required in this branch anyway). I removed everything that stood in the way for compilation (e.g. other loaders, forced start and stop options).

Still segfaults due to matrix copies, I hope to fix this by merging some commits from the refactor_tsp_structure branch.

[jcoupey]

@frodrigo Using current HEAD of the experimental_huge_instances branch, I've been able to solve bigger instances, e.g. pla33810 from TSPLIB. Limitations are:

• there is still a bottleneck in memory usage, a O(n^2) requirement in the graph structure https://github.com/jcoupey/vroom/blob/experimental_huge_instances/src/structures/undirected_graph.h#L34-L36 ;
• the solving strategy is clearing not scaled for this (pla33810 took little less than 10 hours!). The local search should be less exhaustive to go faster (the heuristic phase is less of a problem as it is quite fast, and can be made faster using https://github.com/jcoupey/vroom/blob/experimental_huge_instances/src/heuristics/mst_heuristic.cpp).

[frodrigo]

Interesting ! Thank for looking at this.
How close are you of know solution of pla33810 in 10 hours ?
The bad part, here, is the amount of memory required. Do you think the edge class and the storage of all the weight can be removed ? The spanning tree can be done on square distance without computing the square root. For the rest, I 'm not what between compute distance on the fly or storing on spare matrix can be efficient.

[jcoupey]

The solution for pla33810 costs 68133433, which is +3.16% from optimal. As the benchmark results points out so far, the size of the instances does not really impact on the current approach's performance in term of distance to optimal.
The results for other big instances in TSPLIB are quite in line with that: rl11849, usa13509, brd14051, d15112 and d18512 are at +2.96% , +2.88%, +3.18%, +2.93% and +2.94% from the respective optimal solutions.

Reducing the memory by not storing the edges (at least for the complete graph) would be the next step. This might be a little more tricky than with the matrix as the undirected_graph is used differently depending on the context (with edges or with an adjacency list).