[Scip] Minimal infeasible set

[Marc Pfetsch]

Hi Stefan,

SCIP currently does not support this. It is on our feature wishlist, but 
it may take some time until it will be available. (I have rudimentary 
code, but have not found the time to make it ready to be usefull.)

The complexity severly depends on whether you have integral variables or 
not.

1. If you do not have integral variables, the problem is relatively easy 
to solve: You can write down a linear inequality system arising from the 
Farkas Lemma and compute a feasible basis. The support of the solution 
provides you a minimal set.

2. If you have integral variables, the problem is NP-hard, but there 
exist heuristics to compute a minimal set of constraints that create 
infeasibility, e.g. O. Guieu and J. Chinneck, "Analyzing Infeasible 
Mixed-Integer and Integer Linear Programs", INFORMS J. Comput. 11, 63-77 
(1999).

In case 2 you would need to reimplement the heuristics, wait until SCIP 
supports this feature, or resort to a commercial solver (I hope you do 
not seriously consider this).

Best,

Marc



On 23.08.2011 16:18, dooe1 at seznam.cz wrote:
> Hello, I am using SCIP via the command line interface. I was
> wondering, if there is any possible way of determining the minimal
> set of constraints that cause the infeasibility through this
> interface. Most of the times the infeasibility is detected by the
> pre-processing routine. Is there some way to learn more about causes
> for infeasibility using the command line interface? If not, would you
> recommend me some other tool to tackle this problem? It would make my
> work a lot more efficient. Thanks in advance, cheers, Stefan