Re: [Help-glpk] Almost infeasible solution, not sure what to do next

[Sam Seaver]

Dear Andrew,

Thank you for getting back to me.  I did know that I was getting the
right value for the objective function, because someone I know ran the
same matrices using glpkmex in Matlab, and got the same value.
However, they were able to get the status to be Optimal, and not
infeasible, which I couldn't, and so this led me to try and find the
problem on my computer.

Clearly its numerical, and in this instance, as you say, I can say its
found the optimal basic solution.  However, I need to run this many
times (approx 200 x 4000 times) to test a variety of conditions (each
instance is a small variation in the constraint of a row), and I need
to be able to write code that will be able to tell me that it is
optimal every time the problem is almost infeasible.

It seems to me, that any time it declares that it is infeasible, I
could iterate through all of the columns, and find the one column for
which the bounds are the 'most' violated, and output the column and
its details.  In this way, I could, in a semi-automated manner, find
the problems that are either optimal, or almost infeasible.

Does this seem reasonable to you?  Since I've little experience with
using LP, I don't know of an easier way to automatically determine
'almost'-infeasibility.

Thanks
Sam

On Sat, Oct 10, 2009 at 1:46 AM, Andrew Makhorin <address@hidden> wrote:
>> I've a problem that is almost infeasible, its a large one, but the KKT
>> conditions that glpsol gives me is:
>
>> "KKT.PE: max.abs.err = 1.48e-12 on row 1
>>         max.rel.err = 1.17e-16 on row 10
>>         High quality
>
>> KKT.PB: max.abs.err = 6.01e-07 on column 1052
>>         max.rel.err = 6.01e-07 on column 1052
>>         Medium quality
>
>> KKT.DE: max.abs.err = 2.84e-14 on column 80
>>         max.rel.err = 1.09e-16 on column 1168
>>         High quality
>
>> KKT.DB: max.abs.err = 0.00e+00 on row 0
>>         max.rel.err = 0.00e+00 on row 0
>>         High quality"
>
>> The column that KKT.PB refers to is described thus:
>
>> 1052 R_lipid      B    -6.0112e-07             0          1000
>
>> My glpk code fixes this column, using GLP_FX, to have the lower and
>> upper bounds of 0 and 1000, as you can see, but I don't understand why
>> the output tells me that it is trying to go below zero.  I tried to
>> change tolbnd so that it would allow this, but it doesn't change the
>> result.  Can anyone help me by pointing out to me what the next thing
>> I should try and do?
>
> Nothing, because you have obtained the optimal basic solution. Since
> your instance is degenerate, some basic variables are close to their
> bounds, and some of them may slightly (within a working precision)
> violate the bounds due to round-off errors. This is normal.
>
>



-- 
Graduate student
Northwestern University
Interdisciplinary Biological Sciences (IBiS) Program
2205 Tech Drive (Room 2-108 )
Evanston, IL 60208, US

http://amaral.northwestern.edu/people/seaver/
address@hidden