For an Integer Linear Programming problem (ILP), an irreducible infeasible set (IIS) is an infeasible subset of constraints, variable bounds, and integer restrictions that becomes feasible if any single constraint, variable bound, or integer restriction is removed. It is possible to have more than one IIS in an infeasible ILP.
Is it possible to identify all possible Irreducible Infeasible Sets (IIS) for an infeasible Integer Linear Programming problem (ILP)?
Ideally, I aim to find the MIN IIS COVER, which is the smallest cardinality subset of constraints to remove such that at least one constraint is removed from every IIS.
Thanks for your time and consideration.
Regards
Ramy
As a suggested method, it seems that Farkas' lemma can be used as an efficient tool for your problem.
Mehanfar.n
Dear R. M. Fouad,
Also i suggest you to see links on topic.
https://www.jstor.org/stable/25147009
https://documentation.sas.com/doc/en/pgmsascdc/9.4_3.5/casmopt/casmopt_optmilp_details19.htm
https://www.cambridge.org/core/books/integer-linear-programming-in-computational-and-systems-biology/A1E06EE0AC95E4D9911A49C7140CCF5B
Book Theory and applications of satisfiability testing – SAT 2006...
Best regards
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling