How to interpret IntFeasTol ?
Ongoing
We are solving a model with the following settings
OptimalityTol = 1e-06, default
FeasibilityTol = 1e-05
IntFeasTol = 1e-06
The model is solved but there is a warning about max integrality violation -
Optimal solution found (tolerance 1.00e-06)
Warning: max integrality violation (3.2963e-06) exceeds tolerance
How should we interpret this warning message ? Why is this value allowed if it exceeds the IntFeasTol ? The variable is a semi-continuous integer variable with either 0 or >= 5 as bounds.
-
To help expand on these two feasibility tolerances:
FeasibilityTol (Primal feasibility tolerance)
- Default value: 1.00E-06
- Description: All constraints must be satisfied to a tolerance of FeasibilityTol. In other words, this tolerance is applied to the difference between the constraint's right-hand-side and the left-hand-side values at the solution.
IntFeasTol (Integer feasibility tolerance)
- Default value: 1.00E-05 (Note: this is different from the FeasibilityTol)
- Description: An integrality restriction on a variable is considered satisfied when the variable's value is less than IntFeasTol from the nearest integer value. In other words, this tolerance is applied to the difference between the variable value and the closest integer value.
To map this to your specific questions:
For the constraint x1 = 3.29e-06, which tolerance is applied ? The FeasibilityTol or IntFeasTol or both ?
This means that both are applied in this case.
- FeasibilityTol will limit the difference between the RHS (3.29e-06) and the LHS (x1). With a FeasibilityTol of 1e-5, this means that x1 has to be between -6.71E-06 and 1.329E-05.
- IntFeasTol will limit the difference between x1 and its nearest integer value which is 0. With an IntFeasTol of 1e-6, this means that x1 will be between -1e-6 and 1e-6 in a feasible solution. This provides the tighter range for x1.
Is there any other way of modeling this (that x1's value must be fixed to the value it gained in Solve1, other than explicitly rounding as that has led to some other undesired behavior in our application)
My recommendation is to try to address the infeasibility in the first model, if possible. Maliheh's recommendations are solid on this. I look forward to hearing how IntegralityFocus works out for you. You could also test out an Aggregate of 0 and ScaleFlag of 2. And you can try combinations of these numerically relevant parameters.
If you are still having trouble, this is the type of challenge our Gurobi Expert team can help our commercial customers like you with. If you want us to take a look at your model and/or log file, please let us know and we will convert this into a help request. As always, you can create help requests at support.gurobi.com.
2 -
Hi,
The Gurobi Optimizer solves the model in the presolved space. Since presolve can change the meaning of "feasible within tolerances", when the optimal solution is mapped from the presolved space back into the original problem space, there might be some variables/constraints that violate the predefined tolerance values.
In your case, after mapping the solution back into the original space, there is one or more integer or/and semi-continuous variables with the maximum violation of 3.2963e-06 which is greater than 1e-6 set as the IntFeasTol parameter.
- If a violation as big as 3.2963e-06 is acceptable to your application, you can accept the solution.
- If not, you can experiment with Gurobi's numerically relevant parameters such as IntegralityFocus and NumericFocus.
Best regards,
Maliheh
1 -
Thanks for the prompt response Maliheh !
A violation of 3.29e-06 is fine for us but the problem is the solution of this solve is passed on to a subsequent solve with some of these variable values fixed or as constraints.
Solve1 with 1e-06 IntFeasTol returns a solution like x1 = 3.29e-06 and x2 = -3.24e-06 and x3 = 0 (x1, x2, x3 are integer variables)
In Solve2, constraints x1 = 3.29e-06 (the solution from Solve1) and x2 + x3 = -3.24e-06 are added. And now this is causing an infeasible Solve2.
For the constraint x1 = 3.29e-06, which tolerance is applied ? The FeasibilityTol or IntFeasTol or both ?
Is there any other way of modeling this (that x1's value must be fixed to the value it gained in Solve1, other than explicitly rounding as that has led to some other undesired behavior in our application)
We will experiment with the IntegralityFocus parameter in the meantime.
0 -
Thank you both, this is very helpful. Both the IntegralityFocus and Aggregate parameters seem promising, I will reach out if I need more help.
0 -
I have another question related to this, is there a way to programmatically identify if a solution has violated the tolerances ?
Perhaps identifying if there is a log statement printed like "Warning: max integrality violation%"
0 -
The solution quality attributes can be used. These attributes can be queried on the model object after optimizing the model.
- MaxVio: maximum of all unscaled violations that apply to the model
- BoundVio: maximum of bound violation
- IntVio: maximum of integrality violation
- ConstrVio: maximum violation of the constraints
The Model.printQuality() method can also be used in the Gurobi Python API to print statistics on the quality of the computed solution.
0 -
Hi,
I have exactly the same problem but parameters don't help me (Get the solution from Gurobi, copy the model, give the solution as a mipstart, Gurobi rejects or accepts it but starts a phase-I).
I would like to use the solution pool to find the least violated solution.
Is it possible to get those violations (MaxVio, BoundVio...) for each solution in the pool?
I tried but it returns the exact same values for each solution in the pool.
Thanks.
Vincent
0
Please sign in to leave a comment.
Comments
7 comments