[Top][All Lists]

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

[Help-glpk] MIP infeasability (and proofs thereof)

From: Wayne . H . Vinson
Subject: [Help-glpk] MIP infeasability (and proofs thereof)
Date: Mon, 30 Jan 2006 15:19:26 -0700

This question probably reveals my poor grasp of MIP solving, but here goes:

I'm trying to use glpsol in MIP mode as part of a software build process, specifically a locate step.  The problem being solved is to assign various code sections into various physical memories, and all the constraints on the problem map nicely to integer linear programming.  That all works fine.  However, I'm having a difficult time producing meaningfull error output in the event that the constraints are infeasable (which in this problem means there's not enough physical memory space to locate all the sections). What I would like to get as output in that case is list of mutually infeasable constraints, or the most infeasable constraint, or really anything that would allow me to generate some vaguely helpful error output when the locate fails.

I believe I know at least one method for acomplishing this.  Essentially add another varriable that pads each constaint and forces the problem feasable, and then solve to minimize that variable.  Then in the resulting solution the inequality constraint that holds with strict equality is part of the cause of the infeasability.  My question is threefold:

1) Is there some way to get the info I need out of glpsol directly without the above changes to the MIP?

2) Is there some way to get it out of the glpk API?

3) If the tool will be of no help, is there a superior method to the one I've described to tease the info out of the MIP itself?  Or any problems with the method I've described?

Thanks is advance,

reply via email to

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