Skip to main content

How Gurobi compute IIS for MIP problem?

Answered

Comments

5 comments

  • Official comment
    Yuriy Zinchenko
    Gurobi Staff Gurobi Staff

    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
    First Comment
    Gurobi-versary
    First Question

    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 Gurobi Staff

    > 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
    First Comment
    Gurobi-versary
    First Question

    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 Gurobi Staff

    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.