Routing performance between 8.0 vs 8.2

[Bhoumik Shah]

Hi,

I use or-tools for solving a large instance of routing problem. It worked fine with I used v8.0, but after updating to 8.2 (no other change) the performance has degraded significantly.

[Vincent Furnon]

What are the features of your model (type of constraints and costs) ? Is the performance degraded in latency or quality of solutions ?

On Tue, Mar 16, 2021 at 11:44 AM Bhoumik Shah <bhoumi...@gmail.com> wrote:

Hi,

I use or-tools for solving a large instance of routing problem. It worked fine with I used v8.0, but after updating to 8.2 (no other change) the performance has degraded significantly.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/3b219d5e-b0d6-4cbc-8d98-82e96fb956fdn%40googlegroups.com.

[Mizux Seiha]

Could you try the v8.1 ?

Actually, it seems there are some regressions in the v8.2 which start to pop up...

e.g. https://github.com/google/or-tools/pull/2433#issuecomment-800604359

AFAIK:

- could be fixed on master,

- there is a delta of 43 commits between master and v8.2

- I'll try to regenerate a new release v8.2 ASAP (maybe tomorrow (Paris Time) if it is confirmed 

- I'll do a git bisect between 8.2 and master to figure out the issue/fix

[Laurent Perron]

Let's do a 8.3 with the logging for CP-SAT. 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f5fa1b34-a134-4cdf-ad16-fcf9674f228en%40googlegroups.com.

[Bhoumik Shah]

I ran same problem on different version. Without changing any parameter. Performance of 8.0 is significantly better than others.

FirstSolutionStrategy = AUTOMATIC

LocalSearchMetaheuristic = AUTOMATIC

time_limit.seconds = 1800

v7.8:

index, time, objective

1:14:899903977 

Solver status: 1

v8.0:

index, time, objective

1:42:899903977
2:44:899897402
3:46:899746177
4:50:899733027
5:52:899726452
6:61:899713302
7:63:899706727
8:66:899700152
9:70:899687002
10:75:899680427
11:76:899654127
12:78:899542352
13:80:899483177
14:81:899421345
15:83:899332579
16:86:899304025
17:87:899302405
18:90:899257651
19:93:899234464
20:95:899203548
21:97:899164903
22:99:899146069
23:101:899139589
24:103:899095839
25:105:899086135
26:107:899037615
27:109:898872647
28:112:898727087
29:114:898688271
30:116:898592140
31:118:898578407
32:126:898571832
33:128:898569334
34:130:898523467
35:131:898521476
36:134:898511772
37:136:898395324
38:137:898385620
39:138:898343160
40:140:898284936
41:142:898284500
42:145:898202102
43:146:898110211
44:148:898038993
45:149:898009881
46:151:897963817
47:152:897917317
48:155:897913077
49:156:897854093
50:158:897802200
51:159:897604685
52:160:897596205
53:162:897589845
54:163:897348209
55:169:897265811
56:172:897252078
57:173:897251817
58:174:896998148
59:177:896968656
60:178:896960176
61:179:896953816
62:181:896841832
63:182:896672984
64:183:896621091
65:189:896614516
66:194:896594791
67:195:896588216
68:198:896568776
69:200:896545589
70:203:896497861
71:204:896497069
72:205:896484349
73:212:896477774
74:238:896471199
75:263:896464624
76:266:896458049
77:291:896451474
78:293:896444899
79:294:896438324
80:318:896431749
81:320:896425174
82:344:896419114
83:346:896415470
84:347:896392244
85:349:896347254
86:351:896251123
87:352:895836898
88:353:895617170
89:355:895611110
90:356:895609090
91:357:895541162
92:360:895527429
93:362:895046774
94:373:894909444
95:392:894804284
96:393:894794580
97:395:894790340
98:417:894705321
99:418:894658947
100:419:894527697
101:422:894319127
102:425:894195530
103:433:893936723
104:437:893934603
105:439:893920870
106:442:893844926
107:443:893811006
108:455:893714875
109:457:893641406
110:459:893572741
111:470:893544356
112:473:893542236
113:480:893533756
114:507:893443985
115:521:893424429
116:522:893310877
117:523:893259115
118:524:893239771
119:525:893203364
120:526:893138670
121:527:892922099
122:529:892909843
123:532:892590935
124:535:892488991
125:540:892488087
126:547:892300871
127:551:891783031
128:556:891278179
129:562:891169423
130:581:890988868
131:598:890965548
132:622:890855684
133:624:890692089
134:657:890691828
135:658:890570894
136:715:890494574
137:724:890373530
138:740:890194546
139:823:890167080
140:832:890128001
141:898:890125881
Solver status: 1

v8.1:

index, time, objective

1:1326:1080259534 

Solver status: 1

v8.2:

index, time, objective

1:1310:1080259534 

Solver status: 1

[Bhoumik Shah]

In 8.1 and 8.2 the algorithm keeps all jobs unassigned in the solution. In v7.4 also, results are similar that of v7.8. i.e.: Solver finds first solution quickly but then fails to improve upon it.

[Vincent Furnon]

Thanks for the feedback. Can you share the search parameters you are using ? Do you have pickup and deliveries ?

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d2a7de4d-b89c-484f-88d1-05aaea77f80an%40googlegroups.com.

[Bhoumik Shah]

Attached is the jupyter notebook and input data for the solver.

[Bhoumik Shah]

Hi Vincent,

Were you able to reproduce error at your end? What do you think is the probable cause?