Re: [Bug-glpk] internal error: row->lb != row->ub

[Andrew Makhorin]

> I’m an Octave user. I have tried to implement the so called Earth
> Mover’s Distance, a difference measure for distributions. It is an 
> optimization problem that maps to a transportation problem instance 
> and can be solved by linear programming.

> My script has worked well for many cases, but one particular
> combination of inputs provokes an internal error in GLPK. I have 
> exported the problematic case in CPLEX LP format and the command line 
> version of glpk shows the same behaviour. The message is

> $ glpsol --cpxlp test_glpk.lp
> lpx_read_cpxlp: reading problem data from `test_glpk.lp'...
> lpx_read_cpxlp: 208 rows, 9591 columns, 19182 non-zeros
> lpx_read_cpxlp: 7264 lines were read
> glp_simplex: original LP has 208 rows, 9591 columns, 19182 non-zeros
> GLPK internal error: row->lb != row->ub; file glplpp02.c, line 1539

> So I suspect the problem is not in Octave. Please see the attached 
> test file. Is it an error on my side or a problem in glpk? I’d be 
> grateful for advice.

> My glpk version is 4.23 installed as binary packages from Debian 
> unstable.

Thank you for the bug report.

In fact, the bug appears in the lp presolver (which is part of glpk)
due to its insufficient robustness. Most probably this happens because
some equality constraints in your model have extremely small (in
magnutude) right-hand sides, for example:

 r_208: + x_9591 + x_9452 + x_9313 + x_9174 + x_9035 + x_8896 + x_8757
 + x_8618 + x_8479 + x_8340 + x_8201 + x_8062 + x_7923 + x_7784 + x_7645
 + x_7506 + x_7367 + x_7228 + x_7089 + x_6950 + x_6811 + x_6672 + x_6533
 + x_6394 + x_6255 + x_6116 + x_5977 + x_5838 + x_5699 + x_5560 + x_5421
 + x_5282 + x_5143 + x_5004 + x_4865 + x_4726 + x_4587 + x_4448 + x_4309
 + x_4170 + x_4031 + x_3892 + x_3753 + x_3614 + x_3475 + x_3336 + x_3197
 + x_3058 + x_2919 + x_2780 + x_2641 + x_2502 + x_2363 + x_2224 + x_2085
 + x_1946 + x_1807 + x_1668 + x_1529 + x_1390 + x_1251 + x_1112 + x_973
 + x_834 + x_695 + x_556 + x_417 + x_278 + x_139 = 1.03244013922399e-152

I think the bug will disappear if you replace such rhs by exact zeros.

Another way to avoid the bug is to disable the lp presolver:

$ glpsol --cpxlp test_glpk.lp --nopresol
lpx_read_cpxlp: reading problem data from `test_glpk.lp'...
lpx_read_cpxlp: 208 rows, 9591 columns, 19182 non-zeros
lpx_read_cpxlp: 7264 lines were read
lpx_adv_basis: size of triangular part = 208
      0:   objval =   1.461796876e+08   infeas =   1.000000000e+00 (0)
    102:   objval =   1.728693938e+07   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   1.0 secs
Memory used: 3.3 Mb (3448988 bytes)