reproducibility of results #97
Comments
|
I think we need to distinguish two cases : 1/ the solution value differs from one run to another : this is a real problem. vs 2/ The solution value is the same each time, but the routes are different. This behavior can be expected with linear solvers. If we are dealing with case 2/ I don't see how we can cope with this as it is related to the solver. The solver considers that each of these configurations are optimal (which is true). Usually, when we say we need reproducible results, we refer to the solution value. |
|
By solution value you mean the total costs? I see your point. I was thinking about using the |
|
Yes indeed, solution value = total costs. Using |
|
Closing for now. Please re open if necessary. |
|
a way to achieve reproducible routes is to return just the Clark & Wright solution |
|
I kindly ask for a reopening. Just noticed, that my solution values with I tried out several value constellations of |
Yes, but the quality of the solution will not be as good.
Could you please add a minimal working example so that we can reproduce this ? |
|
I've obtained solution values 21314, 21454, 21345, 21315, 21395 from this code: |
|
Hey @piaulous! With this change the solution is consistent and best value is 22749 (both using the LP and cspy). |
|
@torressa I am not sure I understand. It seems strange to me that we have to manually change the sign. Maybe I am missing something !? |
|
@Kuifje02 Maybe I'm confused too. Here's my reasoning anyway. I did it because of the sign of the constraints, see e.g. here. In the first case, the vehicle bound constraints are <= so the sign of the dual variables are also <=, so the reduced cost becomes In the case when the vehicle bound constraints are = (if |
|
@torressa I am not 100% sure, but here is how I understand things: There are two signs:
I don't think either of those signs should ever be tweaked. They are a consequence of the initial equations. Changing the sign in front of the dual variable means that the sign of the coefficient in the constraint has changed (and not the sign of the constraint), which is not true. I will re think it through though ! definitely needs some double checking :) |
|
Cool, yeh I think you are right. |
|
The subproblem with |
|
Should be, but just to be sure, do |
|
With the current dev version, I get consistent results :
(I do not have access to GUROBI at the moment). I believe it is ok to have different results with different solvers. Indeed, they may be computing slightly different reduced costs , and so a different pool of routes, which in the end yields a difference in the final MIP. On the other hand, I think it is reassuring that both solvers return the same value for the last LP (21500). I had some problems with CPLEX, as the way we forced the barrier algorithm without crossover was deprecated, but it is fixed now. PULP was returning an infeasible status, while it was just an issue with the options. I checked for GUROBI and the options still look valid (https://www.gurobi.com/documentation/9.1/refman/method.html, https://www.gurobi.com/documentation/9.1/refman/crossover.html). But a sanity check would be to comment out the gurobi options when you encounter an infeasible problem, to check if the default options (simplex and not barrier) work. |
|
I've had some weirder results (working with version in dev as well 305c050). Will double check tomorrow. Results using
Results using
|
|
Could we do a quick test ? Using
If I load master_cbc.lp and solve it with CPLEX, it does return 22042. Could you check that GUROBI returns the same solutions as well ? If you want you can also post your lp files (activate line 49): vrpy/vrpy/master_solve_pulp.py Lines 44 to 49 in 305c050 and I can check that results are consistent. If results are consistent, then it probably means that the differences come from the column generation. |
|
I can confirm, both solutions (22042 and 22045) match using Gurobi. Here are the lp_files.zip. I've installed CPLEX as well, and it seems a lot more stable around 22119 (still some fluctuations but not as much) than Cbc/Gurobi. |
|
@torressa you are a powerful man, having access to all those solvers :D So at least this eliminates the hypothesis that the differences come from the way the last MIP is solved. More likely, something in the column generation is not 100% deterministic. My guess is that the barrier algorithm without crossover is not 100% deterministic, and returns different columns, which have the same reduced cost, but which are different, yielding different results in the last MIP. I will investigate and see if I can confirm this. If this is the case, we could give the user perhaps more control over the solver parameters, with some disclaimers saying that some option may be faster/slower and possibly not 100% deterministic. |
|
Haha academia FTW Just going to push a test that solves using all solvers including OR-Tools (copied off your other repo). Interestingly, the 22550 solution using VRPy gives the following routes Routes using OR-Tools (value 14379)
That was what I thought, but disabling barrier everywhere isn't any better. |
|
I am quite confused ! +1 for using or-tools for another reference. VRPy seems pretty far off. |
|
pushed to this amazingly named branch |
|
Seems that |
|
I just realised the or-tools code was wrong. Actually, I'm finding it hard to enforce the solver to use all vehicles. This is being discussed in this thread google/or-tools#2067 (comment) I think, we're actually OK, the behaviour varies with the solver as mentioned before (#97 (comment)), and as already mentioned in the disclaimer in the docs: we do not guarantee the optimal solution. |
|
@torressa thanks for looking into this one. I also think we can close this for now. What should we do with the amazingly named branch ? |
|
Haha I think we can delete it, there's only that test which is pretty slow and requires ortools, so wouldn't want it in the standard build |
Running my CVRP script multiple times with the same input data lead to results, which differ almost all the time.
As I need reproducible results the solution should always look the same.
If this is the initial solution:
1: ['Source', '11', '3', '5', '9', '6', 'Sink'], (III)
2: ['Source', '10', '18', '19', '8', '17', 'Sink'], (II)
3: ['Source', '14', '4', '15', '2', '1', 'Sink'], (II)
4: ['Source', '16', '20', '13', '7', '12', 'Sink'] (I) (III)
These differences occured already:
1: ['Source', '11', '3', '5', '9', '6', 'Sink'],
2: ['Source', '10', '18', '19', '8', '17', 'Sink'],
3: ['Source', '14', '4', '15', '2', '1', 'Sink'],
4: ['Source', '20', '13', '7', '12', '16', 'Sink'] <-- (I) same nodes but different order
1: ['Source', '10', '18', '19', '8', '17', 'Sink'], <-- (II) route numbers (1,2,3,4) differ from initial solution
2: ['Source', '14', '4', '15', '2', '1', 'Sink'], <-- (II) route numbers (1,2,3,4) differ from initial solution
3: ['Source', '11', '12', '6', '5', '9', 'Sink'], (IV) <-- (III) different nodes, different routing
4: ['Source', '16', '20', '13', '7', '3', 'Sink'] (IV) <-- (III) different nodes, different routing
1: ['Source', '10', '18', '19', '8', '17', 'Sink'],
2: ['Source', '14', '4', '15', '2', '1', 'Sink'],
3: ['Source', '3', '7', '13', '20', '16', 'Sink'], <-- (IV) reversed order
4: ['Source', '9', '5', '6', '12', '11', 'Sink <-- (IV) reversed order
The text was updated successfully, but these errors were encountered: