Expected time to evaluate model (feasibility)
544 views
Skip to first unread message
edvin....@savantic.se
Apr 19, 2021, 4:02:40 AM4/19/21
to or-tools-discuss
I'm running the CP-SAT solver on a large bin-packing-like problem with O(7M) variables and O(30M) constraints. By a different method I have found a feasible solution and want to try to improve on it by using it as a starting point, so I've set variables initially using "solution_hint" (see https://github.com/google/or-tools/issues/1152).
Now, it takes almost 10 hours to find the first solution, that is the starting point, i.e. to verify that the initial state is indeed a solution. I'm running on a fairly powerful computer with 8 cores and 32 GB memory. My question is if this is reasonable? The solution callback reports 0 conflicts (expected, because it is a solution), 7.4M booleans and 34k branches.
Laurent Perron
Apr 19, 2021, 4:08:01 AM4/19/21
to or-tools-discuss
If you can send us the model with the hint. We could try to check what is happening.
I'm running the CP-SAT solver on a large bin-packing-like problem with O(7M) variables and O(30M) constraints. By a different method I have found a feasible solution and want to try to improve on it by using it as a starting point, so I've set variables initially using "solution_hint" (see https://github.com/google/or-tools/issues/1152).Now, it takes almost 10 hours to find the first solution, that is the starting point, i.e. to verify that the initial state is indeed a solution. I'm running on a fairly powerful computer with 8 cores and 32 GB memory. My question is if this is reasonable? The solution callback reports 0 conflicts (expected, because it is a solution), 7.4M booleans and 34k branches.
--
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/2b00968f-cc1e-4fb6-b7dc-8233630a90ban%40googlegroups.com.
Frederic Didier
Apr 19, 2021, 4:10:12 AM4/19/21
to or-tools-discuss
+1 with Laurent.
You can also try some parameters:
Are you running in multi-thread? ex: --params num_search_workers:8
You can also try --params linearization_level:0 since the LP might be the one taking time.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeZwro-TW1inEoW-AaG17PxWjjHibSZO4yYCbc3y7x7yrg%40mail.gmail.com.
edvin....@savantic.se
Apr 19, 2021, 6:18:27 AM4/19/21
to or-tools-discuss
Oh, I thought multi-thread was on by default. I tried your suggestions and the time dropped by some 60% when trying on a smaller subset. What LP is being done inside the CP-SAT solver? I thought there was nothing of that given that there is a MIP solver one can chose.
It's not trivial to quickly take out the model and start-guess, I might come back with that.
Frederic Didier
Apr 19, 2021, 6:33:20 AM4/19/21
to or-tools-discuss
Oh, I thought multi-thread was on by default. I tried your suggestions and the time dropped by some 60% when trying on a smaller subset. What LP is being done inside the CP-SAT solver? I thought there was nothing of that given that there is a MIP solver one can chose.
Same usage as in a MIP solver. Heuristics, bounds, propagations, cuts... The solver should maybe be called CP-SAT-MIP :)
LP is a powerful technique and helps on the vast majority of problems.
It's not trivial to quickly take out the model and start-guess, I might come back with that.--måndag 19 april 2021 kl. 10:10:12 UTC+2 skrev Frederic Didier:+1 with Laurent.You can also try some parameters:Are you running in multi-thread? ex: --params num_search_workers:8You can also try --params linearization_level:0 since the LP might be the one taking time.On Mon, Apr 19, 2021 at 10:08 AM 'Laurent Perron' via or-tools-discuss <or-tools...@googlegroups.com> wrote:If you can send us the model with the hint. We could try to check what is happening.--I'm running the CP-SAT solver on a large bin-packing-like problem with O(7M) variables and O(30M) constraints. By a different method I have found a feasible solution and want to try to improve on it by using it as a starting point, so I've set variables initially using "solution_hint" (see https://github.com/google/or-tools/issues/1152).Now, it takes almost 10 hours to find the first solution, that is the starting point, i.e. to verify that the initial state is indeed a solution. I'm running on a fairly powerful computer with 8 cores and 32 GB memory. My question is if this is reasonable? The solution callback reports 0 conflicts (expected, because it is a solution), 7.4M booleans and 34k branches.--
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/2b00968f-cc1e-4fb6-b7dc-8233630a90ban%40googlegroups.com.
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/CABcmEeZwro-TW1inEoW-AaG17PxWjjHibSZO4yYCbc3y7x7yrg%40mail.gmail.com.
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/92941d3d-275b-49e7-a83a-0ae8d4e9bafen%40googlegroups.com.
Message has been deleted
Frederic Didier
Apr 19, 2021, 7:50:33 AM4/19/21
to or-tools-discuss
Just the model in protocol buffer format is enough for us to have a look. The flag --cp_model_dump_models should dump it to /tmp/.
It might be big though, so you probably want to compress it, and if it takes more than 2GB uncompressed, then it might just not work...
The error you get seems an out of memory error. In multithread, we do use a lot more memory, which can be an issue, especially if your model is big (has a lot of non-zeros in your constraints).
On Mon, Apr 19, 2021 at 12:51 PM Edvin Sidebo <edvin....@savantic.se> wrote:
Thanks. I just ran on the full problem with nworkers=8 and the process was Killed, by the kernel I suppose. I tried with nworkers=6 and got “terminate called after throwing an instance of ’std::bad_alloc’. what(): bad_alloc. Aborted (core dumped)”. Do you recognise this at all? I didn’t get this before when num_search_workers wasn’t set (nworkers=1 then). Maybe it’s best if I supply the model and code…----
![]()
Edvin Sidebo
FoU-konsult, fil.dr
Savantic AB
Rosenlundsgatan 52
118 63 Stockholm
+46 (0)702-239333
Växel: +46 (0)8 32 00 32
edvin.sidebo@savantic.se
www.savantic.se
Tillsammans höjer vi Sveriges AI-kompetens!
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/acul1GgXqf8/unsubscribe.
To unsubscribe from this group and all its topics, 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/CABqCn%3De4UPs%2BpRL3e3w2%3DiE4Wzu-qZOrA2y7UQGbneP7gF%2BXcA%40mail.gmail.com.
--
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/A2CCEFA2-1BC9-4A08-B628-730E7D9BD400%40savantic.se.
Message has been deleted
edvin....@savantic.se
Apr 19, 2021, 8:38:54 AM4/19/21
to or-tools-discuss
Aha. But where is this parameter? I don’t find it under solver.parameters. I’m using python.
(sorry, posting again after deleting previous message which held e-mail signature which was added by mistake)
Laurent Perron
Apr 19, 2021, 10:23:23 AM4/19/21
to or-tools-discuss
You can use
model.ExportToFile('model_dump.pb.txt')
and send us the compressed file (which will be quite big).
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/c9bc3d20-f4f9-4347-9594-136c3fafac2an%40googlegroups.com.
Edvin Sidebo
Apr 19, 2021, 4:13:22 PM4/19/21
to or-tools-discuss
Thanks a lot--here it is https://savanticabse-my.sharepoint.com/:u:/r/personal/edvin_sidebo_savanticabse_onmicrosoft_com/Documents/ortoolsmodel/model.pb.txt.zip?csf=1&web=1&e=U3MAdD. Hope it is manageable.
Laurent Perron
Apr 19, 2021, 4:59:56 PM4/19/21
to or-tools-discuss
I cannot log in.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/a6f95ae1-31a9-4092-a7fe-814ffbccac6dn%40googlegroups.com.
Edvin Sidebo
Apr 20, 2021, 2:41:24 AM4/20/21
to or-tools-discuss
Sorry must have made a mistake, can you try again with this https://savanticabse-my.sharepoint.com/:u:/g/personal/edvin_sidebo_savanticabse_onmicrosoft_com/EexmO2jC_3tAk9P96aVeGb4BT0txcqBBP5K8QmjQIp1NeA?e=gSGaXd
Laurent Perron
Apr 23, 2021, 6:56:23 AM4/23/21
to or-tools-discuss
Unfortunately, the model is truncated.
You can remove all names, it reduces the model by around 20-25%.
On our side, I am changing the code to be able to export the model in binary format, which should use a bit less space.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/a5d4e8de-d862-4df6-99e2-4442f3c93734n%40googlegroups.com.
Edvin Sidebo
Apr 26, 2021, 8:25:48 AM4/26/21
to or-tools-discuss
I see. Here's the model without names, hope this one isn't truncated.
Laurent Perron
Apr 26, 2021, 11:41:42 AM4/26/21
to or-tools-discuss
I am hitting hard limits when reading the file.
I will try to work around them.
Can you try using
model.Proto().SerializeToString() and write the string to file.
This would be the binary version of the file, which should be smaller.
Thanks a lot :-)
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/fcef5f85-0306-4322-ac3d-2933780490can%40googlegroups.com.
Edvin Sidebo
Apr 28, 2021, 4:59:00 AM4/28/21
to or-tools-discuss
I realised I could make a smaller version of this model. Here's the link to a model <1GB uncompressed: https://savanticabse-my.sharepoint.com/:u:/g/personal/edvin_sidebo_savanticabse_onmicrosoft_com/EexmO2jC_3tAk9P96aVeGb4BT0txcqBBP5K8QmjQIp1NeA?e=iU6Z90
Laurent Perron
Apr 28, 2021, 5:39:10 AM4/28/21
to or-tools-discuss
OK, I can run this one.
Let's see if we can improve it.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/7c28d11f-f896-4b27-9925-ac4e44d2bdc5n%40googlegroups.com.
Laurent Perron
Apr 28, 2021, 5:44:50 AM4/28/21
to or-tools-discuss
I am getting this (with 8 threads). Is it consistent with your experience ?
Presolved optimization model '':
#Variables: 3143854 (3180 in objective)
- 582118 in [0,1]
- 276918 in [0,2]
- 456464 in [0,3]
- 364301 in [0,4]
- 68751 in [0,5]
- 80372 in [0,6]
- 61706 in [0,7]
- 92778 in [0,8]
- 69086 in [0,9]
- 80683 in [0,10]
- 105847 in [0,11]
- 904829 in [0,12]
- 1 in [2,5528]
#kAtMostOne: 6864 (#literals: 86837)
#kBoolAnd: 537304 (#enforced: 537304) (#literals: 537304)
#kExactlyOne: 168 (#literals: 534240)
#kLinear1: 2564914 (#enforced: 2564914)
#kLinearN: 10368 (#enforced: 6360) (#terms: 12018915)
Preloading model.
[Symmetry] Graph for symmetry has 9950988 nodes and 23075608 arcs.
[Symmetry] GraphSymmetryFinder error: During the initial refinement.
[Symmetry] Symmetry computation done. time: 6.9293 dtime: 3.54675
#Bound 138.99s best:inf next:[11504448,3.51262943e+10] initial_domain
Starting Search at 143.59s with 8 workers and subsolvers: [ default_lp, reduced_costs, pseudo_costs, no_lp, max_lp, core, feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, rins_lns_default, rens_lns_default ]
#1 284.67s best:3.51262943e+10 next:[11504448,3.51262942e+10] core [hint] fixed_bools:0/3152739
Laurent Perron
Apr 28, 2021, 5:53:34 AM4/28/21
to or-tools-discuss
On my beefier workstation, I get the same solution, with a different worker. It seems to indicate that hinting works.
Presolved optimization model '':
#Variables: 3143854 (3180 in objective)
- 582118 in [0,1]
- 276918 in [0,2]
- 456464 in [0,3]
- 364301 in [0,4]
- 68751 in [0,5]
- 80372 in [0,6]
- 61706 in [0,7]
- 92778 in [0,8]
- 69086 in [0,9]
- 80683 in [0,10]
- 105847 in [0,11]
- 904829 in [0,12]
- 1 in [2,5528]
#kAtMostOne: 6864 (#literals: 86837)
#kBoolAnd: 537304 (#enforced: 537304) (#literals: 537304)
#kExactlyOne: 168 (#literals: 534240)
#kLinear1: 2564914 (#enforced: 2564914)
#kLinearN: 10368 (#enforced: 6360) (#terms: 12018915)
Preloading model.
[Symmetry] Graph for symmetry has 9950988 nodes and 23075608 arcs.
[Symmetry] GraphSymmetryFinder error: During the initial refinement.
[Symmetry] Symmetry computation done. time: 5.57199 dtime: 3.54675
#Bound 112.63s best:inf next:[11504448,3.51262943e+10] initial_domain
Starting Search at 114.22s with 16 workers and subsolvers: [ default_lp, reduced_costs, pseudo_costs, no_lp, max_lp, core, quick_restart, quick_restart_no_lp, probing, feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, rins_lns_default, rens_lns_default ]
#1 152.28s best:3.51262943e+10 next:[11504448,3.51262942e+10] quick_restart_no_lp [hint] fixed_bools:0/3152739
Edvin Sidebo
Apr 28, 2021, 7:08:16 AM4/28/21
to or-tools-discuss
Hm, this is what I get from model.ModelStats() after having set it up and settings the start guess, but before doing anything else:
#Variables: 3173641
- 6360 in [0,1]
- 957180 in [0,4]
- 2210100 in [0,12]
- 1 in [0,11054]
#kLinear1: 3188105 (#enforced: 3167280)
#kLinear2: 3180
#kLinearN: 10536 (#enforced: 6360) (#terms: 12672300)
But your output says "Presolved", I don't know what that is exactly, does that explain the differences? How do I get that?
Laurent Perron
Apr 28, 2021, 7:31:44 AM4/28/21
to or-tools-discuss
This may be the output on the master branch, not the 8.2.
Do you find a solution for the smaller problem in the same time frame ?
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/0943392d-e6e5-4db8-9487-6cb90b1f5adfn%40googlegroups.com.
Edvin Sidebo
Apr 29, 2021, 3:17:40 AM4/29/21
to or-tools-discuss
Unfortunately when running multiple workers the process is killed, presumably due to memory? When using num_search_workers=1 I found the first solution in 220s. I don't know which of the times to look at from your output, but I see "Starting Search at 114.22s", if that's the one I get something on the same order of magnitude. So it seems to work to find the start guess this time, but the difference in time to do so between this model which is ~40% of the full one is huge. There's however one difference in the configuration, namely the flag linearlization_level which was set to 0 here but left to default on the full model in my original post. Could that be the reason for the slow-down? I will launch a job again on the full model with linearization_level=0.
To run with multiple workers I need to circumvent the memory related crash, do you have any advice? Is there some way I can configure the memory usage, or estimate how much memory the program will need?
Edvin Sidebo
Apr 30, 2021, 2:49:35 AM4/30/21
to or-tools-discuss
Indeed I found the solution in ~9 minutes for the full (original) problem with linearization_level=0. My conclusion is that with only one worker, the linear part is taking up the time and prevents the solver from reaching the start guess solution.
Advice on the memory issue is welcome. Thanks for all the help
Laurent Perron
Apr 30, 2021, 2:57:09 AM4/30/21
to or-tools-discuss
On memory, no advice.
Your problem is huge. It takes a few GB per worker.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f125028b-b1e8-4c39-9861-5fe194aa86b3n%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages