[Top][All Lists]

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

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

From: Wayne . H . Vinson
Subject: Re: [Help-glpk] MIP infeasability (and proofs thereof)
Date: Tue, 31 Jan 2006 11:38:42 -0700

Minimizing the sum of the infeasabilities is working well.  Since I know that a subset of the constraints (the section sizes) are the only possible causes of infeasability, the non-zero infeasability var (there appears to always be exactly one in practice) tells me what kind of memory is lacking.


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

reply via email to

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