# 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:

`GRBcomputeIIS`

in C`GRBModel::computeIIS`

in C++`GRBModel.ComputeIIS`

in .NET`GRBModel.computeIIS`

in Java`Model.computeIIS`

in Python

## 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:

`GRBfeasrelax`

in C`GRBModel::feasRelax`

in C++`GRBModel.FeasRelax`

in .NET`GRBModel.feasRelax`

in Java`gurobi_feasrelax`

in MATLAB`Model.feasRelaxS`

and`Model.feasRelax`

in Python`gurobi_feasrelax`

in R

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.