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 <[email protected]> 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 [email protected] > "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/ [email protected] _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
