Numerical Problem encountered and Gurobi can't solve the model
AnsweredDear Sir/Madam,
I encountered a numerical problem while solving a LP with the barrier method. If I don't open the homogeneous barrier method, the barrier method can't converge. The model seems not hard. I wonder why this could happen. Here is the log.
Optimize a model with 21000 rows, 12170 columns and 526000 nonzeros
Coefficient statistics:
Matrix range [3e-06, 7e+01]
Objective range [1e-03, 1e-03]
Bounds range [0e+00, 0e+00]
RHS range [4e-03, 2e+01]
Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
[New Thread 0x7fffa2f84700 (LWP 14251)]
[New Thread 0x7fff9bfff700 (LWP 14252)]
Warning: Concurrent optimizer requires crossover - forcing it on
Presolve removed 11000 rows and 1675 columns
Presolve time: 0.42s
Presolved: 10000 rows, 10495 columns, 514000 nonzeros
Ordering time: 0.07s
Barrier statistics:
Dense cols : 495
Free vars : 495
AA' NZ : 5.040e+05
Factor NZ : 1.480e+06 (roughly 23 MBytes of memory)
Factor Ops : 4.237e+08 (less than 1 second per iteration)
Threads : 4
[New Thread 0x7fff998eb700 (LWP 14253)]
[New Thread 0x7fff990ea700 (LWP 14254)]
[New Thread 0x7fff988e9700 (LWP 14255)]
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 2.26467186e+02 0.00000000e+00 9.04e+01 0.00e+00 9.95e+00 1s
1 1.11261373e+02 -1.00593256e+01 6.88e-09 1.95e-02 1.89e+00 1s
2 1.07445474e+02 -8.39708070e+00 4.28e-09 5.79e-04 6.58e-02 1s
3 6.68627446e+01 -7.61819802e+00 1.82e-07 4.66e-05 1.06e-02 1s
4 1.23345947e+01 -6.79149639e+00 1.41e-07 4.22e-10 1.74e-03 1s
5 7.61975150e+00 -6.02295136e+00 3.68e-07 8.79e-10 1.23e-03 1s
6 5.15076485e+00 -4.22868788e+00 2.88e-07 4.31e-09 7.94e-04 1s
7 3.52622524e+00 -3.67563521e+00 2.44e-07 3.73e-09 5.78e-04 1s
8 2.97375533e+00 -2.83173747e+00 1.68e-07 5.69e-09 4.19e-04 1s
9 1.87837788e+00 -1.95692653e+00 1.34e-07 3.25e-09 2.20e-04 1s
10 1.61839036e+00 -1.78134563e+00 1.52e-07 4.47e-09 1.74e-04 1s
11 1.28903208e+00 -1.19363107e+00 1.26e-07 3.25e-09 7.62e-05 1s
12 1.23219331e+00 -1.01562771e+00 1.71e-07 5.83e-09 4.60e-05 2s
13 1.22087180e+00 -9.82617237e-01 1.52e-07 5.94e-09 3.82e-05 2s
14 1.20483788e+00 -9.03907288e-01 1.47e-07 6.67e-09 2.48e-05 2s
15 1.19522936e+00 -8.79742628e-01 1.71e-07 6.41e-09 1.95e-05 2s
16 1.16259660e+00 -8.63162002e-01 2.30e-07 5.70e-09 1.58e-05 2s
17 1.17645373e+00 -8.63627091e-01 1.96e-07 7.44e-09 1.44e-05 2s
18 1.16816596e+00 -8.45590498e-01 2.42e-07 5.87e-09 1.10e-05 2s
19 1.16105543e+00 -8.16775989e-01 1.54e-07 3.82e-09 7.92e-06 2s
20 1.15511565e+00 -7.90044344e-01 1.60e-07 2.71e-09 3.64e-06 2s
21 1.15380845e+00 -7.86445124e-01 1.61e-07 1.87e-09 2.81e-06 2s
22 1.15379887e+00 -7.87224145e-01 1.71e-07 1.84e-09 2.70e-06 2s
23 1.14899584e+00 -7.78915072e-01 1.53e-07 2.60e-09 1.41e-06 2s
24 1.14863550e+00 -7.79273451e-01 1.79e-07 3.40e-09 1.40e-06 2s
25 1.14816067e+00 -7.79165270e-01 1.60e-07 3.39e-09 1.31e-06 2s
26 1.14695158e+00 -7.76561403e-01 1.54e-07 2.28e-09 8.69e-07 2s
27 1.14602841e+00 -7.76938479e-01 1.09e-07 1.68e-09 4.98e-07 2s
28 1.14576264e+00 -7.75084926e-01 1.32e-07 1.36e-09 3.56e-07 2s
29 1.14577772e+00 -7.74895854e-01 1.74e-07 1.46e-09 3.47e-07 2s
30 1.14576224e+00 -7.75245575e-01 1.38e-07 1.17e-09 3.06e-07 2s
31 1.14563798e+00 -7.74957806e-01 1.66e-07 1.77e-09 2.94e-07 2s
32 1.14560715e+00 -7.74921081e-01 1.71e-07 1.63e-09 2.93e-07 2s
33 1.14544196e+00 -7.75978633e-01 1.74e-07 1.55e-09 2.76e-07 2s
34 1.14535790e+00 -7.76170768e-01 1.44e-07 1.35e-09 2.46e-07 2s
35 1.14534927e+00 -7.76590678e-01 1.67e-07 1.84e-09 2.46e-07 3s
36 1.14533100e+00 -7.75942728e-01 1.44e-07 2.04e-09 2.43e-07 3s
37 1.14530083e+00 -7.77467472e-01 1.57e-07 1.98e-09 2.24e-07 3s
38 1.14530699e+00 -7.77852041e-01 2.11e-07 1.92e-09 1.92e-07 3s
39 1.14526873e+00 -7.76964868e-01 1.97e-07 1.79e-09 1.85e-07 3s
40 1.14526041e+00 -7.76766301e-01 2.82e-07 1.73e-09 1.85e-07 3s
41 1.14532754e+00 -7.77118056e-01 2.57e-07 3.12e-09 1.80e-07 3s
42 1.14532012e+00 -7.77395662e-01 2.41e-07 3.36e-09 1.73e-07 3s
43 1.14530502e+00 -7.76863875e-01 1.93e-07 3.36e-09 1.39e-07 3s
44 1.14527638e+00 -7.76646297e-01 1.10e-07 3.34e-09 1.35e-07 3s
45 1.14524371e+00 -7.76671714e-01 1.76e-07 2.21e-09 1.24e-07 3s
46 1.14500291e+00 -7.76145522e-01 1.18e-07 3.44e-09 7.90e-08 3s
47 1.14495691e+00 -7.75683197e-01 1.09e-07 2.38e-09 5.99e-08 3s
48 1.14497685e+00 -7.77282096e-01 1.65e-07 4.51e-09 5.55e-08 3s
49 1.14497520e+00 -7.76467458e-01 1.70e-07 4.24e-09 4.62e-08 3s
50 1.14497354e+00 -7.76446534e-01 1.84e-07 4.15e-09 4.62e-08 3s
51 1.14498354e+00 -7.76536256e-01 2.57e-07 3.78e-09 4.36e-08 3s
52 1.14498148e+00 -7.77550768e-01 2.37e-07 6.88e-09 3.88e-08 3s
53 1.14497178e+00 -7.77816393e-01 2.26e-07 4.94e-09 3.26e-08 3s
54 1.14497127e+00 -7.77766552e-01 2.28e-07 4.86e-09 3.21e-08 3s
55 1.14497051e+00 -7.77564458e-01 2.69e-07 4.43e-09 3.14e-08 3s
56 1.14496853e+00 -7.77634978e-01 3.46e-07 3.64e-09 2.91e-08 3s
57 1.14496888e+00 -7.77446029e-01 2.48e-07 3.91e-09 2.81e-08 3s
58 1.14496017e+00 -7.77345110e-01 2.66e-07 3.15e-09 2.43e-08 4s
59 1.14494409e+00 -7.76775354e-01 2.59e-07 6.72e-09 1.88e-08 4s
60 1.14492302e+00 -7.75692122e-01 3.11e-07 3.19e-09 9.68e-09 4s
61 1.14491337e+00 -7.75542155e-01 2.51e-07 2.72e-09 8.42e-09 4s
62 1.14491352e+00 -7.75542273e-01 2.62e-07 2.94e-09 8.41e-09 4s
63 1.14491106e+00 -7.75494225e-01 2.28e-07 3.01e-09 8.05e-09 4s
64 1.14491013e+00 -7.75401691e-01 1.12e-07 2.82e-09 7.75e-09 4s
65 1.14490541e+00 -7.75622353e-01 3.21e-07 3.32e-09 6.44e-09 4s
66 1.14490634e+00 -7.75558664e-01 1.95e-07 3.56e-09 6.00e-09 4s
67 1.14490729e+00 -7.75535687e-01 1.31e-07 3.60e-09 5.94e-09 4s
68 1.14490072e+00 -7.75681606e-01 1.40e-07 4.02e-09 5.13e-09 4s
69 1.14490070e+00 -7.75691849e-01 1.22e-07 4.01e-09 5.13e-09 4s
70 1.14489914e+00 -7.75625315e-01 1.15e-07 3.88e-09 4.87e-09 4s
71 1.14489228e+00 -7.75358122e-01 2.08e-07 3.02e-09 3.47e-09 4s
72 1.14489081e+00 -7.75733215e-01 1.57e-07 2.43e-09 2.97e-09 4s
73 1.14488671e+00 -7.75300281e-01 1.65e-07 2.89e-09 1.89e-09 4s
74 1.14488639e+00 -7.75428621e-01 1.69e-07 3.53e-09 1.71e-09 4s
75 1.14488555e+00 -7.75206886e-01 2.38e-07 3.83e-09 1.51e-09 4s
76 1.14488547e+00 -7.74932852e-01 1.69e-07 4.55e-09 1.33e-09 4s
77 1.14488534e+00 -7.75279288e-01 1.73e-07 6.12e-09 8.75e-10 4s
78 1.14488368e+00 -7.75938963e-01 1.52e-07 2.65e-09 3.93e-10 4s
79 1.14488358e+00 -7.75357118e-01 2.48e-07 3.62e-09 3.26e-10 4s
80 1.14488302e+00 -7.74716518e-01 1.60e-07 4.21e-09 2.40e-10 4s
81 1.14488258e+00 -7.73234119e-01 1.45e-07 7.80e-09 1.82e-10 5s
82 1.14488251e+00 -7.73505850e-01 1.39e-07 8.33e-09 1.67e-10 5s
83 1.14488241e+00 -7.74555310e-01 1.62e-07 9.28e-09 7.21e-11 5s
84 1.14488226e+00 -7.74725730e-01 1.65e-07 6.48e-09 5.33e-11 5s
85 1.14488226e+00 -7.74647669e-01 1.39e-07 6.39e-09 4.19e-11 5s
86 1.14488215e+00 -7.74630564e-01 2.04e-07 1.03e-08 5.81e-12 5s
87 1.14488209e+00 -7.74657673e-01 1.41e-07 9.72e-09 2.33e-12 5s
88 1.14488209e+00 -7.74531463e-01 1.95e-07 1.01e-08 2.18e-12 5s
89 1.14488209e+00 -7.74477155e-01 2.19e-07 9.85e-09 2.17e-12 5s
90 1.14488209e+00 -7.74525349e-01 1.40e-07 2.81e-08 2.01e-12 5s
91 1.14488209e+00 -7.74545830e-01 1.71e-07 2.69e-08 2.00e-12 5s
92 1.14488209e+00 -7.74560722e-01 1.55e-07 2.66e-08 1.94e-12 5s
93 1.14488209e+00 -7.74658997e-01 1.22e-07 2.59e-08 1.73e-12 5s
94 1.14488209e+00 -7.74952493e-01 1.90e-07 2.22e-08 1.35e-12 5s
95 1.14488209e+00 -7.74942201e-01 1.49e-07 1.49e-08 1.24e-12 5s
96 1.14488209e+00 -7.74943226e-01 1.16e-07 1.49e-08 1.22e-12 5s
97 1.14488209e+00 -7.74966794e-01 1.35e-07 2.77e-08 1.14e-12 5s
Barrier performed 97 iterations in 5.23 seconds
Numerical trouble encountered
Model may be infeasible or unbounded. Consider using the
homogeneous algorithm (through parameter 'BarHomogeneous')
Here is the MPS file for the model.
https://www.dropbox.com/sh/fbf9xl5te6cneyu/AAC7xnCw_C4pghbuxy9Fu8_da?dl=0
Best,
Bo
-
Hi Bo,
The Barrier algorithm is very sensitive to numerical issues such as coefficient scaling or almost parallel constraints. You could try improving the range of your coefficient matrix, see Guidelines for Numerical Issues. You could also try using the Homogeneous Barrier algorithm which is better in tackling numerical issues. You could also try increasing the NumericFocus parameter or using one of the simplex methods to solve your problem by setting the Method parameter. The dual simplex should work best in your case (Method = 1).
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment