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

[Frank Eschmann]

Hi Andrew,

first, thank you very much for the work you made and the quick answer.


> 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(...);
>    }

I thought quite starry-eyed that these little tolerances must be the 
origin of the infeasibility, and that the lp-solver doesn't take 
tolerances in account...


> 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 didn't know what to do with the KTT values. Now they appear in an 
other light as I read the description in the reference manual (I didn't 
read it yet, because I thought the referenc manual is only for 
programmers using the glpk API).


> [...]
> 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.

I tried to fix the variables to the optimal result, which I calculated 
manually.
It's quite possible that there are some more bugs in my problem 
description which makes the problem infeasible. So I hoped to fix the 
variables to the correct values and get the conflict within the 
constraints. Is there any possibility to do such things?
With other examples I succeeded this way and found many bugs in my 
description.
I saw the two variables with value 0.5, but I thought that there also 
should be some other constraints which are violated.


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

I tried to use .lo instead of .fx on the both variables which result to 
0.5, but that didn't work neither.
But I am not quite sure, if this is what you meant.

Should I wait, until the new version is out, so I have more 
possibilities to check, where my problem lies? That is not too bad for 
me, as my problem isn't that urgent. I could take it on ice for the next 
few weeks or months.


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

Unfortunately yes. I tried a bit larger example and it took more than a 
week on a fast PC... and got at last an mip-unfeasability...
But speed isn't that important at the moment. The formulation of the 
problem as a linear programm is the first step to get some information 
on how the problem behaves. With those informations I want to construct 
a heuristic which works online, distributed over the participating 
systems and at run time.


Thanks again for your help,
Frank Eschmann