search

Kuifje02 / vrpy

A python framework for solving the VRP and its variants with column generation.
MIT License
184 stars 43 forks source link

Ideas to boost the code #9

Open Kuifje02 opened 4 years ago

Kuifje02 commented 4 years ago

Not really an issue, just a place to keep track of our ideas to speed up execution of the code.

Kuifje02 commented 4 years ago

Some profiling with line_profiler (cspy.BiDirectional) :

~77% of the time is consumed by self._algorithm(direct) image

~50% consumed by deque(map(self._propagate_label, edges, repeat(direc, len(edges)))) ~20% consumed by self._check_dominance(next_label, direc) image

torressa commented 4 years ago

I think there's a few bits that can be sped up in bidirectional. The deque map, is always going to be a bottleneck as it is the edge propgragation step, and it has to run for every edge. However, dominance checks can be sped up. I managed to use remove the negative cycle assumption but I got carried away and ended up reworking a bit of the structure of the code, so it's taking a bit longer than expected. Hopefully will have something working in a few days.

Kuifje02 commented 4 years ago

On Solomon's instance, cspy is faster up to 8 nodes :

image

And then something happens :D image

Kuifje02 commented 4 years ago

I added some symmetry breaking constraints (which I found in an article) for the lp version. The idea is that if the initial graph is undirected, then for any path A-B-...-Z, the reverse path Z-...-B-A is also valid. To break the symmetry, we can just impose that the index of node A < index of node Z (only if no time windows are enforced). I need to see how much impact it has.

Maybe a similar strategy could be used for the cspy version. With an additional "feasibility" resource, we could keep track of the indexes and forget about the paths that don't satisfay index(first_node) < index(last_node). Just an idea, maybe a bad one : Maybe using the extra resource (and redefining a custom REF) is more expensive.

torressa commented 4 years ago

As long as you can ensure that the indices are well ordered, that will work, however a bit trickier for custom graphs. Custom REFs are fine, they're not expensive at all, it's just that when they're wrong (which currently time windows were) the algorithm stalls.

Kuifje02 commented 4 years ago

Ok so i implemented the symmetry breaking constraints and it turns out :

So unfortunately this is not a promising idea !

Kuifje02 commented 4 years ago

Still looking for some ideas to boost the algorithm. This idea is similar to the p-nearest neighbor in a way : bad edges (with high marginal cost) are simply removed at each iteration for each subproblem. Looking into it.

Kuifje02 commented 4 years ago

I have implemented the method described by Salani here :

In the current code, if alpha is set to 1, the graph is not pruned : https://github.com/Kuifje02/vrpy/blob/824179e84b365a408c65aa111f3b366b05e02eb4/vrpy/main.py#L147-L149

It definitely speeds up the resolution of the pricing problem, but at the expense on missing out on the best columns, resulting in a higher amount of iterations globally. So it hard to conclude that it globally boosts the algorithm. I think it may depend on the instances, for example if the time windows are tight, it may be counter productive. But it definitely needs more testing on different data sets.

I am working on some other strategies, and most likely, if vrpy wants to be able to solve different variants of routing problems, the user will have to tweak/tune the parameters himself (as in ortools by the way), with default parameters and strategies.

Kuifje02 commented 4 years ago

After some exploration, some testing, and some thinking, I figured it is not a good idea to hard code a heuristic strategy for the pricing problem. Its efficiency is too much related to the type of problem (the best pricing strategy may be different if you have time windows or not, if you have limited number of stops, etc). So I changed the code for now such that by default, the subproblem is solved exactly. And if the user wants a heuristic pricing strategy, he just has to specify the wanted strategy as an input when calling the VehicleRoutingProblem.solve() method. https://github.com/Kuifje02/vrpy/blob/1e54974e285e832709a33e61fb4af259f3ab74e6/vrpy/main.py#L77-L85 Right now there are 4 possible strategies : https://github.com/Kuifje02/vrpy/blob/1e54974e285e832709a33e61fb4af259f3ab74e6/vrpy/main.py#L97-L104

The first one is the exact version.

The second one consists in trying to find routes with a smaller number of stops than what is allowed. The idea is that finding a route with 2-4 stops is quite fast, so if there is one with -ve reduced cost, might as well catch it.

The third and fourth ones consist in pruning the graph, so that there are less edges and nodes, resulting in a quicker execution. Both differ in the way the graph is pruned.

And of course each of these options can be solved with BiDirectional, or with GreedyElim.

Let me know if you have other ideas and if you think this approach is legit. The ortools routing library kind of does this too : you can choose a strategy when calling the solver (cheapest insertion, savings, sweep, etc...), and a default one is proposed.

torressa commented 4 years ago

@Kuifje02 I've got semi-good news for the Solomon instances, using the current subproblem_cspy.py version I've added some extra conditions on the time windows that restricts them further. I was trying to do some post-feasibility check where the partial path ...->i->j->Sink is also checked for time-window feasibility. Same backwards, but this assumes the source and sink have upper time windows which are the same (which seems to be the case for Solomon and I've changed it on the ortools data). Also added some more Righini tricks from here, basically trying to halve the resource bounds. Seems to work and is faster than the lp version (up to like 28 or 29 where the lp starts to dominate again). We'll probably see some benefit on the Augerat instances too.

About cspy: The redesign, was a pretty terrible failure.. I think all the extra mumbo jumbo made it significantly slower. And the parallelisation was also not good for vrpy as the set up times in every iteration make it really slow. I'll make another minor release with the timelimit, threshold and hopefully some label elimination. But I've decided to switch to C++, more appropriate for a low level library, will have fun interfacing with python haha

Kuifje02 commented 4 years ago

I've got semi-good news for the Solomon instances, using the current subproblem_cspy.py version I've added some extra conditions on the time windows that restricts them further. I was trying to do some post-feasibility check where the partial path ...->i->j->Sink is also checked for time-window feasibility. Same backwards, but this assumes the source and sink have upper time windows which are the same (which seems to be the case for Solomon and I've changed it on the ortools data). Also added some more Righini tricks from here, basically trying to halve the resource bounds. Seems to work and is faster than the lp version (up to like 28 or 29 where the lp starts to dominate again). We'll probably see some benefit on the Augerat instances too.

This is great, Well done!

The redesign, was a pretty terrible failure.. I think all the extra mumbo jumbo made it significantly slower. And the parallelisation was also not good for vrpy as the set up times in every iteration make it really slow. I'll make another minor release with the timelimit, threshold and hopefully some label elimination. But I've decided to switch to C++, more appropriate for a low level library, will have fun interfacing with python haha

Kudos for trying the parallelisation! We can't always get it right on the first try. Switching to C++ makes sense, sounds exciting!

torressa commented 4 years ago

Thanks man! :) If it works it'll be sick!