Detecting the Sources of Model Infeasibility using Gurobi

Today I come to sing the praises of Irreducible Infeasible Sets (IIS). An IIS is a minimal subset of the constraints of an optimization problem that are self-contradictory. In other words, if you remove any single constraint in an IIS, then the remaining constraints are feasible. Most modern linear and mixed-integer solvers have programming APIs to return IIS information for an infeasible model.

The reason IIS is so cool is that it helps diagnose why a model is not able to be solved. This is especially useful when the optimization problem to be solved is formed with the help of input from a user who may not know anything about operations research, or when the model is complicated. IIS is like the “spell check” of linear programming. Building optimization models without IIS is like debugging using “printf”.

Here is a simple example from the lp_solve documentation:

min x + y
  x >= 6
  y >= 6
  x + y <= 11

6 plus 6 is more than 11, people. In this case, all three constraints are part of the IIS.

Here is some C# code using the Gurobi API that obtains the IIS for a very simple model. First, here is the code that forms and solves the model. This is easy to figure this out by reading the Gurobi docs. The only twist is that I have expressed the first two constraints as lower bounds on the variables x and y.

GRBEnv env = new GRBEnv();
GRBModel model = new GRBModel(env);
GRBVar x = model.AddVar(6, Double.MaxValue, 1, GRB.CONTINUOUS, "x");
GRBVar y = model.AddVar(6, Double.MaxValue, 1, GRB.CONTINUOUS, "y");
model.Update();
GRBConstr c3 = model.AddConstr(x + y, GRB.LESS_EQUAL, 11, "c3");
model.Optimize();
model.ComputeIIS();

To find the IIS you need to call another method called ComputeIIS. Then you can query the constraints and variables to see if they are part of the IIS. This is accomplished using the Get method. I simply print out the constraint and variable names that are in the IIS.

// Print the names of all of the constraints in the IIS set.
foreach (var c in model.GetConstrs())
{
    if (c.Get(GRB.IntAttr.IISConstr) > 0)
    {
        Console.WriteLine(c.Get(GRB.StringAttr.ConstrName));
    }
}                

// Print the names of all of the variables in the IIS set.
foreach (var v in model.GetVars())
{
    if (v.Get(GRB.IntAttr.IISLB) > 0 || v.Get(GRB.IntAttr.IISUB) > 0)
    {
        Console.WriteLine(v.Get(GRB.StringAttr.VarName));
    }
}

If you want to write the IIS information to a text file for review, simply use the write method with the “ilp” extension on the file name:

model.Write("model.ilp");

One last thing: using LINQ (a feature of the C# language), you can simplify how we query for the IIS constraints and variables. For example, I can get all of the constraint names in one statement as follows:

var allConstraintNames =
    from c in model.GetConstrs()
    where c.Get(GRB.IntAttr.IISConstr) > 0
    select c.Get(GRB.StringAttr.ConstrName);

LINQ is very handy for creating models and querying results. I use it often!

Advertisements

Author: natebrix

Follow me on twitter at @natebrix.

One thought on “Detecting the Sources of Model Infeasibility using Gurobi”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s