Handling very large values in the objective function for optimal transport
Answered
I am running optimal transport between two uniform distributions. The functional form of the objective function is $\frac{1}{|x - y|}$. To generate the objective function, I computed the pairwise distance between the points between 0 to 99. Along the diagonal the values of the functions become infinite. To avoid this issue I manually updated the value with 10e+50 a very large value. However, this gives some incorrect answers while running the code
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 648 rows, 104976 columns and 209952 nonzeros
Model fingerprint: 0xc54bcb89
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [3e-03, 1e+25]
Bounds range [1e+00, 1e+00]
RHS range [3e-03, 3e-03]
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: 0.18s
Presolved: 648 rows, 104976 columns, 209952 nonzeros
Ordering time: 0.00s
Barrier statistics:
AA' NZ : 1.304e+04
Factor NZ : 1.320e+04 (roughly 5 MB of memory)
Factor Ops : 1.430e+06 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 4.48245890e+01 0.00000000e+00 1.62e+01 1.39e-17 5.61e-03 0s
1 1.07890397e+00 -1.99630415e-02 3.51e-01 4.44e-16 1.28e-04 0s
2 8.72964908e-03 -1.94654669e-02 3.62e-16 4.44e-16 1.07e-06 0s
3 7.82127049e-03 5.53707862e-03 4.34e-18 2.22e-16 8.65e-08 0s
4 6.47924927e-03 6.05500570e-03 2.99e-17 4.44e-16 1.61e-08 0s
5 6.34024190e-03 6.13826525e-03 1.82e-17 1.11e-16 7.65e-09 0s
6 6.28548167e-03 6.15823139e-03 2.43e-17 1.11e-16 4.82e-09 0s
7 6.22184332e-03 6.16552853e-03 3.99e-17 2.22e-16 2.13e-09 0s
8 6.19988814e-03 6.17017509e-03 6.42e-17 1.11e-16 1.13e-09 0s
9 6.18625194e-03 6.17198528e-03 8.28e-17 2.22e-16 5.40e-10 0s
10 6.17884466e-03 6.17250410e-03 7.29e-17 5.55e-17 2.40e-10 0s
11 6.17532128e-03 6.17274983e-03 5.94e-17 5.55e-17 9.74e-11 0s
12 6.17303241e-03 6.17282696e-03 1.17e-16 2.22e-16 7.78e-12 0s
13 6.17283987e-03 6.17283946e-03 1.87e-16 2.22e-16 1.55e-14 0s
14 6.17283951e-03 6.17283951e-03 2.06e-15 2.22e-16 2.49e-19 0s
Barrier solved model in 14 iterations and 0.36 seconds (0.14 work units)
Optimal objective 6.17283951e-03
Crossover log...
96 DPushes remaining with DInf 0.0000000e+00 0s
0 DPushes remaining with DInf 0.0000000e+00 0s
0 PPushes remaining with PInf 0.0000000e+00 0s
Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 0s
Iteration Objective Primal Inf. Dual Inf. Time
99 6.1728395e-03 0.000000e+00 0.000000e+00 0s
Use crossover to convert LP symmetric solution to basic solution...
Crossover log...
0 DPushes remaining with DInf 4.2603733e-05 1s
69 PPushes remaining with PInf 0.0000000e+00 1s
0 PPushes remaining with PInf 0.0000000e+00 1s
Push phase complete: Pinf 0.0000000e+00, Dinf 6.6939279e-05 1s
Iteration Objective Primal Inf. Dual Inf. Time
385 6.1729325e-03 0.000000e+00 6.693928e-05 1s
406 6.1728744e-03 0.000000e+00 0.000000e+00 1s
Solved with barrier
Solved in 406 iterations and 0.71 seconds (0.23 work units)
Optimal objective 6.172874353e-03
How to handle large values in objective functions in optimal transport if the smallest one is very small and the largest one is very very large relatively?
-
Did you consider skipping those entries? I assume that the fraction \(\frac{1}{|x-y|}\) is some weight/cost coefficient for the distance from \(x\) to \(y\) correct? I think it is best to forbid direct transports from \(x\) to \(x\) and completely omit those \(\infty\) values.
Best regards,
Jaromił0 -
Thanks for the reply Jaromił Najman!
Yes $\frac{1}{|x-y|}$ is the cost function coefficient from $x$ to $y$. I have two confusions here,
1. If I change the diagonal values, where the transportation takes place between $x$ to $x$ to some smaller values like 10e+6, does it work?
2. As you advised if I remove the diagonal values completely from the constraint (LP) matrix as well as from the cost function matrix, Does it give the same transport map and objective minimum as the case (1) above?
0 -
If I change the diagonal values, where the transportation takes place between $x$ to $x$ to some smaller values like 10e+6, does it work?
You would have to test it yourself. It would definitely improve the numerics of your model.
As you advised if I remove the diagonal values completely from the constraint (LP) matrix as well as from the cost function matrix, Does it give the same transport map and objective minimum as the case (1) above?
I don't know your model, so you have to make sure yourself that the model still makes sense after you remove the diagonal values.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
3 comments