Skip to main content

Providing integer start solution drastically increases root relaxation computation time

Answered
Hendrik Weber
  • Edited
Gurobi-versary
First Question
Conversationalist

Hello Gurobi-Team,

I am encountering an issues that I am currently further investigating:

We are attempting to solve a MIP, however the convergence behaviour was unsatisfactory (with the given time limit) so we also developed a heuristic that provides an integer-feasible start solution via the start-attribute. The solver accepts the provided solution as feasible with the corresponding correct objective function value.

The issue that we are encountering: If we do not provide a start solution, the root relaxation is solved very quickly. Then however, the branch-and-bound takes too long, as it does not find good incumbents.

Now when instead we provide an incumbent, the computation of the root relaxation takes much longer than initially. Is there any logical explanation for that? Shouldn't the provided incumbent not play a role until the actual branch-and-bound procedure is started?

Note that we have also set the parameter to use the barrier method, if that is relevant.

________________________________

Without providing incumbent:

Barrier solved model in 22 iterations and 37.44 seconds
Optimal objective 6.23613589e-13
Root crossover log...
75 DPushes remaining with DInf 0.0000000e+00 38s
75110 PPushes remaining with PInf 0.0000000e+00 38s
7222 PPushes remaining with PInf 0.0000000e+00 40s
1959 PPushes remaining with PInf 0.0000000e+00 45s
320 PPushes remaining with PInf 0.0000000e+00 50s
0 PPushes remaining with PInf 0.0000000e+00 52s
Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 52s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
75113 0.0000000e+00 0.000000e+00 0.000000e+00 53s
75113 0.0000000e+00 0.000000e+00 0.000000e+00 53s
Root relaxation: objective 0.000000e+00, 75113 iterations, 20.24 seconds
Total elapsed time = 64.18s

________________________________

With providing incumbent:

