Infeasibility Analysis#

You have a few options if a model is found to be infeasible. You can try to diagnose the cause of the infeasibility, attempt to repair the infeasibility, or both.

Diagnosing infeasibility#

To give you information that can be useful for diagnosing the cause of an infeasibility, Gurobi provides functions and methodes to compute an Irreducible Inconsistent Subsystem (IIS). These routines can be used for both continuous and MIP models, but you should be aware that the MIP version can be quite expensive.

These routines are:

Relaxing for feasibility#

When faced with an infeasible model, you may want to understand how to relax it such that it becomes feasible. To this end, Gurobi provides routines that transform a model into a less constrained one while minimizing the magnitude of the constraint violations.

These routines are:

All of these routines work the same way: they transform the model onto which they are applied by introducing variables and constraints to make the model less constrained, they introduce an objective that measures the gap between the original model and the relaxed one, they minimize that objective, they set back the original objective, and they add a constraint that limits the gap between the original and relaxed models.

Please refer to the description of these routines for the details of how to call them.

Types of relaxation#

There are several ways to measure and minimize the magnitude of the violations of the constraints. These give rise to multiple types of relaxations.

As an example, consider the following model, given here in LP format:

Minimize
 obj: x + y
Subject To
 ct1: x - y = 0
Bounds
 1 <= x <= 2
 3 <= y
General
 x
End

Type 0 relaxation#

A type 0 relaxation would turn that model into the following:

Minimize
  x + y
Subject To
 ct1: x - y + ArtP_ct1 - ArtN_ct1 = 0
 CArtL_x: x + ArtL_x >= 1
 CArtU_x: x - ArtU_x <= 2
 CArtL_y: y + ArtL_y >= 3
 feasobj: ArtL_x + ArtU_x + ArtL_y + ArtP_ct1 + ArtN_ct1 <= 1
Bounds
 x free
 y free
Generals
 x
End

You can see that, for both bounds of the variable x, and for the lower bound of y, variables ArtL_x, ArtU_x and ArtL_y were created. These variables are continuous and non-negative. Their values will be the violations of the (implied) constraints enforcing the bounds of the original variables.

Two other variables ArtP_ct1 and ArtN_ct1 were created to represent the positive and negative violations of the equality constraint ct1.

Finally, the feasopt constraint states that a solution that minimizes the sum of the various violations should be such that this sum is 1, because the feasrelax call found out that the model would become feasible if the sum of the violations was at least 1. And indeed, this relaxed model has an optimal solution with both x and y equal to 2, and ArtL_y equal to 1.

Type 1 relaxation#

A relaxation of type 1 would instead modify the model as follows. This is similar to type 0, except for the feasopt constraint that denotes what objective was minimized during the procedure.

Minimize
  x + y
Subject To
 ct1: x - y + ArtP_ct1 - ArtN_ct1 = 0
 CArtL_x: x + ArtL_x >= 1
 CArtU_x: x - ArtU_x <= 2
 CArtL_y: y + ArtL_y >= 3
 feasobj: [ ArtL_x ^2 + ArtU_x ^2 + ArtL_y ^2 + ArtP_ct1 ^2 + ArtN_ct1 ^2 ]
   <= 0.5
Bounds
 x free
 y free
Generals
 x
End

An optimal solution of this relaxed model has x equal to 2, y equal to 2.5, and both ArtP_ct1 and ArtL_y equal to 0.5.

Type 2 relaxation#

A relaxation of type 2 would modify the model as follows. Compared to types 0 and 1, binary variables and the constraints defining them are added, and these binaries are used in the feasopt constraint.

Minimize
  x + y
Subject To
 ct1: x - y + ArtP_ct1 - ArtN_ct1 = 0
 CArtL_x: x + ArtL_x >= 1
 CArtLB_x: ArtL_x - 1e+06 ArtLB_x <= 0
 CArtU_x: x - ArtU_x <= 2
 CArtUB_x: ArtU_x - 1e+06 ArtUB_x <= 0
 CArtL_y: y + ArtL_y >= 3
 CArtLB_y: ArtL_y - 1e+06 ArtLB_y <= 0
 CArtPB_ct1: ArtP_ct1 - 1e+06 ArtPB_ct1 <= 0
 CArtNB_ct1: ArtN_ct1 - 1e+06 ArtNB_ct1 <= 0
 feasobj: ArtLB_x + ArtUB_x + ArtLB_y + ArtPB_ct1 + ArtNB_ct1 <= 1
Bounds
 x free
 y free
Binaries
 ArtLB_x ArtUB_x ArtLB_y ArtPB_ct1 ArtNB_ct1
Generals
 x
End

An optimal solution of this relaxed model has x and y equal to 1, ArtLB_y equal to 1 as well, and ArtL_y has any value between 2 and 1e+6.

Naming of the variables and constraints#

The names of the variables and constraints created by the feasrelax feature all contain the substring Art, as in artificial variables.

Relaxation variables related to the bounds of variables refer to the name var of the variable, and Cnnn (as in ‘Column’) is used instead if the variable doesn’t have a name.

  • ArtL_var will be the name of the “relaxing the lower bound” variable.

  • ArtLB_var will be the name of the corresponding binary (for type 2 relaxations).

  • ArtU_var will be the name of the “relaxing the upper bound” variable.

  • ArtUB_var will be the name of the corresponding binary (for type 2 relaxations).

Similarly, relaxation variables related to constraints refer to ct if that is the name of the constraint, and Rnnn (as in ‘Row’) is used if the constraint doesn’t have a name.

  • ArtP_ct will be the name of the “positive slack” variable measuring how much must be added to the LHS of the constraint ct for it to be satisfied.

  • ArtPB_ct will be the name of the corresponding binary (for type 2 relaxations), measuring whether any positive slack must be added to the constraint ct for it to be satisfied.

  • ArtN_ct will be the name of the “negative slack” variable measuring how much must be removed from the LHS of the constraint ct for it to be satisfied.

  • ArtNB_ct will be the name of the corresponding binary (for type 2 relaxations), measuring whether any negative slack must be removed from the constraint ct for it to be satisfied.

Constraints linking the relaxation variables will be named as such:

  • CArtL_var will be the name of the constraint linking var to its ArtL variable.

  • CArtLB_var will be the name of the constraint linking an ArtL variable to its corresponding ArtLB variable.

  • CArtU_var will be the name of the constraint linking var to its ArtU variable.

  • CArtUB_var will be the name of the constraint linking an ArtU variable to its corresponding ArtUB variable.

Finally, constraints linking the slack variables to their binaries will be named as such:

  • CArtPB_ct will be the name of the constraint linking an ArtP variable to its corresponding ArtPB variable.

  • CArtNB_ct will be the name of the constraint linking an ArtN variable to its corresponding ArtNB variable.

One last constraint is added to the model, under the name feasopt. It constrains the objective that was minimized during the feasrelax run to be not worse than the value found during that run.