search

torressa / cspy

A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
https://torressa.github.io/cspy/
MIT License
77 stars 24 forks source link

Remove negative cycle check for BiDirectional #33

Closed Kuifje02 closed 4 years ago

Kuifje02 commented 4 years ago

For vrpy (or any other column generation approach), we might have negative cycles, so the check should be waived if the BiDirectional algorithm is chosen.

https://github.com/torressa/cspy/blob/67df376b2c75ed56538b0f76f7daa9291f74e5fd/cspy/checking.py#L136-L137

torressa commented 4 years ago

I've removed the check for bidirectional and just tested it with the Solomon instances (really cool btw), and... it takes like a year (don't really know if it finishes). Committed to dev if you want to check. I think the algorithm is doing what it should, it's just really computationally expensive to work with a complete path. In the comp. results in the paper its says:

The ng-path relaxation with a neighborhood size of ten is applied, and networks with a reduced arc set are used as pricing heuristics.

I've checked to see if removing the custom REFs helps but it doesn't.

torressa commented 4 years ago

Ok, just as an update, restricting the direction to forward, yields the optiomal results for the test solomon case :tada: Not very fast, but it works. I'm not sure why bidirectional search is so slow.. Maybe because of how the monotone resource are defined. Speed-wise, the more restrictive the resources, the smaller number of possible paths, and the faster solution. So if we add time-windows, we should see faster results.

Kuifje02 commented 4 years ago

That's cool ! I also tested the Solomon case with the 50 first vertices and with the LP version of the sub problem and was able to find the solution of the benchmarks. This is reassuring !The solution is plotted below :

image

For the speed we will probably have to do some profiling to identify the bottlenecks, and maybe some acceleration tricks should be implemented, like the one you mentioned. We will see. Another interesting figure is the rate of convergence of the procedure :

image

Most of the time is spent trying to prove optimality. And actually it fails, as I set a 1000 iteration limit.

But in all cases this is promising and interesting ! Eager to do some comparisons with or-tools !