Suboptimal solution using Barrier
AnsweredI see that the barrier method reports suboptimal solutions for some of the linear programming problems I am trying to solve. Following is the log for one of them:
Set parameter Method to value 2
Set parameter Crossover to value 0
Set parameter TimeLimit to value 7200
Set parameter Presolve to value 0
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (linux64)
CPU model: AMD EPYC 7702 64-Core Processor
Thread count: 128 physical cores, 128 logical processors, using up to 32 thread
Optimize a model with 4814 rows, 6955 columns and 94564 nonzeros
Model fingerprint: 0x09391a1b
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [2e+02, 3e+05]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Ordering time: 0.10s
Barrier statistics:
Dense cols : 36
AA' NZ : 1.570e+05
Factor NZ : 1.010e+06 (roughly 13 MB of memory)
Factor Ops : 3.207e+08 (less than 1 second per iteration)
Threads : 32
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -2.02837464e+07 -2.37215176e+06 1.45e+01 2.61e+04 6.74e+04 0s
1 -1.09727354e+07 -3.74652667e+07 7.87e+00 1.43e+04 3.12e+04 0s
2 -1.43370472e+06 -2.86186361e+07 7.17e-01 3.84e-09 4.78e+03 0s
3 -5.43079206e+05 -9.34339169e+06 2.11e-13 6.23e-09 8.81e+02 0s
4 -5.91457639e+05 -3.34908494e+06 4.26e-13 2.34e-09 2.76e+02 0s
5 -6.30881943e+05 -2.45540306e+06 2.24e-13 1.56e-09 1.83e+02 0s
6 -6.73810100e+05 -2.02307346e+06 1.32e-13 1.25e-09 1.35e+02 0s
7 -6.89211298e+05 -1.66461543e+06 1.30e-13 8.29e-10 9.76e+01 0s
8 -7.64467305e+05 -1.37382624e+06 6.69e-14 6.55e-10 6.10e+01 0s
9 -7.69540988e+05 -1.26617145e+06 6.12e-14 4.66e-10 4.97e+01 0s
10 -8.20977843e+05 -1.15143600e+06 1.15e-13 3.20e-10 3.31e+01 0s
11 -8.57204486e+05 -1.09082925e+06 5.64e-14 2.04e-10 2.34e+01 0s
12 -8.76664584e+05 -1.04692757e+06 4.09e-14 1.75e-10 1.70e+01 0s
13 -8.85122764e+05 -1.03285921e+06 4.46e-14 1.75e-10 1.48e+01 0s
14 -9.01569520e+05 -1.01466553e+06 3.88e-14 1.46e-10 1.13e+01 0s
15 -9.14135522e+05 -1.00039654e+06 6.86e-14 1.09e-10 8.63e+00 0s
16 -9.24226804e+05 -9.82410715e+05 5.60e-14 1.46e-10 5.82e+00 0s
17 -9.36502732e+05 -9.72786217e+05 9.97e-14 1.02e-10 3.63e+00 0s
18 -9.43256652e+05 -9.62708981e+05 9.66e-14 1.60e-10 1.95e+00 0s
19 -9.45905408e+05 -9.59717683e+05 5.62e-13 1.46e-10 1.38e+00 0s
20 -9.48453475e+05 -9.57447102e+05 1.54e-12 1.75e-10 9.00e-01 0s
21 -9.50449831e+05 -9.55688605e+05 1.56e-12 4.66e-10 5.24e-01 0s
22 -9.51724835e+05 -9.54621368e+05 1.20e-12 2.04e-10 2.90e-01 0s
23 -9.52320141e+05 -9.53845258e+05 6.18e-13 2.62e-10 1.53e-01 0s
24 -9.52499115e+05 -9.53454014e+05 5.99e-13 1.72e-09 9.56e-02 0s
25 -9.52791296e+05 -9.53171443e+05 1.53e-12 3.16e-09 3.80e-02 0s
26 -9.52824743e+05 -9.53125016e+05 1.21e-12 2.46e-09 3.01e-02 0s
27 -9.52922315e+05 -9.53035876e+05 5.23e-13 1.28e-09 1.14e-02 0s
28 -9.52952810e+05 -9.52977224e+05 5.69e-09 3.49e-10 2.44e-03 1s
29 -9.52957606e+05 -9.52961745e+05 2.67e-08 2.04e-10 4.14e-04 1s
30 -9.52958595e+05 -9.52959239e+05 1.82e-08 1.16e-10 6.44e-05 1s
31 -9.52958791e+05 -9.52958919e+05 5.31e-07 2.91e-10 1.17e-05 1s
32 -9.52958827e+05 -9.52958867e+05 1.14e-06 1.16e-10 3.20e-06 1s
33 -9.52958891e+05 -9.52958865e+05 1.69e-06 1.46e-10 5.06e-07 1s
34 -9.52958906e+05 -9.52958865e+05 1.86e-06 2.04e-10 2.16e-09 1s
35 -9.52958907e+05 -9.52958865e+05 1.63e-06 8.73e-11 3.85e-10 1s
36 -9.52958944e+05 -9.52958865e+05 1.27e-06 2.62e-10 9.05e-11 1s
37 -9.52958881e+05 -9.52958865e+05 1.19e-06 1.16e-10 8.78e-11 1s
38 -9.52958873e+05 -9.52958865e+05 1.16e-06 2.33e-10 8.66e-11 1s
39 -9.52958880e+05 -9.52958865e+05 1.99e-06 1.16e-10 9.22e-11 1s
40 -9.52958821e+05 -9.52958865e+05 3.88e-06 1.75e-10 8.14e-11 1s
41 -9.52958750e+05 -9.52958865e+05 3.80e-06 1.75e-10 9.70e-11 1s
42 -9.52958748e+05 -9.52958865e+05 2.51e-06 1.16e-10 6.41e-11 1s
43 -9.52958797e+05 -9.52958865e+05 4.12e-06 8.00e-11 4.68e-11 1s
44 -9.52958817e+05 -9.52958865e+05 8.51e-06 1.31e-10 3.01e-11 1s
45 -9.52958953e+05 -9.52958865e+05 1.16e-05 1.16e-10 2.45e-11 1s
46 -9.52958848e+05 -9.52958865e+05 2.28e-05 4.07e-10 2.66e-14 1s
47 -9.52958993e+05 -9.52958865e+05 1.23e-05 8.73e-11 1.57e-14 1s
48 -9.52958803e+05 -9.52958865e+05 1.53e-05 1.16e-10 7.27e-17 1s
49 -9.52958780e+05 -9.52958865e+05 1.05e-05 1.75e-10 8.77e-17 1s
50 -9.52958912e+05 -9.52958865e+05 8.24e-06 1.16e-10 1.36e-16 1s
51 -9.52958830e+05 -9.52958865e+05 8.15e-06 4.37e-11 6.13e-15 1s
52 -9.52958830e+05 -9.52958865e+05 8.15e-06 1.16e-10 4.74e-15 1s
Barrier performed 52 iterations in 0.95 seconds (0.78 work units)
Sub-optimal termination - objective -9.52958791e+05
The coefficient stats don't look too bad, so I am guessing the problem doesn't have numerical issues (please correct me if I am wrong here). Also, the primal/dual residuals are close to zero but don't satisfy the BarConvTol default condition of 1e-8; hence (likely) the solution is reported to be suboptimal. So my questions are:
1. Given that the problem's coefficients seem OK, why is the barrier unable to converge?
2. I guess one way to overcome this is to increase BarConvTol given that the objective value is already of the order of 1e+5. Is that right? What else could be done apart from this?
Thank you!
-
You can try setting BarHomogeneous to 1.
Cheers,
David0
Please sign in to leave a comment.
Comments
1 comment