Barrier solved model in 20 iterations and 10.23 seconds
Optimal objective 8.69320488e-16
Root crossover log...
75 DPushes remaining with DInf 0.0000000e+00 10s
75110 PPushes remaining with PInf 0.0000000e+00 10s
5718 PPushes remaining with PInf 0.0000000e+00 15s
2432 PPushes remaining with PInf 0.0000000e+00 20s
802 PPushes remaining with PInf 1.3248888e+02 25s
2 PPushes remaining with PInf 2.7289853e+01 31s
0 PPushes remaining with PInf 2.1877709e+01 31s
Push phase complete: Pinf 2.1877709e+01, Dinf 0.0000000e+00 32s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
75113 0.0000000e+00 2.187771e+01 0.000000e+00 32s
75383 0.0000000e+00 2.268482e+03 0.000000e+00 37s
75713 1.7773616e-07 1.582627e+04 0.000000e+00 41s
76053 8.8055841e-07 8.535057e+04 0.000000e+00 47s
76413 4.1986646e-06 1.987258e+05 0.000000e+00 52s
76613 9.4751026e-06 1.117603e+06 0.000000e+00 56s
77003 2.9816953e-05 6.212086e+05 0.000000e+00 62s
77213 4.6991339e-05 7.615967e+05 0.000000e+00 65s
77622 9.3145536e-05 9.484325e+05 0.000000e+00 72s
77841 1.2497819e-04 1.426962e+06 0.000000e+00 75s
78279 2.1663765e-04 1.162364e+06 0.000000e+00 83s
78498 2.7291879e-04 9.291057e+05 0.000000e+00 87s
78717 3.3956905e-04 6.738083e+05 0.000000e+00 91s
79155 4.6745168e-04 7.772895e+05 0.000000e+00 98s
79374 5.3814510e-04 1.122482e+06 0.000000e+00 101s
79812 7.0802702e-04 2.409616e+06 0.000000e+00 109s
80031 7.9078930e-04 8.392169e+05 0.000000e+00 112s
80250 8.8985900e-04 1.176055e+06 0.000000e+00 116s
80679 1.1040427e-03 1.264657e+06 0.000000e+00 123s
80898 1.2151742e-03 1.040515e+06 0.000000e+00 126s
81308 1.4537611e-03 4.563288e+06 0.000000e+00 132s
81518 1.5761547e-03 1.255407e+06 0.000000e+00 135s
81956 1.8259749e-03 9.656827e+05 0.000000e+00 142s
82365 2.0848581e-03 8.892622e+05 0.000000e+00 148s
82565 2.1946377e-03 7.368350e+05 0.000000e+00 151s
82985 2.4594206e-03 1.926721e+06 0.000000e+00 157s
83385 2.7300466e-03 8.689842e+05 0.000000e+00 163s
83575 2.8628532e-03 2.960726e+06 0.000000e+00 165s
83955 3.0901565e-03 7.576858e+05 0.000000e+00 171s
84305 3.2594131e-03 5.764987e+05 0.000000e+00 175s
84865 3.5096237e-03 4.898612e+05 0.000000e+00 182s
85225 3.7846562e-03 2.599513e+06 0.000000e+00 187s
85555 4.0439159e-03 2.860439e+06 0.000000e+00 191s
85865 4.2511366e-03 1.255789e+06 0.000000e+00 195s
86285 4.4997720e-03 2.214924e+06 0.000000e+00 201s
86755 4.8519249e-03 2.978952e+06 0.000000e+00 206s
87205 5.1303774e-03 1.544982e+07 0.000000e+00 211s
87715 6.1675366e-03 4.420002e+06 0.000000e+00 216s
88195 6.9477224e-03 1.492055e+06 0.000000e+00 221s
88685 7.5027661e-03 1.143825e+06 0.000000e+00 226s
89015 7.8745247e-03 3.174308e+06 0.000000e+00 230s
89505 8.3696968e-03 1.531250e+06 0.000000e+00 236s
90005 8.8875439e-03 4.962835e+06 0.000000e+00 241s
90495 9.3479645e-03 2.914145e+06 0.000000e+00 246s
90995 9.8125323e-03 6.023590e+06 0.000000e+00 251s
91475 1.0299732e-02 3.022038e+06 0.000000e+00 255s
92055 1.0793457e-02 2.955994e+06 0.000000e+00 261s
92535 1.1244275e-02 2.878024e+06 0.000000e+00 265s
93195 1.1827505e-02 4.901760e+05 0.000000e+00 271s
93675 1.2152004e-02 1.845783e+06 0.000000e+00 276s
94315 1.2655973e-02 2.944137e+06 0.000000e+00 281s
94815 1.3098413e-02 2.144839e+06 0.000000e+00 286s
95255 1.3407785e-02 3.316675e+06 0.000000e+00 291s
95705 1.3755924e-02 9.368407e+05 0.000000e+00 295s
96375 1.4185260e-02 5.677835e+06 0.000000e+00 301s
96865 1.4473241e-02 1.389365e+06 0.000000e+00 306s
97315 1.4760126e-02 3.240897e+06 0.000000e+00 310s
97965 1.5223306e-02 3.011554e+06 0.000000e+00 316s
98415 1.5499093e-02 3.012534e+06 0.000000e+00 320s
99075 1.6010691e-02 5.284984e+06 0.000000e+00 326s
99565 1.6315699e-02 2.074233e+06 0.000000e+00 331s
100215 1.6737825e-02 7.647051e+05 0.000000e+00 336s
100835 1.7040531e-02 3.566281e+06 0.000000e+00 341s
101475 1.7429319e-02 4.272653e+05 0.000000e+00 346s
102085 1.7724990e-02 1.660989e+06 0.000000e+00 351s
102695 1.8187231e-02 1.384330e+06 0.000000e+00 355s
103325 1.8592675e-02 1.337874e+06 0.000000e+00 361s
103795 1.8797198e-02 1.421416e+06 0.000000e+00 365s
104425 1.9247467e-02 8.108699e+05 0.000000e+00 371s
105045 1.9691071e-02 1.588319e+06 0.000000e+00 376s
105535 2.0050749e-02 6.128465e+05 0.000000e+00 380s
106165 2.0455883e-02 5.756155e+05 0.000000e+00 386s
106765 2.0792883e-02 2.411053e+06 0.000000e+00 391s
107195 2.1019244e-02 1.753930e+06 0.000000e+00 395s
107815 2.1294190e-02 7.245360e+05 0.000000e+00 401s
108255 2.1509933e-02 8.527715e+05 0.000000e+00 405s
108845 2.1780693e-02 1.765112e+06 0.000000e+00 411s
109455 2.2064391e-02 1.093629e+06 0.000000e+00 416s
109965 2.2482588e-02 2.759090e+06 0.000000e+00 420s
110555 2.2830153e-02 7.652667e+05 0.000000e+00 426s
111145 2.3095236e-02 6.771148e+05 0.000000e+00 431s
111755 2.3355948e-02 2.609664e+06 0.000000e+00 436s
112225 2.3567186e-02 2.224608e+06 0.000000e+00 440s
112845 2.3828745e-02 1.509097e+06 0.000000e+00 446s
113505 2.4221472e-02 8.084519e+05 0.000000e+00 451s
114005 2.4448086e-02 3.863949e+05 0.000000e+00 455s
114605 2.4668163e-02 4.059940e+05 0.000000e+00 461s
115225 2.4913933e-02 6.907094e+05 0.000000e+00 466s
115685 2.5075037e-02 3.319737e+06 0.000000e+00 470s
116305 2.5387785e-02 4.248196e+05 0.000000e+00 476s
116915 2.5608198e-02 1.260327e+06 0.000000e+00 481s
117375 2.5799064e-02 6.795269e+05 0.000000e+00 485s
117955 2.5983482e-02 4.579014e+05 0.000000e+00 490s
118575 2.6212136e-02 5.813166e+05 0.000000e+00 495s
119335 2.6478690e-02 3.907984e+05 0.000000e+00 501s
119965 2.6747398e-02 7.352585e+05 0.000000e+00 506s
120575 2.6936138e-02 8.688761e+05 0.000000e+00 510s
121435 2.7320546e-02 1.835787e+06 0.000000e+00 516s
122115 2.7641537e-02 7.105334e+05 0.000000e+00 520s
122865 2.7903933e-02 6.710435e+05 0.000000e+00 526s
123475 2.8095885e-02 5.432877e+05 0.000000e+00 530s
124105 2.8275217e-02 7.011400e+05 0.000000e+00 535s
124735 2.8482843e-02 5.068814e+05 0.000000e+00 541s
125345 2.8655994e-02 6.075061e+05 0.000000e+00 546s
125955 2.8868189e-02 2.951229e+05 0.000000e+00 550s
126715 2.9096417e-02 1.586469e+06 0.000000e+00 556s
127375 2.9271602e-02 4.413419e+05 0.000000e+00 561s
128015 2.9427465e-02 3.340806e+05 0.000000e+00 566s
128675 2.9618576e-02 1.283627e+06 0.000000e+00 571s
129315 2.9759323e-02 1.036588e+06 0.000000e+00 575s
130095 2.9948670e-02 1.144352e+06 0.000000e+00 581s
130745 3.0096322e-02 1.835500e+05 0.000000e+00 586s
131395 3.0234820e-02 1.713414e+05 0.000000e+00 591s
132025 3.0364274e-02 5.101469e+05 0.000000e+00 596s
132715 3.0542801e-02 9.524303e+05 0.000000e+00 600s
133495 3.0679281e-02 6.605404e+05 0.000000e+00 606s
134145 3.0788991e-02 1.818532e+06 0.000000e+00 611s
134975 3.0932114e-02 9.411169e+05 0.000000e+00 616s
135635 3.1031396e-02 1.580203e+05 0.000000e+00 620s
136485 3.1198730e-02 1.838497e+06 0.000000e+00 626s
137095 3.1310177e-02 8.974867e+05 0.000000e+00 630s
137875 3.1416258e-02 1.958810e+05 0.000000e+00 635s
138685 3.1540033e-02 1.538489e+05 0.000000e+00 641s
139325 3.1629358e-02 2.008536e+06 0.000000e+00 645s
140115 3.1741703e-02 1.205182e+05 0.000000e+00 650s
140895 3.1835403e-02 3.556651e+05 0.000000e+00 656s
141555 3.1923838e-02 7.137554e+04 0.000000e+00 661s
142215 3.2014085e-02 8.478800e+04 0.000000e+00 666s
142855 3.2095692e-02 1.544999e+05 0.000000e+00 670s
143715 3.2214662e-02 5.010671e+04 0.000000e+00 676s
144395 3.2284859e-02 7.760531e+04 0.000000e+00 680s
145265 3.2392722e-02 9.777750e+04 0.000000e+00 685s
146065 3.2463439e-02 2.411437e+05 0.000000e+00 691s
146705 3.2524571e-02 1.798480e+05 0.000000e+00 695s
147515 3.2590171e-02 1.911161e+05 0.000000e+00 701s
148135 3.2648178e-02 4.917139e+05 0.000000e+00 705s
148975 3.2741049e-02 6.323263e+04 0.000000e+00 711s
149615 3.2791718e-02 6.523325e+05 0.000000e+00 716s
150225 3.2828254e-02 4.340756e+04 0.000000e+00 720s
150995 3.2879175e-02 1.728845e+05 0.000000e+00 725s
151815 3.2951788e-02 1.261929e+05 0.000000e+00 731s
152635 3.3005808e-02 8.570438e+04 0.000000e+00 736s
153325 3.3050562e-02 3.630320e+04 0.000000e+00 741s
153995 3.3091776e-02 3.108584e+05 0.000000e+00 745s
154795 3.3138436e-02 6.180560e+05 0.000000e+00 751s
155675 3.3224453e-02 7.434721e+04 0.000000e+00 756s
156384 3.3288427e-02 1.958383e+05 0.000000e+00 760s
157244 3.3345667e-02 7.452346e+04 0.000000e+00 766s
157904 3.3402372e-02 6.749045e+05 0.000000e+00 770s
158714 3.3447135e-02 4.077165e+04 0.000000e+00 776s
159374 3.3498038e-02 1.561155e+04 0.000000e+00 780s
160244 3.3583639e-02 5.157605e+04 0.000000e+00 785s
161084 3.3631861e-02 1.685185e+05 0.000000e+00 791s
161794 3.3691128e-02 3.702452e+05 0.000000e+00 796s
162614 3.3729056e-02 1.761387e+04 0.000000e+00 801s
163304 3.3813250e-02 2.404509e+04 0.000000e+00 805s
164204 3.3906299e-02 2.658560e+04 0.000000e+00 811s
164884 3.3955108e-02 2.631955e+04 0.000000e+00 815s
165574 3.4003877e-02 4.771780e+04 0.000000e+00 820s
166314 3.4084645e-02 9.184560e+04 0.000000e+00 825s
166984 3.4115318e-02 3.017303e+04 0.000000e+00 831s
167624 3.4152207e-02 1.231815e+05 0.000000e+00 836s
168284 3.4182078e-02 4.558750e+04 0.000000e+00 840s
169164 3.4248307e-02 2.171041e+04 0.000000e+00 846s
169794 3.4281595e-02 2.638751e+04 0.000000e+00 850s
170634 3.4336604e-02 1.049960e+05 0.000000e+00 856s
171434 3.4373568e-02 9.510000e+04 0.000000e+00 861s
172114 3.4403103e-02 8.586126e+04 0.000000e+00 866s
172844 3.4460067e-02 5.318740e+04 0.000000e+00 870s
173704 3.4511836e-02 1.181678e+05 0.000000e+00 876s
174534 3.4547288e-02 4.776508e+04 0.000000e+00 881s
175194 3.4590901e-02 1.521375e+04 0.000000e+00 885s
175904 3.4641587e-02 8.267206e+04 0.000000e+00 890s
176734 3.4675539e-02 2.414903e+04 0.000000e+00 896s
177444 3.4711709e-02 3.709855e+04 0.000000e+00 900s
178324 3.4754329e-02 3.557938e+04 0.000000e+00 906s
179034 3.4795211e-02 3.820471e+04 0.000000e+00 911s
179714 3.4824122e-02 4.114550e+04 0.000000e+00 915s
180524 3.4846936e-02 1.253612e+04 0.000000e+00 920s
181364 3.4880333e-02 2.363434e+04 0.000000e+00 926s
182234 3.4953755e-02 1.166937e+05 0.000000e+00 931s
182914 3.4982709e-02 2.507036e+05 0.000000e+00 935s
183594 3.5020487e-02 3.193187e+04 0.000000e+00 940s
184464 3.5053638e-02 2.895673e+04 0.000000e+00 946s
185124 3.5070159e-02 5.844722e+03 0.000000e+00 950s
186004 3.5118303e-02 1.294952e+05 0.000000e+00 956s
186654 3.5148012e-02 2.412653e+04 0.000000e+00 960s
187354 3.5169633e-02 2.836832e+04 0.000000e+00 965s
188224 3.5210562e-02 5.497860e+04 0.000000e+00 970s
189094 3.5235665e-02 1.438123e+04 0.000000e+00 976s
189764 3.5258733e-02 3.116570e+04 0.000000e+00 980s
190634 3.5280229e-02 2.597432e+04 0.000000e+00 986s
191334 3.5301554e-02 3.058910e+04 0.000000e+00 990s
192234 3.5343183e-02 2.016999e+04 0.000000e+00 996s
192964 3.5377538e-02 1.409542e+04 0.000000e+00 1000s
193644 3.5397429e-02 1.873849e+04 0.000000e+00 1005s
194494 3.5415022e-02 4.536479e+03 0.000000e+00 1011s
195174 3.5436227e-02 4.430473e+03 0.000000e+00 1016s
195914 3.5460877e-02 2.385412e+03 0.000000e+00 1020s
196624 3.5480886e-02 1.179220e+04 0.000000e+00 1025s
197344 3.5497971e-02 2.043329e+04 0.000000e+00 1031s
198084 3.5513420e-02 1.066661e+03 0.000000e+00 1036s
198644 3.5532047e-02 2.434703e+04 0.000000e+00 1040s
199364 3.5548527e-02 2.794973e+04 0.000000e+00 1046s
200074 3.5564424e-02 4.471315e+04 0.000000e+00 1051s
200774 3.5584974e-02 4.057347e+04 0.000000e+00 1056s
201454 3.5604307e-02 3.092732e+04 0.000000e+00 1061s
202184 3.5628235e-02 1.318176e+04 0.000000e+00 1066s
202924 3.5645488e-02 5.530092e+03 0.000000e+00 1071s
203684 3.5663827e-02 8.749911e+03 0.000000e+00 1075s
204394 3.5677705e-02 5.067653e+03 0.000000e+00 1080s
205304 3.5700505e-02 1.559683e+03 0.000000e+00 1086s
206084 3.5715194e-02 1.117342e+04 0.000000e+00 1091s
206854 3.5729301e-02 5.170937e+03 0.000000e+00 1096s
207584 3.5745133e-02 4.296220e+03 0.000000e+00 1100s
208304 3.5755648e-02 5.212117e+05 0.000000e+00 1105s
209064 3.5763930e-02 1.014432e+03 0.000000e+00 1110s
209824 3.5776795e-02 1.666592e+03 0.000000e+00 1115s
210603 3.5783978e-02 2.042819e+04 0.000000e+00 1120s
211353 3.5792930e-02 1.257023e+03 0.000000e+00 1125s
212143 3.5797416e-02 1.900984e+02 0.000000e+00 1130s
213132 3.5799696e-02 1.271608e+01 0.000000e+00 1136s
213380 0.0000000e+00 0.000000e+00 0.000000e+00 1138s
213380 0.0000000e+00 0.000000e+00 0.000000e+00 1138s
Root relaxation: objective 0.000000e+00, 213380 iterations, 1132.66 seconds
Total elapsed time = 1141.95s

