[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Huge memory usage difference
|
From: |
Andrew Makhorin |
|
Subject: |
Re: Huge memory usage difference |
|
Date: |
Sun, 16 Aug 2020 17:44:14 +0300 |
On Sun, 2020-08-16 at 11:53 +0200, Domingo Alvarez Duarte wrote:
> Hello !
>
> I just found a class of models that can exhibit a huge memory usage
> difference depending on if we add or not add parameter missing values
> when there is a default value declaration for then.
>
> See this model for example
> https://github.com/mingodad/GLPK/commit/539dd9774829dee4a0b8c8199a9d2b94a3c7d9cb:
>
> GLPK-4.65 from pacakage manager 69.85s 3001.9 Mb 1x 1x
>
> GLPK-4.65 with several optimizations 26.02s 1506.0 Mb 0.37x 0.5x
>
> GLPK-4.65 prev + no param add missing 16.36s 21.2 Mb Mb 0.23x
> 0.007x
>
> This huge difference is due to this changes
> https://github.com/mingodad/GLPK/commit/70d4ad7e97cdb34ee6348c864bd3a941cdb0d422
>
> .
>
> If you have big models/data and can test then with the master branch of
> https://github.com/mingodad/GLPK and report your results I would
> appreciate it and hope this can lead to more performance improvements in
> GMPL/GLPK.
It may not work correctly in some cases, because the expression
specified in the default option may recursively refer to elements
of the same parameter (directly or indirectly).
>
> Notice right now the changes mainly affect GMPL model/data generation
> not solver/solving the generated problem.
>
> ====
>
> /usr/bin/time glpsol-from-package-manager -m mem-default.mod -d
> mem-default.dat
> GLPSOL: GLPK LP/MIP Solver, v4.65
> Parameter(s) specified in the command line:
> -m mem-default.mod -d mem-default.dat
> Reading model section from mem-default.mod...
> mem-default.mod:23: warning: unexpected end of file; missing end
> statement inserted
> 23 lines were read
> Reading data section from mem-default.dat...
> mem-default.dat:32660: warning: unexpected end of file; missing end
> statement inserted
> 32660 lines were read
> Generating omax...
> Generating c1...
> Generating c2...
> Model has been successfully generated
> GLPK Integer Optimizer, v4.65
> 13589 rows, 14037 columns, 42743 non-zeros
> 449 integer variables, all of which are binary
> Preprocessing...
> 9 constraint coefficient(s) were reduced
> 4056 rows, 4495 columns, 12792 non-zeros
> 448 integer variables, all of which are binary
> Scaling...
> A: min|aij| = 1.310e-05 max|aij| = 2.660e+02 ratio = 2.031e+07
> GM: min|aij| = 7.228e-02 max|aij| = 1.384e+01 ratio = 1.914e+02
> EQ: min|aij| = 5.224e-03 max|aij| = 1.000e+00 ratio = 1.914e+02
> 2N: min|aij| = 2.620e-03 max|aij| = 1.750e+00 ratio = 6.679e+02
> Constructing initial basis...
> Size of triangular part is 4056
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.65
> 4056 rows, 4495 columns, 12792 non-zeros
> * 0: obj = 1.000000000e+00 inf = 0.000e+00 (2721)
> * 3122: obj = 5.173823646e+02 inf = 0.000e+00 (0) 3
> OPTIMAL LP SOLUTION FOUND
> Integer optimization begins...
> Long-step dual simplex will be used
> + 3122: mip = not found yet <= +inf (1; 0)
> + 3122: >>>>> 5.173823646e+02 <= 5.173823646e+02 0.0% (1; 0)
> + 3122: mip = 5.173823646e+02 <= tree is empty 0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used: 0.3 secs
> Memory used: 3001.9 Mb (3147772544 bytes)
> 69.85user 0.88system 1:10.73elapsed 99%CPU (0avgtext+0avgdata
> 3083108maxresident)k
> 0inputs+0outputs (0major+770102minor)pagefaults 0swaps
>
> ====
>
> ====
>
> /usr/bin/time myglpsol-with-several-optmizations -m mem-default.mod -d
> mem-default.dat
> GLPSOL: GLPK LP/MIP Solver, v4.65
> Parameter(s) specified in the command line:
> -m mem-default.mod -d mem-default.dat
> Reading model section from mem-default.mod...
> mem-default.mod:23: warning: unexpected end of file; missing end
> statement inserted
> 23 lines were read
> Reading data section from mem-default.dat...
> mem-default.dat:32660: warning: unexpected end of file; missing end
> statement inserted
> 32660 lines were read
> Generating omax...
> Generating c1...
> Generating c2...
> Model has been successfully generated
> GLPK Integer Optimizer, v4.65
> 13589 rows, 14037 columns, 42743 non-zeros
> 449 integer variables, all of which are binary
> Preprocessing...
> 9 constraint coefficient(s) were reduced
> 4056 rows, 4495 columns, 12792 non-zeros
> 448 integer variables, all of which are binary
> Scaling...
> A: min|aij| = 1.310e-05 max|aij| = 2.660e+02 ratio = 2.031e+07
> GM: min|aij| = 7.228e-02 max|aij| = 1.384e+01 ratio = 1.914e+02
> EQ: min|aij| = 5.224e-03 max|aij| = 1.000e+00 ratio = 1.914e+02
> 2N: min|aij| = 2.620e-03 max|aij| = 1.750e+00 ratio = 6.679e+02
> Constructing initial basis...
> Size of triangular part is 4056
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.65
> 4056 rows, 4495 columns, 12792 non-zeros
> * 0: obj = 1.000000000e+00 inf = 0.000e+00 (2721)
> * 3122: obj = 5.173823646e+02 inf = 0.000e+00 (0) 3
> OPTIMAL LP SOLUTION FOUND
> Integer optimization begins...
> Long-step dual simplex will be used
> + 3122: mip = not found yet <= +inf (1; 0)
> + 3122: >>>>> 5.173823646e+02 <= 5.173823646e+02 0.0% (1; 0)
> + 3122: mip = 5.173823646e+02 <= tree is empty 0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used: 0.3 secs
> Memory used: 1506.0 Mb (1579147056 bytes)
> 26.02user 0.57system 0:26.61elapsed 99%CPU (0avgtext+0avgdata
> 1547792maxresident)k
> 1952inputs+0outputs (9major+386354minor)pagefaults 0swaps
>
> ====
>
> ====
>
> /usr/bin/time myglpsol-master -m mem-default.mod -d mem-default.dat
> GLPSOL: GLPK LP/MIP Solver, v4.65
> Parameter(s) specified in the command line:
> -m mem-default.mod -d mem-default.dat
> Reading model section from mem-default.mod...
> mem-default.mod:23: warning: unexpected end of file; missing end
> statement inserted
> 23 lines were read
> Reading data section from mem-default.dat...
> mem-default.dat:32660: warning: unexpected end of file; missing end
> statement inserted
> 32660 lines were read
> Generating omax...
> Generating c1...
> Generating c2...
> Model has been successfully generated
> GLPK Integer Optimizer, v4.65
> 13589 rows, 14037 columns, 42743 non-zeros
> 449 integer variables, all of which are binary
> Preprocessing...
> 9 constraint coefficient(s) were reduced
> 4056 rows, 4495 columns, 12792 non-zeros
> 448 integer variables, all of which are binary
> Scaling...
> A: min|aij| = 1.310e-05 max|aij| = 2.660e+02 ratio = 2.031e+07
> GM: min|aij| = 7.228e-02 max|aij| = 1.384e+01 ratio = 1.914e+02
> EQ: min|aij| = 5.224e-03 max|aij| = 1.000e+00 ratio = 1.914e+02
> 2N: min|aij| = 2.620e-03 max|aij| = 1.750e+00 ratio = 6.679e+02
> Constructing initial basis...
> Size of triangular part is 4056
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.65
> 4056 rows, 4495 columns, 12792 non-zeros
> * 0: obj = 1.000000000e+00 inf = 0.000e+00 (2721)
> * 3122: obj = 5.173823646e+02 inf = 0.000e+00 (0) 3
> OPTIMAL LP SOLUTION FOUND
> Integer optimization begins...
> Long-step dual simplex will be used
> + 3122: mip = not found yet <= +inf (1; 0)
> + 3122: >>>>> 5.173823646e+02 <= 5.173823646e+02 0.0% (1; 0)
> + 3122: mip = 5.173823646e+02 <= tree is empty 0.0% (0; 1)
> INTEGER OPTIMAL SOLUTION FOUND
> Time used: 0.2 secs
> Memory used: 21.2 Mb (22256384 bytes)
> 16.36user 0.02system 0:16.39elapsed 99%CPU (0avgtext+0avgdata
> 24516maxresident)k
> 2600inputs+0outputs (11major+7226minor)pagefaults 0swaps
>
> ====
>
> Cheers !
>
>
>