Why does my VRP solve faster on the full graph than the filtered one?
Answered
I've been working for a while on solving a VRP on a multigraph, and I'm trying to assess whether applying a Pareto filter to remove dominated arcs can have a positive impact on solve time.
By "Pareto-filtered," I mean we apply the standard Pareto dominance criterion and remove all dominated arcs from the graph. The improvement turns out to be very marginal — and in some cases, solving on the full graph is actually faster (and yields a better gap when optimality isn't reached).
Both graphs have the same number of nodes, but the full graph can have 2–3× more arcs. To give a rough sense of scale: the full graph may have around 12,000 arcs, while the Pareto-filtered version has around 5,000.
Has anyone run into this kind of situation before, and could you help me understand what might be going on?
Thanks
-
-
Gurobi Staff
Hi Alix,
I'm not a VRP expert but perhaps I can offer some advice anyway.
When making a comparison between the filtered graph and the full graph, you will want to test with many many instances, or use the Seed parameter, so that you are comparing distributions of solve times. See How can I make accurate comparisons?
I would also look at the size of the presolved models - this will appear in the logfile. It may be that Gurobi's presolve routine is also effectively removing the dominated arcs. If the presolved model size from the full graph is roughly the same size as the presolved model size from the filtered graph then this would be evidence to suggest the presolve routine is performing something similar to your filtering.
If the presolved models look very different, and comparing distributions of solve times indicates that the full graph is faster then perhaps clues can be found in the log file.
- Riley
0 -
Please sign in to leave a comment.
Comments
1 comment