Hide navigation sidebar
Hide table of contents sidebar
Back to top
Toggle table of contents sidebar

# 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. Please also refer to our examples on coping with infeasibility.

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

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 in the same way: they define a relaxation model by introducing additional variables and possibly additional constraints. They also provide various possibilities for you to influence the relaxation model:

- Choose which variable bounds are allowed to be relaxed.

- Choose which constraints are allowed to be relaxed.

- Choose the measure for the “relaxation cost” among three different options.

- Define individual penalties for each relaxed variable bound and each relaxed constraint. These penalties are respected in the relaxation cost.

- Choose whether minimum relaxation cost results are applied directly to the model (`minrelax`-option), meaning a constraint is added to ensure that the minimum relaxation is not exceeded. The details are discussed below.

All `feasRelax` routines are destructive, meaning they directly modify the model on which they are invoked. The above-listed options are handled via function parameters. In the following, we discuss how the relaxation model will look like, i.e., how the model is modified when calling the `feasRelax` routine. First, we assume that the `minrelax`-option is not set, i.e., the original model is relaxed to minimize a chosen relaxation cost. We will discuss how the relaxation model will look like for the three different measures of relaxation cost. In a subsequent section, we discuss what happens when the `minrelax`-option is set to true.

For simplicity, we assume that all variable bounds and all constraints are allowed to be relaxed and all penalties are set to 1.

### Measure of Relaxation Cost

Gurobi provides three options to measure the relaxation cost, which can be interpreted as the L1, L2, and L0 norms of the violations. The function parameter `relaxobjtype` controls which measure is used. In the following we will discuss the three different relaxation cost on an example. Consider the following model, given in LP format:

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

#### Sum of Violations (`relaxobjtype=0`)

One natural measure is to minimize the sum of all (bound and constraint) violations, i.e., to relax the model in the following way:

    Minimize
      ArtL_x + ArtU_x + ArtL_y + ArtP_ct1 + ArtN_ct1
    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
    Bounds
     x free
     y free
    Generals
     x
    End

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`.

The objective is the sum of all these artificial variables to count the total violation. As mentioned above, it is possible to define penalties for the individual bounds and constraints so that the objective can be a weighted sum of violations as well.

#### Sum of Squares of Violations (`relaxobjtype=1`)

It is also common to minimize the sum of squares of all violations. This results in the same relaxation model with a different objective:

    Minimize
      [ ArtL_x ^2 + ArtU_x ^2 + ArtL_y ^2 + ArtP_ct1 ^2 + ArtN_ct1 ^2 ] / 2
    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
    Bounds
     x free
     y free
    Generals
     x
    End

The objective is the sum of squares of the violations. Using penalties for the individual bounds and constraints result in a weighted sum of squares.

#### Count of Violations (`relaxobjtype=2`)

Another measure is to count the number of variables and bounds that need to be relaxed to get a feasible model. To this purpose, additional binary variables are added for each bound and constraint violation:

    Minimize
      ArtLB_x + ArtUB_x + ArtLB_y + ArtPB_ct1 + ArtNB_ct1
    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
    Bounds
     x free
     y free
    Binaries
     ArtLB_x ArtUB_x ArtLB_y ArtPB_ct1 ArtNB_ct1
    Generals
     x
    End

While the continuous variables `ArtL_x` and `ArtU_x` still reflect the amount of violating the lower or upper bound of variable `x`, the binary variables `ArtLB_x` and `ArtUB_x` indicate whether the lower or upper bound, respectively, is relaxed. The binary variables are related to the respective continuous variables via additional constraints. The same applies for the relaxation of the lower bound of `y` and the positive and negative violations of the equality constraint `ct1`. The binary variables are used in the objective to count the violations. Using penalties for the individual bounds and constraints result in a weighted count of the violations.

### Apply Results for Original Objective (`minrelax`-Option)

A first step is to determine and solve the relaxation model depending on the chosen relaxation cost measure, as shown above. This model can then be used to analyze the solutions that make the original model feasible.

A follow-up question might be the following: what is the optimal solution for my original problem under the restriction that the violations are minimal (w.r.t. the chosen measure of the relaxation cost)? Gurobi provides the option to get the relaxation model that reflects this question directly by setting the function parameter `minrelax=True`. This means that the relaxation model w.r.t. the given objective measure, as shown above, is solved. The optimal result is used to add a constraint to the model, under the name `feasobj`, to constrain the relaxation objective so that it is not worse than the found optimal value. Additionally, the original objective is set back. All this is performed immediately when calling the `feasRelax` routine with the option `minrelax=True`.

Considering our example and the sum-of-violation relaxation, the so-created relaxation model is 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

The model contains the artificial variables that account for the violation of bounds or constraints. The model would become feasible if the sum of the violations were at least 1, so the respective `feasobj` constraint is added. Finally, the original objective function is used. Similar is done for the other two measures of relaxation cost. The `feasobj` constraint bounds the respective relaxation cost objective to the optimal value.

### 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 violation-count 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 violation-count 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 violation-count 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 violation-count 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.

Help and Feedback

Press `/` or click to search this documentation | Gurobi website | Gurobi community forum
Go to other Gurobi documentation | Gurobi download | Contact support