[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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]