Configuration for binary LP feasibility check
Answered
Hello,
My goal is to verify (in)feasibility of a binary LP model (no objective). I expect the model is rather infeasible, but I am not sure. What is the suggested configuration for such a task? Should I set MIPFocus, InfProofCuts or other parameters in a specific way?
I am guessing the use of computeIIS does not change the actual optimization and impact of parametrization, except that it provides the IIS additionally?
I suppose the model is not very large but hard. I am quoting below the log file if it would be helpful. It is obtained under default parametrization. It was stopped by "out of memory", but the memory was occupied by other tasks, so it is not a problem at the moment.
Thank you,
AndrewB
Gurobi 10.0.2 (win64, Java) logging started Wed Sep 13 12:34:40 2023
Set parameter Username
Academic license - for non-commercial use only - expires 2023-12-23
Set parameter Threads to value 60
Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (win64)
CPU model: AMD EPYC-Rome Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 60 physical cores, 60 logical processors, using up to 60 threads
Optimize a model with 161778 rows, 163878 columns and 559047 nonzeros
Model fingerprint: 0xeb601cd1
Variable types: 0 continuous, 163878 integer (163878 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [0e+00, 0e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+01]
Presolve removed 141303 rows and 142443 columns
Presolve time: 0.46s
Presolved: 20475 rows, 21435 columns, 84975 nonzeros
Variable types: 0 continuous, 21435 integer (21435 binary)
Root relaxation: objective 0.000000e+00, 5682 iterations, 1.38 seconds (1.99 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 627 - 0.00000 - - 3s
0 0 0.00000 0 947 - 0.00000 - - 8s
0 0 0.00000 0 962 - 0.00000 - - 11s
0 0 0.00000 0 704 - 0.00000 - - 34s
0 0 0.00000 0 772 - 0.00000 - - 36s
0 0 0.00000 0 680 - 0.00000 - - 50s
0 0 0.00000 0 854 - 0.00000 - - 58s
0 0 0.00000 0 755 - 0.00000 - - 81s
0 0 0.00000 0 755 - 0.00000 - - 85s
0 2 0.00000 0 565 - 0.00000 - - 96s
3 2 0.00000 2 1015 - 0.00000 - 9306 106s
5 4 0.00000 3 1150 - 0.00000 - 8284 117s
7 8 0.00000 4 1107 - 0.00000 - 8960 127s
11 12 infeasible 5 - 0.00000 - 8214 142s
31 38 0.00000 7 1177 - 0.00000 - 7691 146s
51 68 0.00000 8 1162 - 0.00000 - 5220 157s
89 128 0.00000 9 1074 - 0.00000 - 3548 208s
149 188 0.00000 10 1072 - 0.00000 - 6180 217s
209 248 0.00000 11 1048 - 0.00000 - 4769 222s
269 308 0.00000 12 1046 - 0.00000 - 3791 227s
329 404 0.00000 13 1049 - 0.00000 - 3167 233s
425 702 0.00000 14 1047 - 0.00000 - 2520 249s
723 1356 0.00000 21 991 - 0.00000 - 1634 292s
1377 3391 0.00000 36 963 - 0.00000 - 1119 347s
3414 8797 0.00000 68 804 - 0.00000 - 690 496s
8854 13459 0.00000 120 568 - 0.00000 - 474 644s
13968 15910 infeasible 171 - 0.00000 - 411 757s
17064 18182 0.00000 200 396 - 0.00000 - 423 871s
20029 18183 0.00000 133 755 - 0.00000 - 445 948s
20031 18184 0.00000 36 586 - 0.00000 - 445 965s
20032 18185 0.00000 81 771 - 0.00000 - 445 980s
20033 18186 0.00000 22 1099 - 0.00000 - 445 992s
20034 18186 0.00000 114 984 - 0.00000 - 445 1014s
20035 18187 0.00000 11 1106 - 0.00000 - 445 1026s
20036 18188 0.00000 59 1059 - 0.00000 - 445 1051s
20037 18188 0.00000 22 1190 - 0.00000 - 445 1064s
20038 18189 0.00000 189 888 - 0.00000 - 445 1105s
20039 18190 0.00000 13 1086 - 0.00000 - 445 1116s
20040 18190 0.00000 69 475 - 0.00000 - 445 1149s
20041 18191 0.00000 12 685 - 0.00000 - 445 1157s
20042 18192 0.00000 117 542 - 0.00000 - 445 1185s
20043 18192 0.00000 166 740 - 0.00000 - 445 1193s
20044 18193 0.00000 190 564 - 0.00000 - 445 1226s
20045 18194 0.00000 156 819 - 0.00000 - 445 1234s
20046 18194 0.00000 167 582 - 0.00000 - 445 1265s
20047 18195 0.00000 162 706 - 0.00000 - 445 1271s
20048 18196 0.00000 22 462 - 0.00000 - 445 1308s
20049 18196 0.00000 19 827 - 0.00000 - 445 1315s
20050 18197 0.00000 163 605 - 0.00000 - 445 1353s
20051 18198 0.00000 178 594 - 0.00000 - 445 1358s
20052 18198 0.00000 162 594 - 0.00000 - 445 1360s
20053 18202 0.00000 11 656 - 0.00000 - 26.4 1381s
20055 18205 0.00000 12 758 - 0.00000 - 27.7 1385s
20075 18211 0.00000 15 674 - 0.00000 - 28.8 1393s
20087 18217 0.00000 16 683 - 0.00000 - 29.5 1397s
20107 18228 0.00000 17 617 - 0.00000 - 30.6 1409s
20137 18256 infeasible 18 - 0.00000 - 37.5 1426s
20185 18286 0.00000 19 540 - 0.00000 - 45.0 1446s
20245 18322 0.00000 20 546 - 0.00000 - 49.4 1460s
20305 18360 0.00000 21 540 - 0.00000 - 53.2 1473s
20365 18399 0.00000 22 539 - 0.00000 - 55.9 1486s
20426 18439 0.00000 23 541 - 0.00000 - 58.5 1497s
20486 18479 0.00000 24 537 - 0.00000 - 60.5 1508s
20546 18614 0.00000 25 536 - 0.00000 - 62.5 1533s
20701 18905 0.00000 26 538 - 0.00000 - 68.0 1582s
21044 19926 0.00000 32 533 - 0.00000 - 83.5 1693s
22179 22289 0.00000 47 489 - 0.00000 - 104 1905s
24921 24812 0.00000 70 534 - 0.00000 - 133 2159s
28250 23703 0.00000 76 1054 - 0.00000 - 155 2161s
28621 26069 0.00000 101 979 - 0.00000 - 157 2400s
31960 28237 0.00000 39 808 - 0.00000 - 190 2630s
35610 30227 0.00000 82 1067 - 0.00000 - 214 2889s
39493 32263 0.00000 43 897 - 0.00000 - 233 3170s
43322 34856 0.00000 74 953 - 0.00000 - 248 3487s
47036 33618 0.00000 110 1022 - 0.00000 - 256 3490s
47765 36661 0.00000 117 1047 - 0.00000 - 259 3778s
49904 35948 0.00000 97 1011 - 0.00000 - 264 3780s
51776 40431 0.00000 89 998 - 0.00000 - 268 4166s
57604 43439 0.00000 60 988 - 0.00000 - 276 4552s
63621 45486 0.00000 133 1017 - 0.00000 - 288 4869s
65624 44819 0.00000 109 1018 - 0.00000 - 290 4870s
68081 49033 0.00000 71 915 - 0.00000 - 295 5264s
72935 47415 0.00000 103 1016 - 0.00000 - 301 5267s
74228 52368 infeasible 135 - 0.00000 - 303 5674s
79775 52228 0.00000 98 1037 - 0.00000 - 310 5677s
80369 57060 0.00000 82 942 - 0.00000 - 311 6079s
80921 57060 0.00000 114 548 - 0.00000 - 312 6080s
86095 60840 0.00000 83 683 - 0.00000 - 319 7189s
90400 69022 0.00000 114 977 - 0.00000 - 326 7907s
96694 69022 0.00000 84 1049 - 0.00000 - 332 7912s
100475 69022 0.00000 77 872 - 0.00000 - 336 7917s
100642 73394 0.00000 116 1063 - 0.00000 - 336 8428s
103234 73394 0.00000 100 532 - 0.00000 - 339 8430s
106017 80412 infeasible 164 - 0.00000 - 341 9063s
108167 80412 0.00000 75 905 - 0.00000 - 342 9065s
114258 86893 0.00000 90 1004 - 0.00000 - 346 9657s
121917 93247 0.00000 88 453 - 0.00000 - 351 10245s
129348 98454 0.00000 87 821 - 0.00000 - 357 10888s
131768 98454 0.00000 103 927 - 0.00000 - 359 10890s
135517 107669 0.00000 147 1046 - 0.00000 - 361 11838s
146202 107669 0.00000 103 1018 - 0.00000 - 367 11850s
146569 114192 0.00000 149 958 - 0.00000 - 367 12651s
154512 121603 infeasible 139 - 0.00000 - 375 13563s
159506 121603 0.00000 142 1098 - 0.00000 - 378 13568s
163588 128793 0.00000 160 920 - 0.00000 - 381 14446s
172583 134808 0.00000 140 1092 - 0.00000 - 388 15327s
179958 144828 0.00000 112 440 - 0.00000 - 392 16563s
185184 144828 infeasible 157 - 0.00000 - 396 16568s
187550 144828 0.00000 124 877 - 0.00000 - 397 16572s
190673 144828 0.00000 147 1097 - 0.00000 - 398 16578s
192627 152798 0.00000 81 358 - 0.00000 - 399 17673s
197408 152798 0.00000 127 836 - 0.00000 - 402 17679s
202646 159304 0.00000 88 720 - 0.00000 - 404 18766s
209439 159304 infeasible 148 - 0.00000 - 409 18776s
211968 165966 0.00000 149 1053 - 0.00000 - 410 19786s
217962 165966 infeasible 164 - 0.00000 - 415 19794s
220333 171545 0.00000 86 386 - 0.00000 - 418 20849s
223168 171545 0.00000 151 740 - 0.00000 - 419 20852s
226080 171545 0.00000 105 1038 - 0.00000 - 421 20857s
227239 181938 0.00000 124 566 - 0.00000 - 422 22439s
229818 181938 0.00000 149 1048 - 0.00000 - 424 22442s
233169 181938 0.00000 131 1048 - 0.00000 - 425 22447s
237896 181938 0.00000 138 1137 - 0.00000 - 428 22456s
240235 189468 0.00000 103 1037 - 0.00000 - 429 23734s
241428 189468 infeasible 166 - 0.00000 - 430 23735s
249544 197281 0.00000 128 948 - 0.00000 - 435 25084s
251340 197281 infeasible 139 - 0.00000 - 436 25086s
253735 197281 0.00000 120 418 - 0.00000 - 438 25090s
256399 197281 0.00000 123 433 - 0.00000 - 439 25095s
259306 203231 0.00000 101 399 - 0.00000 - 441 26331s
263537 203231 0.00000 123 449 - 0.00000 - 442 26337s
266686 210730 0.00000 126 456 - 0.00000 - 443 27795s
276369 217455 0.00000 143 461 - 0.00000 - 448 29213s
284949 224135 0.00000 124 356 - 0.00000 - 454 30681s
293668 229953 0.00000 158 606 - 0.00000 - 461 32102s
301469 235835 infeasible 179 - 0.00000 - 469 33673s
302560 235835 0.00000 173 787 - 0.00000 - 469 33675s
309162 242762 0.00000 158 500 - 0.00000 - 473 35389s
310007 242762 0.00000 170 920 - 0.00000 - 474 35390s
318240 248414 0.00000 159 728 - 0.00000 - 479 36907s
323457 248414 0.00000 129 456 - 0.00000 - 485 36918s
325732 255969 infeasible 167 - 0.00000 - 487 38919s
326181 255969 infeasible 173 - 0.00000 - 487 38920s
335629 262348 0.00000 135 629 - 0.00000 - 493 40714s
336305 262348 infeasible 171 - 0.00000 - 493 40716s
338730 262348 0.00000 156 509 - 0.00000 - 495 40720s
341449 262348 0.00000 167 651 - 0.00000 - 497 40727s
343345 262348 0.00000 149 515 - 0.00000 - 499 40732s
344247 267903 infeasible 178 - 0.00000 - 500 42517s
351724 274964 infeasible 164 - 0.00000 - 505 44599s
351904 274964 0.00000 143 472 - 0.00000 - 505 44600s
361053 281012 0.00000 141 521 - 0.00000 - 509 46727s
363205 281012 0.00000 175 750 - 0.00000 - 510 46731s
369210 281012 infeasible 174 - 0.00000 - 514 46752s
369313 287586 0.00000 126 519 - 0.00000 - 514 49087s
375672 287586 0.00000 141 403 - 0.00000 - 518 49104s
377954 287586 0.00000 167 599 - 0.00000 - 520 49111s
377991 294180 0.00000 154 958 - 0.00000 - 520 51674s
380977 294180 0.00000 139 845 - 0.00000 - 522 51681s
383454 294180 0.00000 137 395 - 0.00000 - 523 51687s
386801 300572 0.00000 181 710 - 0.00000 - 525 54322s
389269 300572 0.00000 153 502 - 0.00000 - 527 54329s
395468 307332 0.00000 162 568 - 0.00000 - 531 56524s
396421 307332 0.00000 144 458 - 0.00000 - 531 56525s
404163 314294 0.00000 155 1024 - 0.00000 - 535 59072s
413519 321008 0.00000 161 871 - 0.00000 - 540 61799s
415367 321008 0.00000 173 843 - 0.00000 - 540 61811s
418028 321008 0.00000 165 517 - 0.00000 - 542 61820s
422573 327132 0.00000 151 472 - 0.00000 - 543 64817s
423990 327132 infeasible 170 - 0.00000 - 544 64821s
Cutting planes:
Clique: 1
Zero half: 2
RLT: 13
BQP: 210
Explored 430904 nodes (245066211 simplex iterations) in 67961.24 seconds (5913.37 work units)
Thread count was 60 (of 60 available processors)
Solution count 0
Solve interrupted (error code 10001)
Best objective -, best bound 0.000000000000e+00, gap -
0
-
Hi Andrew,
I recommend you experiment with MIPFocus, Heuristics, and NoRelHeurTime. With MIPFocus and Heuristics, you can direct Gurobi to prioritize finding feasible solutions. Although your model does not have an objective function, this can further direct solving behavior in that direction. NoRelHeurTime activates the NoRel heuristic, which searches for feasible solutions before solving the root relaxation. When NoRel finds a solution in your specified time, Gurobi terminates (as you did not specify an objective function); if not, it will start the regular solving procedure after your specified NoRel time has passed. This would require some experimentation to figure out a reasonable time to spend on NoRel.
If that does not help, you can also consider ZeroObjNodes, MinRelNodes, and PumpPasses; these are quite expensive heuristics that might be worth trying if experiments with the first set of parameters did not help.
I hope this helps. Let me know if you have any interesting findings.
Best regards,
Lennart0 -
Hi Lennart,
Thank you very much for the suggestions. I understand the use of these parameters may help me to find of a feasible solution faster. What if I rather expect infeasibility and like to finish the search with INFEASIBLE status possibly quickly? Should I experiment with the same parameters?
Best regards,
AndrewB0 -
I suggest, yes. You could also try more aggressive Cuts settings, which might help to come to a conclusion more quickly.
0
Please sign in to leave a comment.
Comments
3 comments