Comments (7)
@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...
from vroom.
So, maybe the first step is avoiding to instantiate submatrix by create a virtual matrix using index to access original matrix data.
from vroom.
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.
from vroom.
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.
from vroom.
@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).
from vroom.
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.
from vroom.
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).
from vroom.
Related Issues (20)
- vroom Error missing duration HOT 5
- Update OS and compilers in CI HOT 1
- Use `std::format` HOT 4
- Use address and UB sanitizers HOT 3
- Handle routing engine http statuses HOT 7
- Ensure request interpretation as TSP HOT 3
- Error with inconsistent vehicle capacity arrays HOT 1
- Seeking Advice: Implementing User-Defined Routes with Invisible Points to Guide Optimization Algorithm HOT 4
- Design of Matrix class HOT 7
- Refactor functions to accept a range instead of a pair of iterators HOT 2
- Compiler warning in gcc-12 build HOT 5
- Update GitHub Actions HOT 1
- Speed up OSRM CI build HOT 2
- Mismatch in compilers used for OSRM and VROOM in CI HOT 1
- VROOM schedules next-day deliveries despite sufficient time windows HOT 5
- Can i solve this user case with VROOM? HOT 2
- More unassigned when using 1 vehicles instead of 2, while creating always 1 route only HOT 10
- Function template names forward iterator while in fact it requires a random access iterator HOT 4
- position job by time HOT 11
- Evaluating dropping rapidjson HOT 5
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from vroom.