I’m solving a linear problem with JuMP and Gurobi, and for some formulations I end up getting the following behaviour:
Academic license - for non-commercial use only
Optimize a model with 6725 rows, 6346 columns and 17254 nonzeros
Coefficient statistics:
Matrix range [1e-07, 1e+07]
Objective range [1e+00, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [4e-07, 1e+04]
Warning: Model contains large matrix coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 3752 rows and 3944 columns
Presolve time: 0.01s
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 1.983774e+06 0.000000e+00 0s
Solved in 1501 iterations and 0.10 seconds
Infeasible model
For another slightly different formulation I get the following behaviour:
What I don’t understand is why the solver declares the model to be infeasible AFTER iterating - surely for a linear problem this could / should be determined before solving? Is it possible that this is due to the large range of matrix coefficients?
I don’t know anything about this particular implementation but typically for optimization and linear programming, the algorithm runs in two phases. In phase 1, the algorithm looks for a feasible solution. In phase 2, the feasible solution is optimized to find the optimal solution.
Both phases use essentially the same algorithm, so determining whether a problem is feasible does indeed require iteration.
That sort of makes sense to me. I was thinking that in the presolve phase, the solver uses the inequality constraints to determine whether a feasible region exists or not. I assume that means solving a system of linear equations, so makes sense that you would have to iterate there as well as when you find the optimal solution. Thank you! Hopefully I figure out what I’m doing wrong soon…
The poor problem scaling is almost certainly the issue. My guess is that Gurobi re-scales your model, finds an initial “feasible” solution to the re-scaled problem and solves. But, when it attempts to un-scale the solution back to the original problem, the solution is numerically infeasible.
When every you see this warning, take it’s advice:
Warning: Model contains large matrix coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Thanks, I’m going to try scaling. One question I have is that I have a parameter which varies between 0 and 1. Ideally, I would like Gurobi (or any solver really) to ignore coefficients which are less than say 10^-4, but how do I do that? I could write my constraints as something like:
for i in I, j in J
if P[i,j] >= 10^-4
<write constraint>
end
end
But writing that for every constraint feels clunky. Does Gurobi understand that 0.0 is 0? Otherwise another thing I could do is just set any values less than 10^-4 to 10^-4 (i.e. small) and hope that my solution doesn’t change.
So I finally scaled my problem, but the issue persists. For one formulation of my problem I get the following Gurobi output:
Academic license - for non-commercial use only
Optimize a model with 6725 rows, 6346 columns and 17263 nonzeros
Coefficient statistics:
Matrix range [2e-04, 1e+02]
Objective range [1e+00, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [3e-07, 1e+01]
Presolve removed 3752 rows and 4783 columns
Presolve time: 0.01s
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 1.953717e+03 0.000000e+00 0s
Solved in 1422 iterations and 0.18 seconds
Infeasible model
For another variation, it uses the barrier method and then encounters trouble:
I recently replaced a lot of my dummy variables (e.g. y = sum(x) where both y and x are JuMP variables) with JuMP expressions, since for various reasons I assumed that this must be the cause of the problem. I have yet to confirm, but it looks like it was.