Performance difference between v7.8 and v8+ (and v9+)

[senhalil]

What version of OR-Tools and what language are you using?
Version: v8.2
Language: C++

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing Solver

What operating system (Linux, Windows, ...) and version?
Ubuntu 18.04

What did you do?
Steps to reproduce the behavior:

1. Optimise the same model and instance with the same initial solution using or-tools v7.8 and v8.2 for 5 minutes
2. Compare results
3. Use the final solution obtained with v7.8 on Step 1 as the new initial solution and re-optimise with with v7.8 and v8.2 for 3 minutes
4. Check if v8.2 accepts the solution of v7.8 and compare results

What did you expect to see
Productive iterations and comparable final solutions

What did you see instead?
Starting from the same initial solution, v8.2 makes a lot more iterations (13.5K + 6.5K) in 5 + 3 minutes but makes no improvement while v7.8 makes considerably less iterations (388 + 54) but it improves the objective function value 24% and 3% in Steps 1 and 3, respectively and saves an extra vehicle each time.

I did the Step 3 to check if v8.2 accepts the solution found by v7.8 on Step 1 but it is not necessary. The log of Step 1 shows the performance difference clearly. The logs can be seen in this gist https://gist.github.com/senhalil/ab943bf0cae2ae10fba940f3380bfad6 but basically starting from the same initial solution v8.2 cannot find in minutes the solutions found by v7.8 in seconds.

I am not aware of a method to export/dump the routing model but if it is possible, I can share the dumps if needed.

Anything else we should know about your project / environment

• All vehicles have a break
• Except a few individual services all are pickup and delivery
• All nodes are optional with penalty
• The comparison is repeated with v8.1 and it gives the same results as v8.2.

[senhalil]

One instance hardly shows anything but still, I let v8.2 run longer on Step 3 and it eventually finds the same solutions in the same order but it takes considerably longer.

Step 3

----> run_ortools services(138) preassigned(138) vehicles(12)
OR-Tools v7.8
Using the provided initial solution.
Iteration : 0 Cost : 183880 Time : 0.0341829
Iteration : 3 Cost : 180872 Time : 45.2126
Iteration : 13 Cost : 179024 Time : 53.108
Final Iteration : 54 Cost : 179024 Time : 168.016

----> run_ortools services(138) preassigned(138) vehicles(12)
OR-Tools v8.2
Using the provided initial solution.
Iteration : 0 Cost : 183880 Time : 0.0538045
Iteration : 8002 Cost : 180872 Time : 212.259
Iteration : 45943 Cost : 179024 Time : 1018.48
Final Iteration : 221529 Cost : 179024 Time : 5400.08

Step 1 is running since 30 minutes but there is no improvement yet, I will update the post when the run is completed.

OR-Tools v7.8
Using the provided initial solution.
Iteration : 0 Cost : 242288 Time : 0.0402563
Iteration : 22 Cost : 239698 Time : 7.42891
Iteration : 32 Cost : 239698  Time : 9.81799
Iteration : 41 Cost : 237105 Time : 13.8963
Iteration : 45 Cost : 234666 Time : 16.086
Iteration : 59 Cost : 232186 Time : 18.9422
Iteration : 64 Cost : 232186  Time : 20.6914
Iteration : 90 Cost : 226040 Time : 33.821
Iteration : 114 Cost : 223104 Time : 40.7006
Iteration : 128 Cost : 223104  Time : 43.6939
Iteration : 135 Cost : 220405 Time : 55.0732
Iteration : 147 Cost : 217523 Time : 60.2223
Iteration : 156 Cost : 215061 Time : 64.0186
Iteration : 171 Cost : 212751 Time : 81.8385
Iteration : 179 Cost : 208573 Time : 103.865
Iteration : 192 Cost : 204738 Time : 126.764
Iteration : 196 Cost : 202434 Time : 126.842
Iteration : 211 Cost : 200139 Time : 135.307
Iteration : 215 Cost : 196787 Time : 135.464
Iteration : 243 Cost : 194833 Time : 151.54
Iteration : 249 Cost : 192834 Time : 152.151
Iteration : 256 Cost : 192834  Time : 152.653
Iteration : 262 Cost : 190603 Time : 152.95
Iteration : 279 Cost : 188707 Time : 154.985
Iteration : 341 Cost : 186745 Time : 220.542
Iteration : 370 Cost : 184875 Time : 267.645
Final Iteration : 388 Cost : 183880 Time : 336.022


OR-Tools v8.2
Using the provided initial solution.
Iteration : 0 Cost : 242288 Time : 0.0456571
Iteration : 65536 Cost : 242288 Time : 1594.92

[senhalil]

Here is the result when I let v8.2 run longer.

Both v7.8 and v8.2 find basically the same solutions in the same order* but v8 takes a lot longer. (*: Our solution hook prints out the solutions that are improving the best solution up to that point more than 1%. Line 5 and Lines 12-16 have a small difference in the objective function value)

Line #	v7-Iteration	v7-Objective	v7-Time (s)	v8-Iteration	v8-Objective	v8-Time (s)
1	0	242288	0	0	242288	0
2	22	239698	7	105940	239698	2654
3	41	237105	13	179831	237105	4498
4	45	234666	15	196755	234666	4901
5	59	232186	17	249680	232194	6215
6	90	226040	32	364030	226040	9116
7	114	223104	38	426833	223104	10788
8	135	220405	52	493287	220405	12690
9	147	217523	57	531423	217523	13604
10	156	215061	61	556192	215061	14259
11	171	212751	78	609565	212751	15907
12	179	208574	99	641145	208573	16702
13	192	204739	121	704497	204738	20163
14	196	202435	121	717565	202434	20474
15	211	200140	130	750898	200139	22149
16	215	196788	130	750902	196787	22149
17	243	194833	151	868460	194833	24744
18	249	192834	152	883700	192834	25082

I suspect the performance difference is related to the vehicle breaks because if I remove the vehicle breaks, there is no performance difference between v7.8 and v8.2. I believe the breaks implementation is overhauled at v8.0.

[DanielaGuerinoni]

Hi All,

Firstly, thank you for this fantastic library.

We have noticed a similar performance difference between v7.8 and later versions of OR-Tools during the CloseModelWithParameters() stage, specifically when pickup and delivery constraints are implemented.

Initially a data set of 100 pickup and delivery jobs (i.e. 200 pickup and delivery nodes) and 50 vehicles were scheduled using a few different versions of OR-Tools.

The time it took to close the model with pickup and delivery constraints in place is as follows:

• Version 7.8: 210 ms
• Version 7.9: 8.07 seconds
• Version 8.0: 7.182 seconds
• Version 8.1: 7.579 seconds
• Version 8.2: 6 seconds
• Version 9.0: 7.413 seconds

When running a data set of 542 jobs (i.e. 1084 pickup and delivery nodes) and 159 vehicles with pickup and delivery constraints using version 9.0, the solver had not passed the model closing stage after 30 min. Using version 7.8; however, the time it took to close the model was only 23 seconds and after a 2 minute solve a solution was produced.

Note that all data sets made use of time window and capacity constraints and were multi-depot problems.

Could you please advise on what the performance difference between versions could be attributed to.

Thank you in advance.