Re: [Help-glpk] Confused by error messages

[Andrew Makhorin]

> I used glpk (4.15) on my linear programming problem and dumped the result
> into a text file. At the beginning of the file, it has the following
> message:
> <quote>
> Rows:       274
> Columns:    7576 (7350 integer, 7350 binary)
> Non-zeros:  1069
> Status:     INTEGER OPTIMAL
> Objective:  obj = 255.0545959 (MINimum)
> </quote>
> 
> This gave me an impression that the solver found the optimal solution.
> When I check the solution file towards the end, I see this message:
> <quote>
> Integer feasibility conditions:
> 
> INT.PE: max.abs.err. = 5.68e-14 on row 150
>         max.rel.err. = 1.42e-14 on row 2
>         High quality
> 
> INT.PB: max.abs.err. = 4.66e+01 on row 152
>         max.rel.err. = 9.79e-01 on row 152
>         SOLUTION IS INFEASIBLE
> </quote>
> 
> Perhaps I am too novice a user to understand these messages. I don't
> understand how an integer optimal solution can be found when
> the solution is infeasible. Then again, there are two words
> INT.PE and INT.PB which I don't understand (and I googled for the meaning
> without much success). I would greatly appreciate any help to make me
> understand what is going on.
> 
> I used glpsol to solve these. I used --intopt with and without
> --nopresol, both giving the same result.

INT.PE shows errors on solution of the main system xR = A * xS, where
xR are auxiliary variables, xS are structural variables. INT.PB shows
errors on bounds of auxiliary and structural variables. (These
conditions are the same as KKT.PE and KKT.PB checked by the routine
lpx_check_kkt; for more details see the library reference.)

In your case the lower or upper bound of at least one row (namely,
152) is violated, i.e. the solution obtained by the solver must be
considered as *wrong* in spite of the solution status. As a rule this
may happen due to excessive round-off errors, which, in turn, may
appear due to very large coefficients at integer variables in some
constraints. The problem can be fixed by decreasing the integer
tolerance (tol_int), which is 1e-6 by default.

If you wish, you can write your instance in mps format (using either
the routine lpx_write_mps or the glpsol option '--wmps filename'),
gzip it, and post it to me. This would allow me to say something more
reasonable.

Andrew Makhorin