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