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:

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:

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.