Re: Huge memory usage difference

[Domingo Alvarez Duarte]

Hello Andrew !

Thank you for reply !

So testing to detect simple expressions can make it usable in those cases ?

Can you give one such example where it'll fail ?

Cheers !

On 16/8/20 16:44, Andrew Makhorin wrote:
> 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 !