[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [Bug-glpk] Re: 1e-0 vs. 1e+0

**From**: |
Frank Eschmann |

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

**Date**: |
Fri, 21 Mar 2003 17:23:44 +0100 |

**User-agent**: |
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.2.1) Gecko/20021130 |

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