Re: [Help-glpk] Problem infeasible is feasible for glpsol

[Andrew Makhorin]

> Find below a very simple problem (outpb.lp) which is infeasible by
> construction (row r_1 defines x_1 >=0 whereas r_6 x_1<=-1e-006).
> Although there is no feasible solution for x_1 glpsol gives the
> following output:
> 
> $ glpsol --cpxlp outpb.lp  -o sol
> lpx_read_cpxlp: reading problem data from `outpb.lp'...
> lpx_read_cpxlp: 8 rows, 2 columns, 8 non-zeros
> lpx_read_cpxlp: 20 lines were read
> lpx_simplex: original LP has 8 rows, 2 columns, 8 non-zeros
> Objective value = 0
> OPTIMAL SOLUTION FOUND BY LP PRESOLVER
> Time used:   0.0 secs
> Memory used: 0.1M (66340 bytes)

This is because your instance has a very small feasible region and
lp presolver is more tolerant to infeasibility than lp solver.

Solving your instance with --nopresol option gives:

========================================================================
lpx_read_cpxlp: reading problem data from `foo.mod'...
lpx_read_cpxlp: 8 rows, 2 columns, 8 non-zeros
lpx_read_cpxlp: 20 lines were read
lpx_adv_basis: size of triangular part = 8
      0:   objval =   0.000000000e+00   infeas =   1.000000000e+00 (0)
      1:   objval =   0.000000000e+00   infeas =   1.000000000e-07 (0)
PROBLEM HAS NO FEASIBLE SOLUTION
Time used:   0.0 secs
Memory used: 0.1M (53136 bytes)
========================================================================

However, if you look at the output, you will see that all optimality
conditions are "almost" satisfied:

========================================================================
Problem:    
Rows:       8
Columns:    2
Non-zeros:  8
Status:     INFEASIBLE (FINAL)
Objective:  obj = 0 (MINimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 r_1          B          1e-06                           0 
     2 r_2          B         -1e-07                           1 
     3 r_3          B      -0.633976                           1 
     4 r_4          B       0.633976                           1 
     5 r_5          B          1e-07                           1 
     6 r_6          NU        -1e-06                      -1e-06         < eps
     7 r_7          B       0.633976                           1 
     8 r_8          B      -0.633976                           1 

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x_1          B         -1e-06           -10            10 
     2 x_2          NL           -10           -10            10         < eps

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 1.94e-16 on row 3
        max.rel.err. = 1.77e-17 on row 3
        High quality

KKT.PB: max.abs.err. = 1.00e-06 on row 1
        max.rel.err. = 1.00e-06 on row 1
        Medium quality

KKT.DE: max.abs.err. = 0.00e+00 on column 0
        max.rel.err. = 0.00e+00 on column 0
        High quality

KKT.DB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

End of output
========================================================================

If you agree (the lp presolver does while the lp solver does not) that
KKT.PB is satisfied, the solution is feasible; if not, your instance
has no feasible solution.

Andrew Makhorin