Checking numerical issues in optimal transport
Answered
I have beend running optimal transport between two distributions.
However, the cost function has values which are very large and still GUROBI
gives optimal objective value. My doubt is whether this answer is reliable.
KIndly clarify whether the warning message should be taken very seriously and also
please clarify whether the optimal objective solutions is accurate.
I have attached the result from GUROBI below.
----------------------------OUTPUT FROM GUROBI-----------------------------------------
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 2753 rows, 1566996 columns and 3133992 nonzeros
Model fingerprint: 0x220b4012
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [6e+05, 1e+11]
Bounds range [1e+00, 1e+00]
RHS range [1e-07, 2e-02]
Warning: Model contains large objective coefficients
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve time: 4.93s
Presolved: 2753 rows, 1566996 columns, 3133992 nonzeros
Ordering time: 0.04s
Barrier statistics:
AA' NZ : 1.567e+06
Factor NZ : 2.228e+06 (roughly 600 MB of memory)
Factor Ops : 2.151e+09 (less than 1 second per iteration)
Threads : 3
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 3.10898804e+13 0.00000000e+00 1.95e+02 9.00e+10 8.07e+07 6s
1 8.61000209e+12 -1.84556894e+09 1.43e+02 2.90e-04 7.07e+07 7s
2 8.05164039e+09 -1.84713281e+09 7.35e-03 4.58e-05 6.66e+03 7s
Barrier performed 2 iterations in 7.36 seconds (2.04 work units)
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Solved in 13408 iterations and 7.43 seconds (2.35 work units)
Optimal objective 5.751498609e+05
Solution quality statistics for model ot_copy :
Maximum violation (unscaled/scaled):
Bound : 4.79999374e-08 / 4.79999374e-08 (C1040075)
Constraint : 0.00000000e+00 / 0.00000000e+00
Dual : 0.00000000e+00 / 0.00000000e+00
OBJECTIVE VALUE= 575149.8608509641
-
As you can see from the solution quality statistics, the final solution has no constraint violations and only very low bound violations (which are still 2 orders of magnitude below the default feasibility tolerances). Thus, your solution point should be reliable. You should still check whether the solution makes sense for your application though.
Sometimes a model with possibly bad numerics can still solve perfectly fine. The Warning you see does not always mean that something will go wrong during the solution process. It shall just make clear that if the final solution has large violations then it is very likely caused by large coefficients and a badly scaled model. Gurobi will try a lot of things to still solve the model as good as possible even with shaky numerics. If however, you start seeing big solution point violations, you should try to improve your model's numerics as described in our Guidelines for Numerical Issues.
Best regards,
Jaromił1 -
Thank you so much Jaromił Najman
0
Please sign in to leave a comment.
Comments
2 comments