How do I change variable and/or constraint bounds to make an infeasible model feasible using feasRelax?

Gurobi's feasibility relaxation feature addresses the question: "What modifications are necessary to restore feasibility in the model?" In this article, we will show how to use this feature.  However, the article How do I determine why my model is infeasible? expands on the topic of infeasibility analysis tools further.

Gurobi provides a possibility to create a feasibility relaxation of an infeasible model. There are two methods model.feasRelaxS() and model.feasRelax() (for Python, and corresponding methods for other APIs) where feasRelaxS is a simplified version of feasRelax. In this article, we concentrate on feasRelaxS, but the approach with feasRelax is similar. 

Similar as shown in the example workforce3.py, feasRelaxS can be used to check which variable and/or constraint bounds need to be changed to make an infeasible model feasible. The Python script below can be used to compute the relaxed bounds. Note that it could be worth restricting to variable bound changes only or to constraint bound changes only which can be handled via the third and fourth input parameters of feasRelaxS.

import gurobipy as gp
from gurobipy import GRB
import sys

m = gp.read("infeasible_model.mps.bz2")
m.optimize()

status = m.Status
if status == GRB.UNBOUNDED:
    print('The model cannot be solved because it is unbounded')
    sys.exit(0)
if status == GRB.OPTIMAL:
    print('The optimal objective is %g' % m.ObjVal)
    sys.exit(0)
if status != GRB.INF_OR_UNBD and status != GRB.INFEASIBLE:
    print('Optimization was stopped with status %d' % status)
    sys.exit(0)

# Relax the bounds and try to make the model feasible
print('The model is infeasible; relaxing the bounds')
orignumvars = m.NumVars
# relaxing only variable bounds
m.feasRelaxS(0, False, True, False)
# for relaxing variable bounds and constraint bounds use
# m.feasRelaxS(0, False, True, True)

m.optimize()

status = m.Status
if status in (GRB.INF_OR_UNBD, GRB.INFEASIBLE, GRB.UNBOUNDED):
    print('The relaxed model cannot be solved \
           because it is infeasible or unbounded')
    sys.exit(1)
if status != GRB.OPTIMAL:
    print('Optimization was stopped with status %d' % status)
    sys.exit(1)

# print the values of the artificial variables of the relaxation
print('\nSlack values:')
slacks = m.getVars()[orignumvars:]
for sv in slacks:
    if sv.X > 1e-9:
        print('%s = %g' % (sv.VarName, sv.X))

Slack values:
ArtU_varname1 = 1
ArtL_varname2 = 2.79911e-06
ArtP_constrname1 = 1.57294e-04
ArtN_constrname2 = 2

For variable bounds, the slack variables start with "ArtU_" or "ArtL_" followed by the name of the original variable. Starting with "ArtU_" means that the upper bound of the original variable needs to be increased while starting with "ArtL_" means that the lower bound of the original variable needs to be decreased. In the output above, the upper bound for varname1 needs to be increased by 1, and the lower bound of varname2 needs to be decreased by 2.79911e-06.

For constraint bounds, the slack variables start with "ArtP_" or "ArtN_" followed by the name of the original constraint. Starting with "ArtP_" means that the RHS (right-hand side) of the constraint needs to be decreased while "ArtN_" means that the RHS needs to be increased. For the output above, the RHS of constrname1 needs to be decreased by 1.57294e-04 and the RHS of constrname2 needs to be increased by 2.

Changing the original model file according to the given slack values should result in a feasible model.
Note that also small slack values in the order of 1e-07 or smaller might be important even if they are below the default FeasibilityTol, this holds especially for numerical difficult problems.

If relaxobjtype=2 (the first argument of model.feasRelaxS() and model.feasRelax()) is specified, the objective of the feasibility relaxation is to minimize the total number of bound and constraint violations. In this case, also binary variables are involved in the feasibility relaxation. The names of these binary variables start with "ArtUB_", "ArtLB_", "ArtPB_" or "ArtLB_" followed by the name of the variables and constraints, respectively. The binary variables indicate which variables and/or constraints need to be relaxed.

To customize the feasibility relaxation model further, you may want to consider using the  Model.feasRelax() function which allows you to control,

• Which variables or constraints can be considered for relaxation.
• Customize penalties for each variable bound and constraint.