Why Barrier report numerical trouble encountered even the ranges are not large?
Ongoing
Hello!
I am using Barrier with persovle on to solve an LP. So I rescaled the model to make the matrix and objective range relatively small. And this model is solved with dual simplex without an issue. But when I switched to Barrier, it reported the numerical issue encountered. I need to scale the model up to a much larger one so I am going to need Barrier to solve it fast. In such case, do I need to further rescale the model to have even smaller ranges? Or is there any other solution that doesn't sacrifice too much performance while using Barrier? Because it is hard to rescale further.
The output log is attached. Thanks in advance.
Kind regards,
Hongyu.
Model fingerprint: 0xcd057ed6
Coefficient statistics:
Matrix range [1e-04, 2e+04]
Objective range [6e-01, 2e+03]
Bounds range [0e+00, 0e+00]
RHS range [1e-01, 1e+03]
Presolve removed 81660 rows and 49380 columns
Presolve time: 1.41s
Presolved: 289712 rows, 712740 columns, 2402574 nonzeros
Ordering time: 2.30s
Barrier statistics:
Dense cols : 12
Free vars : 15693
AA' NZ : 3.543e+06
Factor NZ : 3.045e+07 (roughly 700 MB of memory)
Factor Ops : 5.356e+09 (less than 1 second per iteration)
Threads : 8
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -2.40240648e+11 3.07930172e+09 2.00e+07 6.08e+02 2.29e+08 5s
1 -1.36091287e+11 3.85190263e+09 4.34e+06 7.34e+03 5.49e+07 5s
2 -9.94340058e+11 3.80477961e+09 5.25e+05 6.83e+03 4.72e+07 6s
3 -1.00415108e+12 3.72550505e+09 3.97e+04 1.59e+03 1.09e+07 6s
4 -7.04851902e+11 3.77142622e+09 1.49e+03 5.71e+02 3.82e+06 7s
5 -5.56735775e+11 1.64940111e+09 5.90e+02 1.40e+02 1.24e+06 7s
6 -2.88873336e+11 9.36792842e+08 1.50e+02 5.40e+01 4.56e+05 7s
7 -1.24067611e+11 3.56691582e+08 4.94e+01 1.50e+01 1.51e+05 8s
8 -1.32706878e+10 8.44224669e+07 1.83e+00 1.09e+00 1.39e+04 8s
9 -2.40871126e+09 4.37418704e+07 2.97e-01 2.14e-01 2.53e+03 8s
10 -1.01176831e+09 3.26167380e+07 1.18e-01 2.74e-03 1.08e+03 9s
11 -4.36085869e+08 2.83322506e+07 4.97e-02 1.09e-03 4.78e+02 9s
12 -2.53251522e+08 2.70390427e+07 2.86e-02 8.79e-04 2.87e+02 9s
13 -1.95481903e+08 2.67258768e+07 2.26e-02 8.24e-04 2.27e+02 10s
14 -1.06350144e+08 2.18199844e+07 1.35e-02 3.46e-04 1.30e+02 10s
15 -6.30170224e+07 1.75846458e+07 9.37e-03 2.00e-04 8.08e+01 11s
16 -4.64458196e+07 1.59399899e+07 1.02e-02 1.96e-04 6.19e+01 11s
17 -2.66310906e+07 1.47716529e+07 8.88e-03 1.66e-04 4.00e+01 11s
18 -1.62282081e+07 1.11351346e+07 6.54e-03 9.46e-05 2.56e+01 12s
19 -7.79618594e+06 8.79672104e+06 4.14e-03 6.39e-05 1.44e+01 13s
20 -4.54682358e+06 6.51967196e+06 1.82e-03 4.11e-05 8.78e+00 14s
21 -2.47458445e+06 5.81273095e+06 1.16e-03 3.68e-05 5.89e+00 15s
22 -1.71121304e+06 4.76636789e+06 8.53e-04 3.07e-05 4.17e+00 16s
23 -1.12940502e+06 4.07611454e+06 7.24e-04 2.35e-05 2.96e+00 17s
24 -6.71295365e+05 3.67587326e+06 7.79e-04 2.19e-05 2.18e+00 18s
25 -5.79110461e+05 3.12282829e+06 7.71e-04 1.54e-05 1.66e+00 19s
26 -4.86900476e+05 2.92241576e+06 6.97e-04 1.32e-05 1.43e+00 20s
27 -3.77397571e+05 2.61630268e+06 5.71e-04 9.90e-06 1.12e+00 21s
28 -2.57051548e+05 2.51645979e+06 5.48e-04 8.93e-06 9.43e-01 22s
29 -2.25011914e+05 2.34475003e+06 5.28e-04 7.32e-06 7.90e-01 23s
30 -1.58183597e+05 2.22735569e+06 5.04e-04 6.07e-06 6.42e-01 24s
31 -1.34910590e+05 2.06902562e+06 5.42e-04 4.77e-06 5.20e-01 25s
32 -1.03972417e+05 1.92662111e+06 6.48e-04 3.68e-06 4.00e-01 26s
33 -9.39748246e+04 1.86464122e+06 6.84e-04 3.27e-06 3.58e-01 27s
34 -8.53082273e+04 1.82496627e+06 6.96e-04 2.98e-06 3.30e-01 28s
35 -7.81117691e+04 1.81045075e+06 6.88e-04 2.89e-06 3.15e-01 29s
36 -6.39140087e+04 1.78891560e+06 6.29e-04 2.76e-06 2.90e-01 30s
37 -5.12439772e+04 1.70326883e+06 5.74e-04 2.25e-06 2.36e-01 31s
38 -4.77224372e+04 1.68249785e+06 5.78e-04 2.13e-06 2.23e-01 33s
39 -4.58244633e+04 1.65519466e+06 5.80e-04 1.98e-06 2.10e-01 34s
40 -4.33535630e+04 1.65088222e+06 5.81e-04 1.96e-06 2.06e-01 35s
41 -3.95033021e+04 1.63406341e+06 5.82e-04 1.87e-06 1.95e-01 36s
42 -3.43303048e+04 1.61121508e+06 5.85e-04 1.75e-06 1.81e-01 37s
43 -2.97486695e+04 1.58871948e+06 5.87e-04 1.64e-06 1.68e-01 38s
44 -2.08445761e+04 1.56342789e+06 5.91e-04 1.51e-06 1.50e-01 39s
45 -1.71339053e+04 1.53953533e+06 5.89e-04 1.58e-06 1.37e-01 40s
46 -1.19754765e+04 1.52094748e+06 5.49e-04 1.40e-06 1.26e-01 41s
47 -8.90823963e+03 1.49609844e+06 5.44e-04 1.21e-06 1.14e-01 42s
48 -5.12804609e+03 1.47367706e+06 5.49e-04 1.09e-06 1.04e-01 43s
49 -4.62606798e+02 1.44807637e+06 5.67e-04 9.80e-07 9.18e-02 44s
50 3.77400518e+03 1.43018953e+06 5.82e-04 8.96e-07 8.23e-02 45s
51 6.04970567e+03 1.40998930e+06 5.81e-04 8.05e-07 7.45e-02 46s
52 6.05042474e+03 1.40997994e+06 5.81e-04 8.05e-07 7.45e-02 47s
53 8.89551921e+03 1.40381639e+06 5.77e-04 7.78e-07 7.03e-02 48s
54 1.02836076e+04 1.38166776e+06 5.76e-04 6.66e-07 6.26e-02 49s
55 1.21481826e+04 1.36979845e+06 5.65e-04 6.29e-07 5.85e-02 50s
56 1.28725765e+04 1.36411085e+06 5.67e-04 6.12e-07 5.68e-02 51s
57 1.38629564e+04 1.35836931e+06 5.58e-04 5.95e-07 5.50e-02 53s
58 1.47269535e+04 1.35427493e+06 5.51e-04 5.88e-07 5.33e-02 54s
59 1.58426503e+04 1.35277422e+06 5.41e-04 5.87e-07 5.21e-02 55s
60 1.73620976e+04 1.33708774e+06 5.27e-04 5.83e-07 4.75e-02 56s
61 1.77650495e+04 1.33481058e+06 5.30e-04 6.80e-07 4.65e-02 57s
62 1.89351355e+04 1.32181387e+06 5.35e-04 6.41e-07 4.32e-02 58s
63 1.97945163e+04 1.31569490e+06 5.39e-04 6.23e-07 4.11e-02 59s
64 2.02402751e+04 1.31162719e+06 5.40e-04 6.07e-07 4.00e-02 61s
65 2.04028708e+04 1.31065770e+06 5.41e-04 6.02e-07 3.97e-02 61s
66 2.16982007e+04 1.30575708e+06 5.47e-04 5.79e-07 3.73e-02 62s
67 2.17519110e+04 1.30529015e+06 5.47e-04 5.78e-07 3.72e-02 63s
68 2.19806053e+04 1.30388397e+06 5.47e-04 5.71e-07 3.67e-02 64s
69 2.25643732e+04 1.29949875e+06 5.48e-04 5.53e-07 3.53e-02 65s
70 2.26606397e+04 1.29874629e+06 5.48e-04 5.51e-07 3.51e-02 66s
71 2.26852271e+04 1.29751133e+06 5.48e-04 5.55e-07 3.48e-02 67s
72 2.26873251e+04 1.29747951e+06 5.48e-04 5.54e-07 3.48e-02 67s
73 2.28569149e+04 1.29675122e+06 5.50e-04 5.54e-07 3.46e-02 68s
74 2.31062702e+04 1.29382099e+06 5.63e-04 4.40e-07 3.35e-02 69s
75 2.31143787e+04 1.29377931e+06 5.63e-04 4.39e-07 3.34e-02 70s
76 2.35342858e+04 1.29231701e+06 5.92e-04 4.87e-07 3.26e-02 72s
77 2.35967005e+04 1.29197673e+06 5.93e-04 4.86e-07 3.25e-02 73s
78 2.41037914e+04 1.28813427e+06 6.05e-04 8.03e-07 3.10e-02 74s
79 2.41058897e+04 1.28808930e+06 6.05e-04 8.06e-07 3.10e-02 75s
80 2.42526096e+04 1.28648220e+06 6.06e-04 8.01e-07 3.08e-02 75s
81 2.44698084e+04 1.28599927e+06 6.11e-04 7.99e-07 3.05e-02 76s
82 2.44775184e+04 1.28595332e+06 6.11e-04 8.02e-07 3.05e-02 77s
83 2.44790756e+04 1.28590058e+06 6.12e-04 8.05e-07 3.05e-02 78s
84 2.47964601e+04 1.28537509e+06 6.12e-04 8.02e-07 3.02e-02 79s
Barrier performed 84 iterations in 78.69 seconds (88.53 work units)
Numerical trouble encountered
Model may be infeasible or unbounded. Consider using the
homogeneous algorithm (through parameter 'BarHomogeneous')
User-callback calls 5706, time in user-callback 0.01 sec
done in 88.9s
0
-
Hi Hongyu,
Have you tried the parameters suggested in Solver parameters to manage numerical issues?
e.g. Aggregate = 0 or Presolve = 0.
Also, as mentioned the article linked, you could try changing the solution method, unless you specifically need barrier. If you do need barrier, as indicated at the bottom of the log, try BarHomogeneous = 1.
Cheers,
David0 -
Hi David,
Thanks for your answers. The problem attached is a smaller example, but the real problem I am going to solve is a scale-up version of this problem, so I do need to use barrier to yield better performance.
I indeed tried with presolve off but it didn't help, and i didn't try aggregate. BarHomogeneous didn't help as well. But mysteriously, setting crossover to 1 solve all the problems. I tried to understand why crossover can help numerical issues. Could you help me understand why?
Kind regards,
Hongyu.
0
Please sign in to leave a comment.
Comments
2 comments