Too much time and memory usage

[mingodad]

Testing a fresh build baryonyx uses too much time and memory:

/usr/bin/time baryonyx -O -p init-population-size=10  easy.lp
problem reads from file `easy.lp'
  - output file: easy.lp-9319.sol
  - objective: minimize
  - mode: linear
  - variables: 497/331/0 (real/general/binary)
  - constraints: 434/21/0 (equal/greater/less)
- Preprocessing starts (size: 1.06 MB)
  - Preprocessor finish. Removed variables 12 (size: 1.06 MB)
- Preprocessing finishes (size: 1.06 MB)
  - optimize_inequalities_Z
Solver starts
...
  - Constraints remaining: 124 (loop: 0 t: 0.0s reinit: 0)
  - Constraints remaining: 124 (loop: 0 t: 0.0s reinit: 0)
^CCommand terminated by signal 2
42.71user 81.03system 0:22.64elapsed 546%CPU (0avgtext+0avgdata 14772872maxresident)k
19920inputs+80outputs (343506major+8946333minor)pagefaults 0swaps

The same with glpsol:

/usr/bin/time glpsol --lp easy.lp 
GLPSOL: GLPK LP/MIP Solver, v4.65
Parameter(s) specified in the command line:
 --lp easy.lp
Reading problem data from 'easy.lp'...
455 rows, 827 columns, 1633 non-zeros
331 integer variables, all of which are binary
2237 lines were read
GLPK Integer Optimizer, v4.65
455 rows, 827 columns, 1633 non-zeros
331 integer variables, all of which are binary
Preprocessing...
10 constraint coefficient(s) were reduced
444 rows, 816 columns, 1622 non-zeros
320 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  3.100e+01  ratio =  3.100e+01
GM: min|aij| =  8.781e-01  max|aij| =  1.139e+00  ratio =  1.297e+00
EQ: min|aij| =  8.052e-01  max|aij| =  1.000e+00  ratio =  1.242e+00
2N: min|aij| =  5.000e-01  max|aij| =  1.000e+00  ratio =  2.000e+00
Constructing initial basis...
Size of triangular part is 444
Solving LP relaxation...
GLPK Simplex Optimizer, v4.65
444 rows, 816 columns, 1622 non-zeros
      0: obj =   3.100000000e+02 inf =   6.200e+01 (3)
      3: obj =   3.120000000e+02 inf =   0.000e+00 (0)
*     7: obj =   3.120000000e+02 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
+     7: mip =     not found yet >=              -inf        (1; 0)
+    50: >>>>>   3.120000000e+02 >=   3.120000000e+02   0.0% (3; 0)
+    50: mip =   3.120000000e+02 >=     tree is empty   0.0% (0; 5)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 1.0 Mb (1085290 bytes)
0.01user 0.00system 0:00.02elapsed 70%CPU (0avgtext+0avgdata 4404maxresident)k
1984inputs+0outputs (10major+414minor)pagefaults 0swaps

easy.lp.zip

Also there is a bug that prevents reading this "lp" file in parser.cpp with this possible fix:

raw_problem_status
parse([[maybe_unused]] const baryonyx::context& ctx,
      stream_buffer& buf,
      problem_parser& p) noexcept
{
...
       if (auto elem =
              read_function_element(buf.first(), buf.second(), buf.third());
            elem) {
            if (!p.append_to_objective(*elem))
                return baryonyx::file_format_error_tag::too_many_variables;

            if(elem->read) buf.pop_front(elem->read); //fix for elm->read == 0
            else buf.pop_front();
            continue;
        }
...

And also another bug when trying to load an lp file without any other arguments:

cd lib/test
baryonyx general.lp 
problem reads from file `general.lp'
  - output file: general.lp-10013.sol
  - objective: minimize
  - mode: linear
  - variables: 0/3/0 (real/general/binary)
  - constraints: 2/0/0 (equal/greater/less)
- Preprocessing starts (size: 1.00 MB)
  - Preprocessor finish. Removed variables 3 (size: 1.00 MB)
- Preprocessing finishes (size: 1.00 MB)
  - solve_equalities_01
Solver starts
 * Global parameters:
  - limit: 1000
  - time-limit: infs
  - floating-point-type: double
  - print-level: 0
  - auto-tune: disabled
  - observation: none
 * In The Middle parameters:
  - preprocessing: none
  - constraint-order: none
  - theta: 0.5
  - delta: -1
  - kappa: 0 0.001 0.6
  - alpha: 1
  - w: 50
  - norm: loo
 * Pushes system parameters:
  - pushes-limit: 100
  - pushing-objective-amplifier: 5
  - pushing-iteration-limit: 50
  - pushing-k-factor: 0.9
 * Solver initialization parameters:
  - init-policy: bastert
  - init-policy-random: 0.5
 * Optimizer initialization parameters:
  - init-population-size: 100
  - init-crossover-bastert-insertion: 0.01
  - init-crossover-solution-selection-mean: 0.0
  - init-crossover-solution-selection-stddev: 0.3
  - init-mutation-variable-mean: 0.0001
  - init-mutation-variable-stddev: 0.001
  - init-mutation-value-mean: 0.5
  - init-mutation-value-stddev: 0.2
  - init-kappa-improve-start: 0.0
  - init-kappa-improve-increase: 0.02
  - init-kappa-improve-stop: 0.2
  - merge constraint according to the `none` algorithm
  - merged constraints removed: 0
  - problem memory used: 1.00 MB
Solver finished
Segmentation fault (core dumped)

[quesnel]

I confirm bugs. I work on it.

[quesnel]

Hi @mingodad and thank you for report. I fix:

• the parser in e3d0841
• the last error (in fact a bad report when then preprocessing found the solution) in ce81b6d.

The time/memory error occurred in the integer coefficient (< -1 or > 1) solver and need more work. Baryonyx uses specific solver (branch&bound or an exhaustive solver) for each constraints with integer coefficient. I continue to work.

[mingodad]

Thank you ! And I'm glad it help improve baryonyx.