[Help-glpk] Re: Failure with a basic LP problem

[Andrew Makhorin]

>I've just come across the following problem :
>
>Minimize
>test: a
>Subject To
>c1: - a + b >= -6909301372.79
>c2: - a + c >= -6919351684.21
>c3: - a + d >= -6930335991.34
>End
>
>for which a=b=c=d=0 seems to be an obvious solution (cplex agrees).
>Yet glpk (4.0) gives the following answer :
>
>lpt_read_prob: reading LP data from `bug-glpk2.lp'...
>lpt_read_prob: 4 variables, 3 constraints
>lpt_read_prob: 7 lines were read
>lpx_simplex: original LP has 3 rows, 4 columns, 6 non-zeros
>lpx_simplex: presolved LP has 3 rows, 4 columns, 6 non-zeros
>gm_scal: max / min = 1.000e+00
>gm_scal: max / min = 1.000e+00
>lpx_adv_basis: size of triangular part = 3
>      0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
>      1:   objval =   0.000000000e+00   infeas =   9.999999856e-01 (0)
>      2:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
>      3:   objval =   0.000000000e+00   infeas =   9.999999855e-01 (0)
>PROBLEM HAS NO FEASIBLE SOLUTION
>lpx_simplex: cannot recover undefined or non-optimal solution
>Time used:   0.0 secs
>Memory used: 0.1M (72700 bytes)
>
>The previous failures I had with glpk came from scaling problems. Is it
>still the case is this problem ?

Thank you very much for your bug report!

Looks like the same trouble as you previously reported, but now due to
large right-hand sides.

In case of your example glpk starts from an advanced initial basis,
where basic variables are b, c, d:

   Row name   St   Activity     Lower bound   Upper bound    Marginal
 ------------ -- ------------- ------------- ------------- -------------
 c1           NL   -6.9093e+09   -6.9093e+09                       < eps
 c2           NL  -6.91935e+09  -6.91935e+09                       < eps
 c3           NL  -6.93034e+09  -6.93034e+09                       < eps

 Column name  St   Activity     Lower bound   Upper bound    Marginal
 ------------ -- ------------- ------------- ------------- -------------
 a            NL             0             0                           1
 b            B    -6.9093e+09             0               
 c            B   -6.91935e+09             0               
 d            B   -6.93034e+09             0               

This initial basis is primal infeasible, so glpk tries to find a primal
feasible basis introducing some artificial variable to make the current
basis primal feasible. Constraint coefficients at that variable are
primal infeasibilities for basic variables, i.e. very large numbers.
Due to that reduced costs for auxiliary objective function (which is the
artificial variable to be minimized) becomes less than an internal
tolerance, while the basis is still primal infeasible.

It seems that the method of one artificial variable currently used on
the phase I in the glpk simplex solver is not sufficiently robust. At
least I do not know how to avoid this defect. The only way is to replace
it by another, more robust method (most probably I will do that in the
next release).

Interesting to note that if the routine which constructs an initial
basis were a bit more intelligent, there would be no troubles.
If you run glpk with options --nopresol --std, the standard initial
basis (where all auxiliary variables are basic) is used. It is optimal,
so no simplex pivots are needed:

Problem:    PROBLEM
Rows:       3
Columns:    4
Non-zeros:  6
Status:     OPTIMAL
Objective:  test = 0 (MINimum)

 Row name   St   Activity     Lower bound   Upper bound    Marginal
 ------------ -- ------------- ------------- ------------- -------------
 c1           B              0   -6.9093e+09               
 c2           B              0  -6.91935e+09               
 c3           B              0  -6.93034e+09               

 Column name  St   Activity     Lower bound   Upper bound    Marginal
 ------------ -- ------------- ------------- ------------- -------------
 a            NL             0             0                           1
 b            NL             0             0                       < eps
 c            NL             0             0                       < eps
 d            NL             0             0                       < eps


- Andrew Makhorin