How Gurobi compute IIS for MIP problem?

Answered

Ramy Mohamed

• February 23, 2022 13:37

Hello,

 

Please, I have questions about how Gurobi computes the IIS for MIP models.

As mentioned in this article: How does Gurobi compute the IIS for infeasible models? – Gurobi Support Portal. The approach for computing IIS is based on this paper:

ORSA JOURNAL ON COMPUTING
Vol. 2, No. 1, 1990, DOI: 10.1287/ijoc.2.1.61
Identifying Minimally Infeasible Subsystems of Inequalities
John Gleeson, Jennifer Ryan

Gleeson and Ryan use a variant of Farkas’Lemma to obtain a polyhedron in which each vertex corresponds to an IIS. From my understanding, this method works well for LP problems, and I think it is actually possible to find all IISes of infeasible LP problems if we find all the vertices of the alternative polyhedron.   

My questions:

-Why Gurobi doesn't return all IISes for LP problem? 

-How does Gurobi use Gleeson and Ryan's approach, which is for LP, to compute the IIS for MIP (infeasible models with integer variables)?

 

Thank you very much for your time and consideration

Regards

Ramy

PhD Student

1

• Official comment

  

  Yuriy Zinchenko

  Gurobi Staff

  • February 23, 2022 19:15

  Hello Ramy,

  Thanks for asking! :)

  1. For LP, computing all III's based on the dual, as you said, is equivalent to enumerating all the vertices of the respective dual polyhedron, which could be a massive computational task.  You can google for "vertex enumeration" algorithms or packages. AFAIK there are some, but not many, again, mostly due to the fact the number of such vertices usually grows combinatorially and may be huge.

  2. For MIP, there is no option to dualize (at least, in some compute-reasonable sense, so to speak).  Instead, one can largely rely on various "filters", e.g.,  a deletion filter, an addition filter, etc.  What this terminology refers to is essentially picking a constraint and attempting to remove it from the model to see if the resulting sub-model remains infeasible (a deletion filter), or starting from an empty set, trying to add some subset of constraints in hopes of generating an infeasible system (an addition filter), etc.  Under the hood, Gurobi uses a combination of those, but overall the situation with MIP is far more complex/compute-intensive, as compared to what one can do for LP.

  Hope this helps.
• 

  Ramy Mohamed

  • February 23, 2022 19:32

  

  

  

  Hello Yuriy,

  Thank you very much for your answer. It is very helpful. Much appreciated.

  Please, I have another question:

  If Guroubi computes IIS using a filtering algorithm, that means we can attempt to get multiple IISes by shuffling the constraints in the model, correct? I tried doing that but Guroubi's computIIS method always returns the same IIS regardless of the constraints' order. Does Guroubi order the constraints before applying the filtering algorithm?

  I implemented a filtering algorithm to isolate IIS and I was able to get different IISes by simply shuffling the constraints in the model. I am wondering, can I do the same using Guroubi computeIIS? As it returns IIS much faster. 

  I used the approach from the following paper: 

  Guieu, Olivier, and John W. Chinneck. "Analyzing infeasible mixed-integer and integer linear programs." INFORMS Journal on Computing 11.1 (1999): 63-77. 

   

  Thanks again for your time and consideration.

  Regards

  Ramy

  0
• 

  Yuriy Zinchenko

  Gurobi Staff

  • February 25, 2022 17:45

  > If Guroubi computes IIS using a filtering algorithm, that means we can attempt to get multiple IISes by shuffling the constraints in the model, correct? I tried doing that but Guroubi's computIIS method always returns the same IIS regardless of the constraints' order. Does Guroubi order the constraints before applying the filtering algorithm?

  Precisely!  You can also try to change the Seed parameter, which may alter the IIS trajectory. FWIW, I was trying to find John Chinneck's slides when I wrote my first reply, as he uses the "filter" terminology extensively, and the slides were great, but for some reason could not find it.

  Hope this helps,

  1
• 

  Ramy Mohamed

  • March 01, 2022 15:04

  

  

  

  Hello Yuriy,

  Thank you again for your reply. It is very helpful.

  Here is the slides you were looking for: https://www.sce.carleton.ca/faculty/chinneck/docs/CPAIOR07InfeasibilityTutorial.pdf

  This is a tutorial presentation by Professor Chinneck. This was presented on 2007 in this conference: 

  The Fourth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR'07) May 23-26, 2007 - Brussels, Belgium

   

  Btw, Professor Chinneck is in the same department in which I am doing my PhD: Systems and Computer Engineering at Carleton University. 

   

  Regards

  Ramy

  0
• 

  Yuriy Zinchenko

  Gurobi Staff

  • March 02, 2022 20:11

  Great to hear this is helpful.

  Stay well, Ramy, and please say "hello" to John if you run into him; he may remember Yuriy who was a PDF at McMaster when Professor Chinneck visited.

  Regards.

  0

Please sign in to leave a comment.