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 CGRBModel::computeIIS
in C++GRBModel.ComputeIIS
in .NETGRBModel.computeIIS
in JavaModel.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 CGRBModel::feasRelax
in C++GRBModel.FeasRelax
in .NETGRBModel.feasRelax
in Javagurobi_feasrelax
in MATLABModel.feasRelaxS
andModel.feasRelax
in Pythongurobi_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 linkingvar
to itsArtL
variable.CArtLB_var
will be the name of the constraint linking anArtL
variable to its correspondingArtLB
variable.CArtU_var
will be the name of the constraint linkingvar
to itsArtU
variable.CArtUB_var
will be the name of the constraint linking anArtU
variable to its correspondingArtUB
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 anArtP
variable to its correspondingArtPB
variable.CArtNB_ct
will be the name of the constraint linking anArtN
variable to its correspondingArtNB
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.