Re: [Help-glpk] Why would fixed constraints lead to infeasibility?

[Sam Seaver]

Yes, I can say that the problem is almost infeasible.  I also removed
the column, and applied its constraints directly to the rows involved,
and got the same almost infeasibility for some of these rows.

As it happens, three of these rows are very highly used (this is a
large problem, 7000+ columns, 3000+ rows), and affording the
constraints of the rows some of the same slack means I get an optimal
solution.

I read somewhere that my version of glpk may be too old to deal with
these inflexible constraints, I use 4.29, should I upgrade?
S

On Mon, Sep 21, 2009 at 10:04 AM, Michael Hennebry
<address@hidden> wrote:
> On Mon, 21 Sep 2009, Sam Seaver wrote:
>
>>> GLPK does allow one to fix variables.
>>> I suspose it's *possible* that telling it a fixed "variable" is
>>> double bounded instead of fixed might cause it to do the wrong thing.
>>> Probably the difficulty is elsewhere.
>>> Is your problem almost infeasible?
>>
>> How do I determine the 'almost' part?
>
> With difficulty.
> Here is a possiblity:
> Scratch the old objective.
> Replace it with maximize slack.
> Leave equalities alone.
> Replace Ax>=b with slack<=Ax-b.
> Replace Ax<=b with slack<=b-Ax.
> Mathematically, for the original problem to be feasible,
> the optimal of the new problem must be non-negative.
> If it's small, the original problem is almost infeasible.
>
> Scaling could affect both the difficulty in solving
> the original and the optimum of the new problem.
>
> --
> Michael   address@hidden
> "Pessimist: The glass is half empty.
> Optimist:   The glass is half full.
> Engineer:   The glass is twice as big as it needs to be."
>



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