[Bug-glpk] Re: 1e-0 vs. 1e+0

[Andrew Makhorin]

>I formulated a scheduling problem for a special computer architecture in 
>GLPK/L. I am using glpsol 3.2.4.
>After a few bug fixes in my formulation I tried a little larger problem 
>-- and got a wrong solution. So I constrained the variables to the 
>values I expected, and I couldn't found a violation of the dependencies, 
>though glpsol says, that there is no feasible solution, even for the 
>nomip problem.
>
>So I expanded the output of glpsol a little bit, that I get information 
>which constraints are violated (maybe a good idea for a next version... 
>:o) ) and the exact values of activity and the bounds -- my changes are 
>also attached.

Your code checks not all possibilities. It should be the following:

   if (typx == LPX_LO || typx == LPX_DB || typx == LPX_FX)
   {  /* check for lower bound violation */
      if (vx < lb - 1e-5 * (1.0 + fabs(lb))) fprintf(...);
   }
   if (typx == LPX_UP || typx == LPX_DB || typx == LPX_FX)
   {  /* check for upper bound violation */
      if (vx > ub + 1e-5 * (1.0 + fabs(ub))) fprintf(...);
   }

However, if you wish to know which constraints are still violated, you
doesn't need to modify the code :+). You need just to look at the
Kuhn-Tucker optimality conditions computed at the final point (they are
printed in the end of the output provided by glpsol).

I run your problem with the following command line:

   glpsol --lpm ... --nomip -o sol

(note that --nomip should be specified; otherwise KKT conditions will
not be computed, because your problem is MIP). KKT conditions computed
at the final point were the following (for detailed explanations about
these mystery lines please see description of the routine lpx_check_kkt
in the glpk reference manual):

------------------------------------------------------------------------
Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 3.28e-16 on row 2568
        max.rel.err. = 1.54e-16 on row 2568
        High quality

KKT.PB: max.abs.err. = 7.07e-01 on column 4
        max.rel.err. = 4.14e-01 on column 4
        PRIMAL SOLUTION IS INFEASIBLE

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
------------------------------------------------------------------------

And looking at the column 4 I found that:

     4 ArgMig[m1,m2,t04]
                    B            0.5             1             =

i.e. this variable is fixed at 1, however its value in the final point
is 0.5 due to inconsistent constraints in your problem, which involves
primal infeasibility.

Since your problem is large enough, I was not able to find what caused
infeasibility using visual analysis. But interesting to note that when
I run your problem with a next version of glpsol, which includes an LP
presolver, primal infeasibility was detected at the presolving stage.
Therefore I suppose there is something wrong with fixed variables.

Also I'd like note that it may happen that your problem will be hard for
glpk *mip* solver.


Andrew Makhorin