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

[Michael Hennebry]

On Mon, 30 Jan 2006 address@hidden wrote:

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

As you suspected, the difficulty is not peculiar to GLPK,
it's an aspect of MILPs and even LPs.
Try minimizing the sum of the infeasibiliities.
If you can, it might be useful to tell glpsol to print
a solution whenever it finds a new and improved one.
A set of original constraints which are tight or violated
is a set of mutually infeasible constraints.

-- 
Mike   address@hidden
"Demons after money?  Whatever happened to the still-beating heart
of a virgin?  No one has any standards any more."  -- Rupert Giles