[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Sam Seaver
Subject: Re: [Help-glpk] Why would fixed constraints lead to infeasibility?
Date: Wed, 23 Sep 2009 01:23:51 +0400

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

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?

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

reply via email to

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