pre-solve is buggy
Answered
-
The \( \texttt{vs} \) array contains extremely small values like \(3.9268 \cdot 10^{-11} \) and \( 6.1232 \cdot 10^{-17} \). The latter is smaller than the machine precision of \(~10^{-16}\) for 64-bit doubles and is thus ignored by the solver:
Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
Additionally, some RHS values defined in the MATLAB program are \( 10^{-7} \).
It's good modeling practice to not include in the model any meaningful values that are less than the feasibility tolerance. Gurobi's default feasibility tolerance is \( 10^{-6} \), which is several orders of magnitude larger than many of the values in your model. Section 2.3 of this paper on ill-conditioning and numerical instability has a nice example of how model values smaller than the feasibility tolerance can lead to unexpected infeasibilities.
To resolve the issue, try reformulating the model so none of its values are less than the feasibility tolerance. Setting the FeasibilityTol parameter to a smaller value may also help to a certain degree.
0 -
That's all fine and well, good practice and everything. However, I expect gurobi to behave consistently (e.g. like mosek) even in the face of numerical instability. Meaning, if it fails, then it should fail in all cases. Right now, switching the order of constraints or enabling/disabling pre-solve produce different results.
Having said that, I guess that you can't really control numerical issues that way, and changing these parameters affect problem stability, and there's nothing to do about it (i.e. it's not a bug) except trying all options--which is impractical.
I'll consider your advice, thanks.
0 -
I have a related issue.
I have a mixed-int model that was reported infeasible. I _added_ a constraint to the model, and it was solved fine. I turned off the presolve instead of adding the constraint, and it was fine as well.
No warnings this time, but it probably has again something to do with numerical issues. I tried lowering:
options.gurobi.FeasibilityTol = 1e-2;options.gurobi.IntFeasTol = 1e-1;which didn't help.1. Is there a way for me to detect that an infeasibility might have been caused by numerical issues? It's probably tricky in MI (unlike in SOCP) because you prune parts of the tree based on a threshold regardless of numerics.2. Can gurobi tell me the condition number of the problem matrix before and after the presolve so I'll have some indication that this might be the issue, and I should try without presolve?I'm trying to find a better solution than trying without presolve to confirm infeasibility each time--which could be very slow.0 -
I agree that this sounds like a similar numerical issue.
Poor numerics and round-off error can put a model on the border of feasibility. In such cases, the solver can correctly declare, with respect to its tolerances, that a model is feasible or infeasible depending on the basis. Adding a constraint can result in Gurobi selecting different bases corresponding to different conclusions of feasibility. The example in Section 2.3 of the paper on ill-conditioning and numerical instability I mentioned shows how a different basis can result in a different conclusion of feasibility.
I would try tightening the feasibility tolerance instead of relaxing it. It's possible a particular presolve reduction is resulting in the infeasibility. This is likely a perfectly reasonable reduction involving extremely small model coefficients that are several orders of magnitude smaller than the feasibility tolerance. If you decrease the feasibility tolerance, Gurobi may interpret the very small coefficient values as "meaningful" and not employ this reduction. In any case, parameters do not address the root cause of the problem, which is the model's numerics.
Note that Gurobi's feasibility tolerances should not be interpreted as slack on constraints. In other words, Gurobi does not actively try to exploit tolerances to find better (or feasible) solutions. For example, consider the trivial problem \( \min \{x : x \geq 0\} \) and Gurobi's default feasibility tolerance of \(10^{-6}\). We should expect Gurobi to return an optimal solution of \( x = 0 \), not \( x = 10^{-6} \). A model should be relaxed by modifying its constraints/bounds.
1. A good heuristic to determine if the infeasibility could be caused by numerical issues is to check the coefficient statistics. Some examples of coefficient values that commonly cause problems are:
- Values close to or less than the feasibility tolerance (default \(10^{-6}\)).
- A linear coefficient matrix spanning several orders of magnitude. Problems tend to occur more frequently for coefficient matrices spanning \(\approx 8\) orders of magnitude. Smaller relative ranges of coefficients are better.
- Large objective coefficients and RHS values.
More examples can be found in Gurobi's Guidelines for Numerical Issues. If any of the above are present in your model, the best thing to do is reformulate the model.
2. The condition number is calculated for a square matrix. In general, a model's constraint matrix has many different condition numbers depending on the chosen basis. Gurobi only reports the condition number for an optimal simplex basis, which is obtained by solving an LP via primal or dual simplex, or by performing crossover after solving the LP with the barrier algorithm. The condition number cannot be queried at arbitrary points in the solution process, and it is only available for LPs.
0 -
I see, thanks for the detailed answer.
In this specific case, I found an issue with my model, and so far it seems fine after resolving it.
https://github.com/yalmip/YALMIP/discussions/1010
In the future, I'll try to have a look at what yalmip feeds gurobi and search for extreme numbers.
0 -
Can you perhaps take a look at the following model:
https://drive.google.com/file/d/17dM2GdJYPVZ2FkFDZ0Qd4uOXnZdW4lgh/view
It's exported from yalmip, and it can be run as:
gurobi( model, model.params )
When the presolve is set to default (aggressive), it reports infeasible. When it's set to conservative, there are no issues.
The numerics don't look too bad:
Coefficient statistics:
Matrix range [1e+00, 1e+01]
Objective range [1e-03, 1e+03]
Bounds range [1e+00, 1e+00]
RHS range [6e-01, 1e+03]------
UPDATE: my bad, looks like a numerical issue after all. I set IntFeasTol=2e-7. Setting it back to default resolves the issue.
0
Please sign in to leave a comment.
Comments
6 comments