Re: [Help-glpk] No feasible solution

[Michael Hennebry]

On Wed, 24 Dec 2003, [koi8-r] ëÕÌÅÚÎÅ× å×ÇÅÎÉÊ ÷ÁÌ[koi8-r] ÅÒØÅ×ÉÞ wrote:

> I've got "Problem has no primal feasible solution". Does somebody has a clue
> how to locate the constraints that caused the emptiness. I have about 1000
> of them. Is there any formal way to drill down up to at least ten?

The minimum is never more than one more than the number of variables.

A straightforward way to find such a set of constraints is to
drop constraints one at a time.
If dropping a constraint results in a solvable problem, pick it up
and go on to the next constraint.

After applying phase 1 to an infeasible problem, all basic satisfied
constraints may be dropped.


If the problem has a feasible dual, then running the dual simplex method
is a more direct approach.
After the last pivot, the nonbasic constraints and one of the
violated constraints will constitute a minimal set.
GLPK's simplex table routines will allow one to pick a correct
constraint from the violated ones.

-- 
Mike   address@hidden
"History is written by the winners."  --  the losers