________________________________

 

I can also attach the console output if that is of any help.

Thanks for the support!

Hendrik

1

Comments

8 comments

Date Votes
  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    HI Hendrik,

    Could you also attach the first lines of the LOG file showing the model statistics, i.e., number of rows, columns, nonzeros, and the coefficient ranges?

    It looks like the barrier algorithm converges to a better starting basis for the root simplex without a starting point provided by you. This can be seen by the fact that the primal and dual infeasibility is 0 after crossover.

    In the second optimization run, the simplex algorithm makes only little progress. This is most likely caused by numerical issues. The provided feasible point looks suspicious, because the objective value is in the order of magnitude of 1e-16 which is at the border of numerical precision. You could try setting the NumericFocus parameter to 3 in order to switch to Quad precision.

    Best regards,
    Jaromił

    0
  • Hendrik Weber
    Gurobi-versary
    First Question
    Conversationalist

    Hello Jaromił,

    Thank you for your immediate answer.

    Here are the "first parts" of the output logs. Please excuse the lack of formatting:

    ________________________________

    Without providing incumbent:

    Academic license - for non-commercial use only
    Changed value of parameter Method to 2
    Prev: -1 Min: -1 Max: 5 Default: -1
    Changed value of parameter TimeLimit to 7200.0
    Prev: inf Min: 0.0 Max: inf Default: inf
    Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (win64)
    Optimize a model with 461198 rows, 1025792 columns and 1654390 nonzeros
    Model fingerprint: 0x7bf81dfa
    Variable types: 879120 continuous, 146672 integer (146520 binary)
    Coefficient statistics:
    Matrix range [8e-01, 1e+03]
    Objective range [1e+00, 2e+00]
    Bounds range [1e+00, 1e+00]
    RHS range [8e-01, 2e+03]
    Warning: Completing partial solution with 142112 unfixed non-continuous variables out of 146672
    User MIP start did not produce a new incumbent solution
    Processed MIP start in 29.32 seconds
    Presolve removed 301223 rows and 948223 columns
    Presolve time: 2.32s
    Presolved: 159975 rows, 77569 columns, 400505 nonzeros
    Variable types: 21973 continuous, 55596 integer (55444 binary)
    Root barrier log...
    Ordering time: 1.28s
    Barrier statistics:
    AA' NZ : 9.263e+05
    Factor NZ : 9.350e+06 (roughly 170 MBytes of memory)
    Factor Ops : 1.441e+09 (less than 1 second per iteration)
    Threads : 5
    Objective Residual
    Iter Primal Dual Primal Dual Compl Time
    0 1.19956271e+05 -7.48098707e+06 1.30e+04 4.16e-02 1.01e+03 34s
    1 5.90840962e+04 -7.30871198e+06 6.33e+03 1.54e+00 4.92e+02 34s
    2 8.57411424e+03 -5.75228656e+06 8.34e+02 3.13e-13 7.67e+01 35s
    3 1.95144575e+03 -3.06077864e+06 9.78e+01 2.77e-13 1.57e+01 35s
    4 1.35946248e+03 -1.30934119e+06 2.65e+01 7.82e-14 5.31e+00 35s
    5 1.17767629e+03 -4.17406611e+05 3.13e+00 1.60e-14 1.44e+00 35s
    6 1.11429215e+03 -3.47237146e+04 7.89e-03 7.77e-15 1.18e-01 35s
    7 8.23730095e+02 -7.98982561e+03 1.78e-15 4.86e-15 2.86e-02 35s
    8 7.13524079e+02 -5.75316639e+03 8.88e-16 3.49e-15 2.10e-02 35s
    9 5.70298488e+02 -3.69088225e+03 8.88e-16 3.50e-15 1.38e-02 36s
    10 2.85950835e+02 -2.82962059e+03 1.73e-14 2.82e-15 1.01e-02 36s
    11 2.05472256e+02 -1.82040584e+03 1.47e-14 3.48e-15 6.58e-03 36s
    12 1.16846899e+02 -1.03591392e+03 3.38e-14 3.46e-15 3.74e-03 36s
    13 7.31383741e+01 -7.55502936e+02 3.02e-14 2.46e-15 2.69e-03 36s
    14 7.54585968e+01 -6.98995912e+02 4.00e-14 2.21e-15 2.52e-03 36s
    15 6.55344200e+01 -5.08882670e+02 3.73e-14 3.05e-15 1.87e-03 36s
    16 6.11817809e+01 -2.96540922e+02 4.13e-14 2.15e-15 1.16e-03 37s
    17 3.40979452e+01 -2.58952313e+02 1.54e-13 1.65e-15 9.52e-04 37s
    18 1.23292121e+01 -1.85618205e+02 1.75e-13 1.92e-15 6.43e-04 37s
    19 1.41522634e+00 -7.44283201e+00 4.35e-13 2.52e-15 2.88e-05 37s
    20 6.19825067e-04 -3.41164362e-02 3.35e-13 2.24e-15 1.13e-07 37s
    21 6.23613589e-10 -3.43178975e-08 3.16e-13 2.80e-15 1.13e-13 37s
    22 6.23613589e-13 -3.43179045e-11 5.28e-15 2.69e-15 1.13e-16 37s
    Barrier solved model in 22 iterations and 37.44 seconds

    ________________________________

    With providing incumbent:

    Academic license - for non-commercial use only
    Changed value of parameter Method to 2
    Prev: -1 Min: -1 Max: 5 Default: -1
    Changed value of parameter TimeLimit to 7200.0
    Prev: inf Min: 0.0 Max: inf Default: inf
    Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (win64)
    Optimize a model with 461198 rows, 1025792 columns and 1654390 nonzeros
    Model fingerprint: 0x45c0f276
    Variable types: 879120 continuous, 146672 integer (146520 binary)
    Coefficient statistics:
    Matrix range [8e-01, 1e+03]
    Objective range [1e+00, 2e+00]
    Bounds range [1e+00, 1e+00]
    RHS range [8e-01, 2e+03]
    User MIP start produced solution with objective 177 (1.19s)
    Loaded user MIP start with objective 177
    Processed MIP start in 1.27 seconds
    Presolve removed 301223 rows and 948223 columns
    Presolve time: 3.60s
    Presolved: 159975 rows, 77569 columns, 400505 nonzeros
    Variable types: 21973 continuous, 55596 integer (55444 binary)
    Root barrier log...
    Ordering time: 1.38s
    Barrier statistics:
    AA' NZ : 9.263e+05
    Factor NZ : 9.350e+06 (roughly 170 MBytes of memory)
    Factor Ops : 1.441e+09 (less than 1 second per iteration)
    Threads : 6
    Objective Residual
    Iter Primal Dual Primal Dual Compl Time
    0 1.19956271e+05 -7.48098707e+06 1.30e+04 4.16e-02 1.01e+03 7s
    1 5.90840962e+04 -7.30871198e+06 6.33e+03 1.54e+00 4.92e+02 7s
    2 8.57411424e+03 -5.75228656e+06 8.34e+02 1.42e-13 7.67e+01 7s
    3 1.95144575e+03 -3.06077864e+06 9.78e+01 1.71e-13 1.57e+01 8s
    4 1.35946248e+03 -1.30934119e+06 2.65e+01 1.28e-13 5.31e+00 8s
    5 1.17767629e+03 -4.17406611e+05 3.13e+00 2.84e-14 1.44e+00 8s
    6 1.11429215e+03 -3.47237146e+04 7.89e-03 7.11e-15 1.18e-01 8s
    7 8.23730095e+02 -7.98982561e+03 9.71e-16 4.25e-15 2.86e-02 8s
    8 7.13524079e+02 -5.75316639e+03 1.03e-15 3.86e-15 2.10e-02 8s
    9 5.70298488e+02 -3.69088225e+03 1.33e-15 3.26e-15 1.38e-02 9s
    10 2.85950835e+02 -2.82962059e+03 2.66e-14 2.95e-15 1.01e-02 9s
    11 2.05472256e+02 -1.82040584e+03 2.26e-14 2.99e-15 6.58e-03 9s
    12 1.36040219e+02 -1.31022761e+03 2.40e-14 2.14e-15 4.70e-03 9s
    13 7.52613359e+01 -9.77724825e+02 1.95e-14 3.01e-15 3.42e-03 9s
    14 9.12240663e+01 -5.92703692e+02 4.80e-14 2.52e-15 2.22e-03 9s
    15 7.11321956e+01 -3.88181946e+02 4.53e-14 2.39e-15 1.49e-03 9s
    16 5.37593403e+01 -1.48658910e+02 5.82e-14 3.80e-15 6.57e-04 10s
    17 7.99438021e-01 -1.81588262e+01 2.70e-13 1.94e-15 6.16e-05 10s
    18 8.60674623e-04 -5.03211627e-02 3.42e-13 3.20e-15 1.66e-07 10s
    19 8.65886527e-10 -5.12831888e-08 3.18e-13 2.44e-15 1.69e-13 10s
    20 8.69320488e-16 -5.14905842e-14 4.68e-15 1.78e-15 1.70e-19 10s
    Barrier solved model in 20 iterations and 10.23 seconds

    _____________________________________________

    We know for a fact that the provided integer solution is not very good, we are still working on improving the heuristic solution. This was simply intended as a proof of concept. 

    I will try to switch to quad precision as you suggested.

    I did not expect the provided start solution to also have an impact on the computation time "before the branching". I thought the provided incumbent would simply be used for pruning during branch-and-bound.

    Is there somehow a way to "ignore" the provided integer solution until we start the actual branching? A workaround that I could think of is using callbacks.

    Thank you so much for your help!

    Hendrik

     

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Hendrik,

    Providing the solution later via a callback would be the way to go in this case. You can achieve this via the cbSetSolution() function in a MIPNODE callback.

    >I did not expect the provided start solution to also have an impact on the computation time "before the branching". I thought the provided incumbent would simply be used for pruning during branch-and-bound.

    This is a rather minor detail which in general should not have much impact except in cases with shaky numerics (as seems to be the case here).

    Best regards,
    Jaromił

    0
  • Hendrik Weber
    Gurobi-versary
    First Question
    Conversationalist

    Hello Jaromił,

    thank you so much for your help.

    Yes, we have encountered cases in the computational study where we were prompted with "Warning: Markowitz tolerance tightened to...".

    The coefficient range of 4 orders of magnitude in the model seems very reasonable. We have not yet been able to identify where the numerical issues are introduced.

    We will look further into it, also considering this here: http://files.gurobi.com/Numerics.pdf 

    In case you have any other hints or directions you can point us to: It is highly appreciated!

    Thanks again for your help and patience!

    Hendrik

     

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Hendrik,

    Please note that the coefficient ranges are only an indicator for numerical issues. The ranges may be very small and the underlying problem could still suffer from numerical issues, e.g., if the coefficient matrix is near to singular, has almost linearly dependent rows or similar.

    You could also try upgrading to our latest version 9.1.

    Best regards,
    Jaromił

    0
  • Mark Stone
    Gurobi-versary
    First Comment

    Jaromił Najman  wrote "You could try setting the NumericFocus parameter to 3 in order to switch to Quad precision."

    Does NumericFocus value of 2 also use Quad precision, and if so, is it used less than for value of 3? What about value of 1?

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Mark,

    The NumericFocus parameter automatically controls the quad precision computation, the Markowitz Tolerance, and a few others. Since NumericFocus automatically decides whether to use quad precision, it is possible that setting the value to 2 or 1 will also enable it, where a higher value favors the enabling more. If you want to explicitly enable Quad Precision, you can set the Quad parameter.

    For more information, please have a look at our Guidelines for Numerical Issues and the Webinar on Avoiding Numerical Issues in Optimization.

    Best regards,
    Jaromił

    0

Post is closed for comments.

Didn't find what you were looking for?

New post