Gurobi states problem is infeasible when solution certainly exists
AnsweredI'm encountering some odd behavior that is likely rooted in my misunderstanding of the way Gurobi operates UTH.
I have two optimization problems, below aren't the exact problems but illustrate the idea.
Problem 1: minimize the deviation from a strict equality
min(x) s
s.t
Ax <= b + s
Ax >= b - s
Dx <= e
s is the level of deviation from a given value d
Problem 2: within the deviation try to minimize for an additional objective (s is fixed based on value from Problem 1)
min(x) c'x
s.t
Ax <= b + s
Ax >= b - s
Dx <= e
Problem 1 will relax the deviation amount to ensure that x satisfies Dx <= e. Given that relaxation I want to then satisfy a secondary objective. In theory, the solution to problem 1 is a feasible and perhaps optimal solution to problem 2. Yet, gurobi is throwing an infeasibility error for problem 2 even when I warm start problem 2 with the values from problem 1.
I noticed that if I slightly perturb s (i.e s = s + 1e-4) then gurobi is able to find a solution no problem. I imagine that tweaking the feasibility tolerance or objective tolerance would help, but I would like to have them set to the same tolerance in both problems.
I would expect gurobi to return the solution from problem 1 if no better solution can be found.
Thank you for your help with this.
-
Hi,
The behaviour you described can occur if the solution returned by the first problem is not "clean." Due to the finite precision of floating-point arithmetic, the optimal solution returned by Gurobi may exhibit constraint or bound violations beyond the feasibility tolerance, especially if your model includes problematic numerical properties. These might include large objective and RHS values or a wide range of matrix coefficients. Do you see any warning messages in the log of the first model indicating a violation beyond the default feasibility tolerance of 1e-6 for the optimal solution?
To confirm whether this is a numerical issue, you can fix the lower and upper bounds of the variables in the second model to the values from the first model's solution and then optimize the model. As you pointed out, this would render the model infeasible. You can then call the method
model.computeIIS()
to generate an IIS file, which can help identify the source of the infeasibility. For more details on diagnosing an infeasible model, see the article "How do I determine why my model is infeasible?".I imagine that tweaking the feasibility tolerance or objective tolerance would help, but I would like to have them set to the same tolerance in both problems
If acceptable for your application, you can set the
FeasibilityTol
parameter to a larger value for both models. Additionally, you could experiment with parameters such asNumericFocus=1|2|3
andScaleFlag=2
when solving the first model to see if enforcing stricter numerical precautions helps produce a cleaner solution.It also seems that your application involves solving an optimization model with two hierarchical objective functions. You might want to explore Gurobi's multi-objective feature, which provides a convenient API for handling such models.
Best regards,
Maliheh
0 -
Thank you Maliheh. This confirms my suspicion. I will give your recommendations a try and see what the results are.
Best,
Alex
0
Please sign in to leave a comment.
Comments
2 comments