Algorithm for large model.
Answered
Hi! I'm trying to solve a large energy system MILP. For starters I ran a pure LP without the binary variables to check the solve time before adding binaries. Disclaimer, I don't have a background in optimization mathematics so this question might be obvious or basic, sorry in advance.
The solver took a lot of time so I stopped it in the crossover as can be seen in the log below. I tried to follow the guidelines to not cause numeric stability problems to the best of my abilities. I can probably narrow the matrix range a bit more.
- Is there a numerical problem?
- I used all default options, is there a problem with the algorithms chosen by the solver?
- Is it perhaps due to the size of the problem itself?
obj: 50940550 rows, 30383538 columns, 112614746 nonzeros.
Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (win64).
CPU model: 12th Gen Intel(R) Core(TM) i7-12700H, instruction set [SSE2|AVX|AVX2]
Thread count: 14 physical cores, 20 logical processors, using up to 20 threads
Optimize a model with 50940550 rows, 30383538 columns and 112614746 nonzeros
Model fingerprint: 0x13dcc1bf
Coefficient statistics:
Matrix range [3e-06, 4e+03]
Objective range [6e-03, 2e+08]
Bounds range [2e+00, 2e+04]
RHS range [5e-01, 8e+06]
Presolve removed 20311286 rows and 8867906 columns (presolve time = 7s) ...
Presolve removed 20311286 rows and 8867906 columns (presolve time = 10s) ...
Presolve removed 24343286 rows and 8867906 columns (presolve time = 15s) ...
Presolve removed 33678534 rows and 18203154 columns (presolve time = 32s) ...
Presolve removed 33678646 rows and 18203266 columns (presolve time = 35s) ...
Presolve removed 33678646 rows and 18203266 columns (presolve time = 40s) ...
Presolve removed 33678646 rows and 18203266 columns (presolve time = 46s) ...
Presolve removed 33678646 rows and 18203266 columns (presolve time = 52s) ...
Presolve removed 33678870 rows and 18203266 columns (presolve time = 55s) ...
Presolve removed 33678870 rows and 18203266 columns
Presolve time: 112.96s
Presolved: 17261680 rows, 12180272 columns, 53168334 nonzeros
Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Elapsed ordering time = 51s
Elapsed ordering time = 55s
Elapsed ordering time = 60s
Ordering time: 173.26s
Barrier statistics:
Dense cols : 2576
AA' NZ : 6.944e+07
Factor NZ : 1.751e+09 (roughly 26.0 GB of memory)
Factor Ops : 5.308e+12 (roughly 17 seconds per iteration)
Threads : 12
Barrier solved model in 141 iterations and 7575.58 seconds (6196.11 work units)
Optimal objective 3.67988486e+10
Crossover log...
11274669 variables added to crossover basis 7581s
5760390 DPushes remaining with DInf 0.0000000e+00 7584s
4117236 DPushes remaining with DInf 0.0000000e+00 7602s
3477895 DPushes remaining with DInf 0.0000000e+00 7616s
------------------------------
1938165 DPushes remaining with DInf 0.0000000e+00 21337s
1936860 DPushes remaining with DInf 0.0000000e+00 21421s
1935546 DPushes remaining with DInf 0.0000000e+00 21508s
1934292 DPushes remaining with DInf 0.0000000e+00 21594s
Thank you very much in advance for your time!
Anibal.
-
Hi Anibal,
There are a few things that come to mind.
- Your model is really big. It has over 100 mio nonzeros and still over 50 mio nonzeros after presolve. Thus, it is expected to take a lot of time. Although, the behavior you see seems extreme.
- You might want to experiment with the parameters Presolve=2, PreSparsify=1/2, and Aggregate=2. This might decrease the size of the presolved model further and hoperfully speed-up the optimization process.
- You could upgrade to the latest Gurobi version 11.
- If nothing helps, you could share the model. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
Best regards,
Jaromił0 -
Dear Jaromil,
Thank you very much for your fast response.
I will try to run again with those parameters and see if there is an improvement.
Regarding the version 11, I have a student lic. requested last year with version 10 of gurobi, is there a way to ask for the latest one?
And lastly, I would love to share the model since that would make things much easier, but unfortunately I'm writing a paper on it and until it is published I can't share it.
Best regards,
Anibal.
0 -
Hi Anibal,
Regarding the version 11, I have a student lic. requested last year with version 10 of gurobi, is there a way to ask for the latest one?
As an academic, you can always get a new license for free. Please refer to Academic Program and Licenses.
Best regards,
Jaromił0 -
Dear Jaromil,
I managed to upgrade Gurobi to v11.
I ran 4 test on a smaller instance to check if the options had an effect and got the following results:
opt={"Presolve":2,
"PreSparsify":2,
"Aggregate":2}DEFAULT:
Presolve time: 12
Barrier solve: 389 (377)
Finished solve: 1537 (1148)
-Presolved: 2236419 rows, 1633307 columns, 6431637 nonzeros
Dense cols : 303
AA' NZ : 6.988e+06
Factor NZ : 5.993e+07 (roughly 2.0 GB of memory)
Factor Ops : 1.401e+10 (less than 1 second per iteration)
OPTIONS:
Presolve time: 105
Barrier solve: 431 (326)
Finished solve: 1292 (861)
-Presolved: 2236321 rows, 1633307 columns, 6431385 nonzeros
Dense cols : 303
AA' NZ : 6.987e+06
Factor NZ : 6.011e+07 (roughly 2.0 GB of memory)
Factor Ops : 1.416e+10 (less than 1 second per iteration)
DEFAULT:
Presolve time: 12
Barrier solve: 378 (366)
Finished solve: 1156 (778)
-Presolved: 2236419 rows, 1633307 columns, 6431637 nonzeros
Dense cols : 303
AA' NZ : 6.988e+06
Factor NZ : 5.993e+07 (roughly 2.0 GB of memory)
Factor Ops : 1.401e+10 (less than 1 second per iteration)
Threads : 12
OPTIONS:
Presolve time: 101
Barrier solve: 456 (355)
Finished solve: 1385 (929)
-Dense cols : 303
AA' NZ : 6.987e+06
Factor NZ : 6.011e+07 (roughly 2.0 GB of memory)
Factor Ops : 1.416e+10 (less than 1 second per iteration)
Threads : 12I don't know if I'm missing something but my understanding is that the performance after the presolve is roughly the same (since the PC was being lightly used during runs for all cases so there are some fluctuations) but the presolve time is much higher with the options.
I guess I'm out of options to lower the solve time. I understand that also commercial softwares that solve energy systems take a considerable amount of time. Just to be sure, is there perhaps anything that might come to mind to try to lower the time?
0 -
Yes, it looks difficult. But at least the time per iteration decreased by a lot. Gurobi now only need roughly 1 second per iteration instead of 17 in your original post. You could also experiment with the AggFill parameter. It is hard to give a guidance for this parameter as it is very subtle, so you could just do some try-and-error.
Just to be sure, is there perhaps anything that might come to mind to try to lower the time?
Althought the numerics of your model look fine, maybe you can still slightly improve and gain something. We discuss numerics in detail in our Guidelines for Numerical Issues.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
5 comments