GAP falls slowly
Answered
Hello, in the following log file I explain the MILP problem that I am trying to solve, unfortunately when reaching the last process, the algorithm slowly decreases its GAP. In addition to this, I have implemented the PerturbValue and DegenMoves parameters without success, since the suspicion is that the degenerancy is the problem. The idea of this problem is to tune the parameters as little as possible, any other recommendations?
Gurobi 10.0.2 (linux64) logging started Thu Nov 9 17:23:14 2023
Set parameter LogFile to value "/home/pc2/Desktop/Enrique Osorio/CCG/OUtput/IEEE118/IEEE118_iteracion_2.log"
Set parameter NumericFocus to value 1
Set parameter PerturbValue to value 1000
Set parameter DegenMoves to value 0
Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (linux64)
CPU model: Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 16 physical cores, 32 logical processors, using up to 32 threads
Optimize a model with 713668 rows, 522512 columns and 2073033 nonzeros
Model fingerprint: 0xc536462c
Variable types: 522481 continuous, 31 integer (31 binary)
Coefficient statistics:
Matrix range [2e-06, 2e+08]
Objective range [1e-01, 4e+04]
Bounds range [1e+00, 1e+06]
RHS range [1e-02, 2e+08]
Warning: Model contains large matrix coefficient range
Presolve removed 364143 rows and 85905 columns (presolve time = 5s) ...
Presolve removed 364815 rows and 86577 columns
Presolve time: 9.72s
Presolved: 348853 rows, 435935 columns, 1556604 nonzeros
Variable types: 435904 continuous, 31 integer (31 binary)
Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Root barrier log...
Ordering time: 2.27s
Barrier statistics:
Dense cols : 31
AA' NZ : 2.017e+06
Factor NZ : 1.802e+07 (roughly 500 MB of memory)
Factor Ops : 3.496e+09 (less than 1 second per iteration)
Threads : 13
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 2.03518536e+13 -9.03984867e+15 1.04e+06 4.55e+03 9.40e+10 16s
1 1.97448486e+13 -1.67199044e+15 7.17e+05 5.02e+04 5.31e+10 16s
2 1.89329518e+13 -3.32269053e+14 3.80e+05 8.31e+03 2.74e+10 17s
3 1.57717249e+13 -1.17017932e+13 1.64e+04 4.41e+01 1.19e+09 17s
4 1.03982344e+12 -5.66654746e+12 1.66e+01 1.82e+00 9.21e+06 17s
5 1.84469714e+11 -1.12796255e+12 2.25e+00 1.01e-01 1.61e+06 18s
6 2.31971654e+10 -1.35322355e+11 1.38e-01 4.70e-07 1.83e+05 18s
7 4.28968979e+09 -1.51757621e+10 8.90e-03 5.41e-08 2.15e+04 18s
8 2.38895102e+07 -6.13724604e+07 8.72e-11 9.61e-08 9.32e+01 18s
9 8.65371705e+05 -6.58792472e+06 2.10e-12 6.66e-11 8.15e+00 19s
10 4.07392254e+05 -9.16394502e+05 8.81e-13 8.19e-12 1.45e+00 19s
11 1.87185648e+05 -3.48466028e+05 5.12e-13 7.28e-12 5.85e-01 19s
12 9.73012336e+04 -1.10125758e+05 8.95e-13 7.28e-12 2.27e-01 20s
13 5.07670577e+04 -2.85451620e+04 3.87e-13 7.28e-12 8.67e-02 20s
14 3.21569635e+04 -8.27118915e+03 1.99e-13 3.64e-12 4.42e-02 20s
15 2.80849450e+04 -1.09411680e+02 1.42e-13 3.64e-12 3.08e-02 21s
16 2.34102292e+04 3.52127838e+03 1.07e-13 3.64e-12 2.17e-02 21s
17 2.05325227e+04 6.75171015e+03 1.14e-13 3.64e-12 1.51e-02 22s
18 1.86472994e+04 8.56769712e+03 5.68e-14 3.64e-12 1.10e-02 22s
19 1.77160458e+04 1.11017756e+04 8.53e-14 7.28e-12 7.23e-03 23s
20 1.68629506e+04 1.27704389e+04 8.53e-14 3.64e-12 4.47e-03 23s
21 1.63110866e+04 1.36397065e+04 8.53e-14 3.64e-12 2.92e-03 24s
22 1.62550011e+04 1.35571113e+04 8.53e-14 3.64e-12 2.95e-03 25s
23 1.60277446e+04 1.40842489e+04 8.53e-14 3.64e-12 2.12e-03 25s
24 1.58102557e+04 1.44899840e+04 8.53e-14 3.64e-12 1.44e-03 26s
25 1.56019831e+04 1.48559664e+04 8.53e-14 7.28e-12 8.15e-04 26s
26 1.55332440e+04 1.50751711e+04 8.53e-14 7.28e-12 5.01e-04 27s
27 1.54728883e+04 1.51039705e+04 7.11e-14 7.28e-12 4.03e-04 27s
28 1.54499203e+04 1.51677172e+04 8.53e-14 7.28e-12 3.08e-04 28s
29 1.54284160e+04 1.51948320e+04 7.11e-14 7.28e-12 2.55e-04 28s
30 1.54010260e+04 1.52548263e+04 7.11e-14 7.28e-12 1.60e-04 29s
31 1.53799881e+04 1.52709007e+04 8.53e-14 7.28e-12 1.19e-04 29s
32 1.53624904e+04 1.52922827e+04 8.53e-14 3.64e-12 7.67e-05 30s
33 1.53578419e+04 1.53062730e+04 8.53e-14 3.64e-12 5.64e-05 30s
34 1.53562122e+04 1.53096198e+04 8.53e-14 7.28e-12 5.09e-05 31s
35 1.53502154e+04 1.53171689e+04 8.53e-14 5.82e-11 3.61e-05 31s
36 1.53459176e+04 1.53231489e+04 7.11e-14 3.64e-12 2.49e-05 32s
37 1.53445857e+04 1.53262917e+04 8.53e-14 7.28e-12 2.00e-05 33s
38 1.53420684e+04 1.53328644e+04 6.10e-10 3.64e-12 1.01e-05 33s
39 1.53405415e+04 1.53336454e+04 3.93e-10 7.28e-12 7.54e-06 34s
40 1.53397278e+04 1.53359807e+04 2.63e-10 3.64e-12 4.10e-06 34s
41 1.53395032e+04 1.53363750e+04 2.28e-10 7.28e-12 3.42e-06 35s
42 1.53389530e+04 1.53372579e+04 1.44e-10 3.64e-12 1.85e-06 35s
43 1.53386238e+04 1.53375245e+04 9.26e-11 3.64e-12 1.20e-06 35s
44 1.53383794e+04 1.53377860e+04 5.65e-11 7.28e-12 6.49e-07 36s
45 1.53382859e+04 1.53378917e+04 4.24e-11 5.82e-11 4.31e-07 36s
46 1.53382655e+04 1.53378973e+04 1.69e-10 7.28e-12 4.02e-07 37s
47 1.53381710e+04 1.53379427e+04 1.00e-10 3.64e-12 2.50e-07 37s
48 1.53380758e+04 1.53379767e+04 1.82e-10 5.82e-11 1.08e-07 37s
49 1.53380665e+04 1.53379813e+04 3.80e-08 5.82e-11 9.31e-08 38s
50 1.53380292e+04 1.53379957e+04 7.78e-08 5.82e-11 3.67e-08 38s
51 1.53380250e+04 1.53379970e+04 6.65e-07 3.64e-12 3.08e-08 39s
52 1.53380200e+04 1.53379991e+04 5.03e-07 3.64e-12 2.30e-08 39s
53 1.53380137e+04 1.53380019e+04 1.07e-06 7.28e-12 1.30e-08 39s
54 1.53380128e+04 1.53380031e+04 4.49e-06 7.28e-12 9.35e-09 40s
55 1.53380132e+04 1.53380031e+04 9.22e-06 7.28e-12 8.37e-09 40s
56 1.53380132e+04 1.53380031e+04 9.22e-06 7.28e-12 8.37e-09 41s
57 1.53380130e+04 1.53380032e+04 9.89e-06 1.46e-11 8.11e-09 41s
58 1.53380125e+04 1.53380032e+04 1.08e-05 1.46e-11 7.68e-09 41s
59 1.53380119e+04 1.53380035e+04 1.34e-05 7.28e-12 6.33e-09 42s
60 1.53379992e+04 1.53380041e+04 1.47e-05 3.64e-12 4.18e-09 42s
61 1.53379992e+04 1.53380041e+04 1.47e-05 5.82e-11 4.17e-09 43s
62 1.53379992e+04 1.53380041e+04 1.47e-05 5.82e-11 4.17e-09 43s
63 1.53379992e+04 1.53380041e+04 1.47e-05 7.28e-12 4.16e-09 44s
64 1.53379990e+04 1.53380041e+04 1.50e-05 7.28e-12 4.03e-09 44s
65 1.53380023e+04 1.53380042e+04 1.96e-05 5.82e-11 3.75e-09 45s
66 1.53380046e+04 1.53380043e+04 2.22e-05 7.28e-12 3.42e-09 45s
Barrier solved model in 66 iterations and 45.41 seconds (30.28 work units)
Optimal objective 1.53380046e+04
Root crossover log...
Restart crossover...
67894 DPushes remaining with DInf 0.0000000e+00 47s
25681 DPushes remaining with DInf 0.0000000e+00 53s
14472 DPushes remaining with DInf 0.0000000e+00 66s
8993 DPushes remaining with DInf 0.0000000e+00 70s
2609 DPushes remaining with DInf 0.0000000e+00 77s
912 DPushes remaining with DInf 0.0000000e+00 80s
0 DPushes remaining with DInf 0.0000000e+00 82s
149619 PPushes remaining with PInf 6.6787723e-02 82s
130644 PPushes remaining with PInf 6.7378337e-01 90s
111974 PPushes remaining with PInf 4.5865682e-02 95s
102334 PPushes remaining with PInf 4.5865682e-02 100s
96356 PPushes remaining with PInf 4.5862844e-02 105s
59242 PPushes remaining with PInf 1.7123025e-01 114s
56573 PPushes remaining with PInf 1.3763808e-01 115s
48645 PPushes remaining with PInf 1.3763808e-01 120s
34874 PPushes remaining with PInf 1.3763681e-01 125s
31359 PPushes remaining with PInf 1.3754719e-01 130s
28219 PPushes remaining with PInf 1.3754719e-01 135s
25360 PPushes remaining with PInf 1.3746010e-01 141s
22837 PPushes remaining with PInf 1.1273575e-01 145s
20527 PPushes remaining with PInf 1.1273575e-01 151s
18597 PPushes remaining with PInf 1.1273573e-01 155s
16634 PPushes remaining with PInf 1.1273572e-01 160s
14753 PPushes remaining with PInf 1.1273572e-01 165s
12871 PPushes remaining with PInf 1.1273572e-01 170s
10981 PPushes remaining with PInf 1.1265947e-01 175s
8783 PPushes remaining with PInf 1.1265947e-01 180s
6900 PPushes remaining with PInf 1.1265947e-01 185s
4077 PPushes remaining with PInf 1.4610478e-01 191s
2474 PPushes remaining with PInf 1.4610477e-01 195s
1185 PPushes remaining with PInf 1.3567462e-01 200s
0 PPushes remaining with PInf 1.3537821e-01 204s
Push phase complete: Pinf 1.3537821e-01, Dinf 1.7513088e+00 204s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
194479 1.5338114e+04 0.000000e+00 1.751309e+00 205s
194957 1.5338005e+04 0.000000e+00 0.000000e+00 210s
Waiting for other threads to finish... 274s
Concurrent spin time: 90.73s (can be avoided by choosing Method=3)
Solved with barrier
194957 1.5338005e+04 0.000000e+00 0.000000e+00 301s
Root relaxation: objective 1.533800e+04, 194957 iterations, 290.75 seconds (208.65 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 15338.0048 0 15 - 15338.0048 - - 301s
0 0 15381.0068 0 13 - 15381.0068 - - 2255s
0 0 15381.1070 0 13 - 15381.1070 - - 2499s
0 0 15381.1107 0 13 - 15381.1107 - - 2502s
0 0 15385.9929 0 14 - 15385.9929 - - 2721s
0 0 15386.1002 0 14 - 15386.1002 - - 3189s
0 0 15386.1223 0 14 - 15386.1223 - - 3192s
0 0 15386.1223 0 14 - 15386.1223 - - 3194s
0 0 15413.1696 0 13 - 15413.1696 - - 3450s
0 0 15415.2538 0 14 - 15415.2538 - - 3476s
0 0 15415.7304 0 13 - 15415.7304 - - 3483s
0 0 15415.7422 0 14 - 15415.7422 - - 3487s
0 0 15415.7433 0 14 - 15415.7433 - - 3489s
0 0 15443.9832 0 14 - 15443.9832 - - 3648s
0 0 15444.3833 0 14 - 15444.3833 - - 3670s
0 0 15444.3860 0 14 - 15444.3860 - - 3673s
0 0 15446.9578 0 14 - 15446.9578 - - 3748s
0 0 15447.7512 0 14 - 15447.7512 - - 3789s
0 0 15447.8865 0 14 - 15447.8865 - - 3800s
0 0 15447.9016 0 14 - 15447.9016 - - 3803s
0 0 15447.9045 0 13 - 15447.9045 - - 3805s
0 0 15448.7577 0 13 - 15448.7577 - - 3815s
0 0 15448.7862 0 13 - 15448.7862 - - 3819s
0 0 15448.7862 0 13 - 15448.7862 - - 3822s
0 0 15448.7862 0 13 - 15448.7862 - - 3828s
H 0 0 16682.071217 15448.7862 7.39% - 4036s
H 0 0 16487.775731 15448.7862 6.30% - 4205s
0 2 15448.7862 0 13 16487.7757 15448.7862 6.30% - 4207s
1 4 15884.3541 1 12 16487.7757 15448.9000 6.30% 34262 4850s
3 8 16198.1515 2 12 16487.7757 15465.5405 6.20% 20266 5888s
7 12 cutoff 3 16487.7757 15536.7989 5.77% 32121 7219s
0
-
The idea of this problem is to tune the parameters as little as possible, any other recommendations?
The difference in coefficient range of your matrix is 14 orders of magnitude
Matrix range [2e-06, 2e+08]
I see that you are using the NumericFocus parameter, but it would be a lot better to try to re-scale the model by hand in order to reduce the coefficient range. This should be the best way to improve performance for your model. For more information please refer to our Guidelines for Numerical Issues.
Setting the PerturbValue seems strange to me. Is it really required? I would guess that once you re-scaled your model it should not be needed.
You could set the Method to 2 in order to always use Barrier as it seems to be best here. This should save some time.
It might make sense to experiment with the NoRelHeurTime parameter which activates the No Relaxation heuristics. This particular heuristics searches for a feasible point even before solving the root node relaxation.
Maybe experimenting with the MIPFocus parameter might help as well.
Please refer to our documentation of the Most important parameters for more inspiration.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment