Why doesn't objective value improve? Then it acquires enormous value
Answered
I am solving a MILP with 5788538 rows, 33964001 columns and 20903685 nonzeros. The number of binary variables is 1000.
I use Gurobi version 11.0.0 within the Matlab interface.
In general, I am dealing with a problem with discrete traffic dynamics, and when I set the number of the discrete-time steps equal to K=100, then the optimization works just fine. However, when I increase the number to K=200, I get this message:
Barrier solved model in 53 iterations and 635.43 seconds (176.33 work units)
Optimal objective 1.40111765e+02
However, the root relaxation phase follows and then at some point (at iteration 141691) the objective function value explodes to -1.6845971e+36.
I was wondering whether this is normal, or is it an indicator that I have modelled something incorrectly in terms of the constraints in Gurobi?
Some of the log file is attached:
Set parameter Username
Set parameter TimeLimit to value 36000
Set parameter FeasibilityTol to value 0.001
Set parameter OptimalityTol to value 0.001
Set parameter BarHomogeneous to value 1
Set parameter MIPFocus to value 3
Set parameter Presolve to value 2
Academic license - for non-commercial use only - expires 2025-01-15
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 11+.0 (22631.2))
CPU model: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 5788538 rows, 33964001 columns and 20903685 nonzeros
Model fingerprint: 0x6733ca27
Variable types: 33963001 continuous, 1000 integer (1000 binary)
Coefficient statistics:
Matrix range [4e-03, 7e+01]
Objective range [8e-03, 8e-03]
Bounds range [1e+00, 3e+03]
RHS range [1e-02, 5e+03]
Presolve removed 0 rows and 0 columns (presolve time = 6s) ...
Presolve removed 4 rows and 29260168 columns (presolve time = 11s) ...
Presolve removed 3714615 rows and 31156761 columns (presolve time = 15s) ...
Presolve removed 4360714 rows and 32829245 columns (presolve time = 20s) ...
Presolve removed 4561541 rows and 32857203 columns
Presolve time: 24.37s
Presolved: 1226997 rows, 1106798 columns, 5915728 nonzeros
Variable types: 1105480 continuous, 1318 integer (0 binary)
Root relaxation presolve removed 767 rows and 648 columns
Root relaxation presolved: 270109 rows, 260620 columns, 1210557 nonzeros
Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Root barrier log...
Elapsed ordering time = 5s
Elapsed ordering time = 10s
Elapsed ordering time = 14s
Elapsed ordering time = 15s
Elapsed ordering time = 20s
Ordering time: 20.79s
Barrier statistics:
AA' NZ : 1.893e+06
Factor NZ : 5.792e+07 (roughly 700 MB of memory)
Factor Ops : 9.329e+10 (roughly 5 seconds per iteration)
Threads : 2
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -1.12537180e+06 -1.18513220e+08 1.18e+05 9.04e-03 5.38e+03 263s
1 -6.75631097e+05 -1.14030818e+08 7.01e+04 1.33e+00 3.24e+03 268s
2 -1.93584279e+05 -9.74187455e+07 1.96e+04 3.21e-01 9.70e+02 272s
3 -4.91352168e+04 -4.25843956e+07 4.68e+03 2.22e-14 2.37e+02 276s
4 -1.73523962e+04 -1.15717491e+07 1.81e+03 2.14e-13 5.90e+01 282s
5 -5.07872117e+03 -5.76192313e+06 5.81e+02 1.07e-13 1.91e+01 289s
6 -2.08254293e+03 -2.85699405e+06 3.12e+02 5.40e-14 8.80e+00 295s
7 -3.26953737e+02 -1.01710103e+06 1.56e+02 1.22e-13 3.05e+00 300s
8 8.60271736e+02 -3.67491091e+05 5.04e+01 2.99e-13 8.87e-01 306s
9 1.13193388e+03 -1.80765309e+05 2.31e+01 7.45e-14 4.05e-01 311s
10 1.21772993e+03 -9.01307271e+04 1.00e+01 5.08e-14 1.87e-01 316s
11 1.22852479e+03 -5.27325378e+04 5.53e+00 3.33e-14 1.05e-01 322s
12 1.21400952e+03 -2.68149946e+04 3.33e+00 6.47e-14 5.39e-02 327s
13 1.17531498e+03 -1.54345692e+04 1.53e+00 1.01e-13 2.97e-02 333s
14 1.13201175e+03 -8.81677391e+03 1.01e+00 8.06e-14 1.76e-02 338s
15 9.79950140e+02 -5.06572178e+03 6.60e-01 1.28e-13 1.06e-02 343s
16 7.84564930e+02 -2.58678328e+03 3.50e-01 1.36e-13 5.74e-03 349s
17 6.28333182e+02 -1.75893293e+03 2.29e-01 1.13e-13 3.99e-03 353s
18 5.01627671e+02 -1.22961124e+03 1.56e-01 1.01e-13 2.85e-03 359s
19 4.02345434e+02 -7.23996452e+02 4.46e-01 1.14e-13 1.88e-03 365s
20 3.49885522e+02 -6.21890231e+02 3.32e-01 1.29e-13 1.60e-03 369s
21 3.12589333e+02 -2.80927980e+02 2.58e-01 1.64e-13 9.80e-04 374s
22 2.40194500e+02 -1.19839689e+02 1.25e-01 1.27e-13 5.81e-04 380s
23 1.98347049e+02 4.07199875e+01 7.02e-02 1.82e-13 2.54e-04 386s
24 1.72842318e+02 9.52956426e+01 3.94e-02 3.77e-14 1.24e-04 394s
25 1.60442911e+02 1.21427414e+02 2.54e-02 5.04e-14 6.28e-05 402s
26 1.55374616e+02 1.27274873e+02 1.92e-02 3.09e-14 4.52e-05 409s
27 1.51142993e+02 1.30427278e+02 1.39e-02 2.03e-14 3.32e-05 416s
28 1.49364694e+02 1.33546286e+02 1.17e-02 2.65e-14 2.54e-05 424s
29 1.46162251e+02 1.36129314e+02 7.65e-03 1.27e-14 1.61e-05 430s
30 1.43607060e+02 1.37468173e+02 4.42e-03 5.07e-14 9.81e-06 437s
31 1.42160903e+02 1.38694427e+02 2.59e-03 6.28e-15 5.54e-06 445s
32 1.41686603e+02 1.39034257e+02 1.99e-03 2.51e-14 4.24e-06 451s
33 1.40949627e+02 1.39548399e+02 1.06e-03 9.07e-14 2.24e-06 458s
34 1.40558374e+02 1.39864211e+02 5.62e-04 2.50e-13 1.11e-06 465s
35 1.40378809e+02 1.39989938e+02 3.59e-04 1.65e-13 6.29e-07 472s
36 1.40249706e+02 1.40057748e+02 3.80e-04 2.16e-13 3.16e-07 479s
37 1.40180572e+02 1.40080359e+02 2.98e-04 2.57e-13 1.68e-07 487s
38 1.40150064e+02 1.40093498e+02 1.69e-04 3.10e-13 9.46e-08 495s
39 1.40136459e+02 1.40101008e+02 1.10e-04 8.99e-13 5.95e-08 504s
40 1.40127127e+02 1.40104620e+02 7.00e-05 2.15e-12 3.78e-08 510s
41 1.40122980e+02 1.40106608e+02 5.19e-05 3.76e-12 2.75e-08 518s
42 1.40119402e+02 1.40109246e+02 3.58e-05 1.46e-12 1.72e-08 527s
43 1.40116249e+02 1.40110131e+02 2.14e-05 1.64e-12 1.04e-08 535s
44 1.40114644e+02 1.40110891e+02 1.40e-05 2.74e-12 6.41e-09 543s
45 1.40113286e+02 1.40111296e+02 7.60e-06 5.23e-12 3.41e-09 551s
46 1.40112458e+02 1.40111584e+02 3.64e-06 1.58e-11 1.51e-09 559s
47 1.40112089e+02 1.40111651e+02 1.80e-06 4.87e-11 7.54e-10 569s
48 1.40111925e+02 1.40111714e+02 9.62e-07 2.07e-10 3.70e-10 580s
49 1.40111835e+02 1.40111730e+02 1.33e-06 2.03e-10 1.86e-10 593s
50 1.40111815e+02 1.40111735e+02 1.04e-06 1.46e-10 1.44e-10 606s
51 1.40111783e+02 1.40111741e+02 6.14e-07 7.13e-11 7.83e-11 618s
52 1.40111778e+02 1.40111741e+02 1.77e-06 6.88e-11 6.75e-11 626s
53 1.40111765e+02 1.40111743e+02 1.05e-06 5.67e-11 4.08e-11 635s
Barrier solved model in 53 iterations and 635.43 seconds (176.33 work units)
Optimal objective 1.40111765e+02
Root crossover log...
202962 DPushes remaining with DInf 0.0000000e+00 637s
129616 DPushes remaining with DInf 5.7041549e-01 640s
82360 DPushes remaining with DInf 3.0459036e+00 647s
70650 DPushes remaining with DInf 4.4708217e+00 651s
60031 DPushes remaining with DInf 4.5007283e+00 658s
54804 DPushes remaining with DInf 4.2732220e+00 663s
52485 DPushes remaining with DInf 4.3105445e+00 667s
48032 DPushes remaining with DInf 4.2415495e+00 671s
44397 DPushes remaining with DInf 4.9724206e+00 675s
41268 DPushes remaining with DInf 4.9773139e+00 681s
38436 DPushes remaining with DInf 4.9121133e+00 685s
34261 DPushes remaining with DInf 5.0792117e+00 693s
32869 DPushes remaining with DInf 5.0685559e+00 697s
30418 DPushes remaining with DInf 4.9804230e+00 702s
28574 DPushes remaining with DInf 4.9855182e+00 707s
27724 DPushes remaining with DInf 4.9560963e+00 714s
27634 DPushes remaining with DInf 4.9560963e+00 719s
27544 DPushes remaining with DInf 4.9560963e+00 725s
27454 DPushes remaining with DInf 4.9560963e+00 731s
27354 DPushes remaining with DInf 4.9560963e+00 736s
27254 DPushes remaining with DInf 4.9560963e+00 744s
27144 DPushes remaining with DInf 4.9560963e+00 752s
26994 DPushes remaining with DInf 4.9560963e+00 759s
26864 DPushes remaining with DInf 4.9560963e+00 767s
26754 DPushes remaining with DInf 4.9560963e+00 774s
26652 DPushes remaining with DInf 4.9560963e+00 781s
26406 DPushes remaining with DInf 4.9560963e+00 788s
26051 DPushes remaining with DInf 4.9560963e+00 794s
25695 DPushes remaining with DInf 4.9560963e+00 806s
25382 DPushes remaining with DInf 4.9560963e+00 814s
25033 DPushes remaining with DInf 4.9560963e+00 823s
24673 DPushes remaining with DInf 4.9560963e+00 835s
24366 DPushes remaining with DInf 4.9560963e+00 845s
24018 DPushes remaining with DInf 4.9560963e+00 855s
23648 DPushes remaining with DInf 4.9560963e+00 863s
23307 DPushes remaining with DInf 4.9560963e+00 870s
22956 DPushes remaining with DInf 4.9560963e+00 877s
22633 DPushes remaining with DInf 4.9560963e+00 883s
22320 DPushes remaining with DInf 4.9560963e+00 890s
21911 DPushes remaining with DInf 4.9560963e+00 896s
21573 DPushes remaining with DInf 4.9560963e+00 902s
21122 DPushes remaining with DInf 4.9560963e+00 910s
20647 DPushes remaining with DInf 4.9560963e+00 917s
20175 DPushes remaining with DInf 4.9560963e+00 924s
19751 DPushes remaining with DInf 4.9560963e+00 931s
19255 DPushes remaining with DInf 4.9560963e+00 938s
18751 DPushes remaining with DInf 4.9560963e+00 948s
18243 DPushes remaining with DInf 4.9560963e+00 958s
17724 DPushes remaining with DInf 4.9560963e+00 968s
17234 DPushes remaining with DInf 4.9560963e+00 974s
16729 DPushes remaining with DInf 4.9560963e+00 980s
16350 DPushes remaining with DInf 4.9560963e+00 993s
15899 DPushes remaining with DInf 4.9560963e+00 1000s
15458 DPushes remaining with DInf 4.9560963e+00 1008s
15152 DPushes remaining with DInf 4.9560963e+00 1019s
14846 DPushes remaining with DInf 4.9560963e+00 1031s
14561 DPushes remaining with DInf 4.9560963e+00 1045s
14320 DPushes remaining with DInf 4.9560963e+00 1057s
14098 DPushes remaining with DInf 4.9560963e+00 1069s
13888 DPushes remaining with DInf 4.9560963e+00 1078s
13718 DPushes remaining with DInf 4.9560963e+00 1087s
13536 DPushes remaining with DInf 4.9560963e+00 1096s
13355 DPushes remaining with DInf 4.9560963e+00 1106s
13164 DPushes remaining with DInf 4.9560963e+00 1119s
12961 DPushes remaining with DInf 4.9560963e+00 1129s
12771 DPushes remaining with DInf 4.9560963e+00 1141s
12556 DPushes remaining with DInf 4.9560963e+00 1150s
12353 DPushes remaining with DInf 4.9560963e+00 1160s
12164 DPushes remaining with DInf 4.9560963e+00 1169s
11990 DPushes remaining with DInf 4.9560963e+00 1182s
11919 DPushes remaining with DInf 4.9560963e+00 1187s
11814 DPushes remaining with DInf 4.9560963e+00 1192s
11654 DPushes remaining with DInf 4.9560963e+00 1202s
11502 DPushes remaining with DInf 4.9560963e+00 1210s
11361 DPushes remaining with DInf 4.9560963e+00 1220s
11231 DPushes remaining with DInf 4.9560963e+00 1229s
11090 DPushes remaining with DInf 4.9560963e+00 1237s
10940 DPushes remaining with DInf 4.9560963e+00 1245s
10800 DPushes remaining with DInf 4.9560963e+00 1253s
10650 DPushes remaining with DInf 4.9560963e+00 1264s
10518 DPushes remaining with DInf 4.9560963e+00 1273s
10487 DPushes remaining with DInf 4.9560963e+00 1276s
Restart crossover...
202910 DPushes remaining with DInf 1.4781044e-03 1278s
102221 DPushes remaining with DInf 1.0451655e+00 1282s
75875 DPushes remaining with DInf 2.6035594e+00 1288s
71569 DPushes remaining with DInf 4.5857011e+00 1291s
64988 DPushes remaining with DInf 5.0161882e+00 1298s
62430 DPushes remaining with DInf 4.0024910e+00 1302s
59899 DPushes remaining with DInf 3.4308830e+00 1305s
55821 DPushes remaining with DInf 4.7159900e+00 1313s
53765 DPushes remaining with DInf 4.5727656e+00 1316s
50190 DPushes remaining with DInf 4.6241418e+00 1323s
48628 DPushes remaining with DInf 4.6927943e+00 1327s
45824 DPushes remaining with DInf 4.8210978e+00 1333s
44346 DPushes remaining with DInf 4.7507477e+00 1336s
41457 DPushes remaining with DInf 4.6922208e+00 1341s
38545 DPushes remaining with DInf 4.8041217e+00 1347s
35966 DPushes remaining with DInf 4.8308449e+00 1353s
34919 DPushes remaining with DInf 4.8660024e+00 1357s
33955 DPushes remaining with DInf 5.6927697e+00 1363s
33191 DPushes remaining with DInf 5.7292990e+00 1366s
33092 DPushes remaining with DInf 5.7284701e+00 1372s
33012 DPushes remaining with DInf 5.9530711e+00 1377s
32932 DPushes remaining with DInf 5.9335087e+00 1383s
32832 DPushes remaining with DInf 5.9320450e+00 1387s
32732 DPushes remaining with DInf 5.9314757e+00 1392s
32622 DPushes remaining with DInf 6.1227326e+00 1398s
32502 DPushes remaining with DInf 6.3367651e+00 1404s
32382 DPushes remaining with DInf 1.1007712e+01 1410s
32262 DPushes remaining with DInf 1.1224792e+01 1418s
32142 DPushes remaining with DInf 2.3373732e+01 1425s
31980 DPushes remaining with DInf 2.5963281e+01 1433s
31765 DPushes remaining with DInf 8.4045628e+01 1441s
31527 DPushes remaining with DInf 1.3045084e+02 1450s
31248 DPushes remaining with DInf 1.9058006e+02 1461s
30956 DPushes remaining with DInf 2.3916469e+02 1469s
30653 DPushes remaining with DInf 2.8069889e+02 1478s
30365 DPushes remaining with DInf 3.4462786e+02 1486s
30090 DPushes remaining with DInf 4.8913931e+02 1496s
29802 DPushes remaining with DInf 5.5068478e+02 1504s
29484 DPushes remaining with DInf 6.8571969e+02 1514s
29222 DPushes remaining with DInf 7.5360725e+02 1519s
28914 DPushes remaining with DInf 8.2413487e+02 1527s
28647 DPushes remaining with DInf 8.5002684e+02 1535s
28452 DPushes remaining with DInf 8.5280232e+02 1539s
28271 DPushes remaining with DInf 8.5683902e+02 1542s
28097 DPushes remaining with DInf 8.7629608e+02 1546s
27796 DPushes remaining with DInf 9.0033577e+02 1555s
27645 DPushes remaining with DInf 9.1097902e+02 1558s
27476 DPushes remaining with DInf 9.4229475e+02 1563s
27296 DPushes remaining with DInf 9.4282225e+02 1567s
27108 DPushes remaining with DInf 1.0026147e+03 1572s
26898 DPushes remaining with DInf 1.0602867e+03 1576s
26711 DPushes remaining with DInf 1.0962276e+03 1581s
26502 DPushes remaining with DInf 1.1213272e+03 1585s
26284 DPushes remaining with DInf 1.2118250e+03 1590s
25827 DPushes remaining with DInf 1.2777462e+03 1599s
25596 DPushes remaining with DInf 1.2966044e+03 1604s
25346 DPushes remaining with DInf 1.3109107e+03 1608s
25100 DPushes remaining with DInf 1.3939489e+03 1613s
24841 DPushes remaining with DInf 1.4150147e+03 1617s
24619 DPushes remaining with DInf 1.4765860e+03 1622s
24389 DPushes remaining with DInf 1.5299393e+03 1627s
24149 DPushes remaining with DInf 1.6359609e+03 1632s
23925 DPushes remaining with DInf 1.6804305e+03 1637s
23682 DPushes remaining with DInf 1.7026923e+03 1641s
23197 DPushes remaining with DInf 1.6022189e+03 1650s
22955 DPushes remaining with DInf 1.6316718e+03 1654s
22717 DPushes remaining with DInf 1.1232723e+04 1657s
22483 DPushes remaining with DInf 8.1092894e+03 1661s
22233 DPushes remaining with DInf 7.9932611e+03 1665s
21775 DPushes remaining with DInf 1.9162655e+04 1673s
21593 DPushes remaining with DInf 1.9082579e+04 1676s
21200 DPushes remaining with DInf 1.6964397e+04 1682s
20816 DPushes remaining with DInf 1.6955468e+04 1688s
20655 DPushes remaining with DInf 1.6925246e+04 1691s
20356 DPushes remaining with DInf 1.6845164e+04 1698s
20194 DPushes remaining with DInf 1.6603193e+04 1704s
19972 DPushes remaining with DInf 1.6074089e+04 1707s
19779 DPushes remaining with DInf 4.4633990e+05 1711s
Warning: 1 variables dropped from basis
19620 DPushes remaining with DInf 2.3244814e+04 1715s
19388 DPushes remaining with DInf 2.3267422e+04 1722s
19232 DPushes remaining with DInf 2.3202204e+04 1725s
18985 DPushes remaining with DInf 2.2828689e+04 1731s
18882 DPushes remaining with DInf 2.1794889e+04 1735s
18781 DPushes remaining with DInf 2.1793761e+04 1740s
18583 DPushes remaining with DInf 2.1791389e+04 1749s
18483 DPushes remaining with DInf 2.1788884e+04 1752s
18381 DPushes remaining with DInf 2.1765347e+04 1756s
18184 DPushes remaining with DInf 2.1798140e+04 1763s
18083 DPushes remaining with DInf 2.1780982e+04 1767s
17988 DPushes remaining with DInf 2.1800373e+04 1770s
17795 DPushes remaining with DInf 2.1799240e+04 1778s
17699 DPushes remaining with DInf 2.1799232e+04 1781s
17511 DPushes remaining with DInf 2.1802125e+04 1788s
17417 DPushes remaining with DInf 2.1957050e+04 1792s
17228 DPushes remaining with DInf 2.1910030e+04 1799s
17134 DPushes remaining with DInf 2.1910037e+04 1802s
17040 DPushes remaining with DInf 2.1910031e+04 1806s
16852 DPushes remaining with DInf 2.1910201e+04 1814s
16757 DPushes remaining with DInf 2.1909813e+04 1818s
16663 DPushes remaining with DInf 2.1909862e+04 1822s
16569 DPushes remaining with DInf 2.1909848e+04 1826s
16379 DPushes remaining with DInf 2.1909785e+04 1833s
16285 DPushes remaining with DInf 2.1909796e+04 1836s
16190 DPushes remaining with DInf 2.1910558e+04 1840s
16000 DPushes remaining with DInf 2.1928193e+04 1848s
15906 DPushes remaining with DInf 2.1928206e+04 1851s
15716 DPushes remaining with DInf 2.1924824e+04 1858s
15621 DPushes remaining with DInf 2.1925408e+04 1862s
15525 DPushes remaining with DInf 2.1919510e+04 1866s
15431 DPushes remaining with DInf 2.1919880e+04 1871s
15241 DPushes remaining with DInf 2.1903693e+04 1878s
15145 DPushes remaining with DInf 2.1898552e+04 1882s
15049 DPushes remaining with DInf 2.3211230e+04 1885s
14860 DPushes remaining with DInf 2.3341805e+04 1893s
14765 DPushes remaining with DInf 2.3341061e+04 1896s
14572 DPushes remaining with DInf 2.4029824e+04 1903s
14476 DPushes remaining with DInf 2.4230161e+04 1908s
14380 DPushes remaining with DInf 2.4433563e+04 1912s
14284 DPushes remaining with DInf 2.4841501e+04 1917s
14189 DPushes remaining with DInf 2.4859042e+04 1920s
14001 DPushes remaining with DInf 2.5089724e+04 1929s
13907 DPushes remaining with DInf 2.5095240e+04 1934s
13813 DPushes remaining with DInf 2.5234759e+04 1939s
13718 DPushes remaining with DInf 2.5290111e+04 1943s
13624 DPushes remaining with DInf 2.5321372e+04 1949s
13530 DPushes remaining with DInf 2.5483820e+04 1955s
13436 DPushes remaining with DInf 2.5581816e+04 1960s
13342 DPushes remaining with DInf 2.5598067e+04 1965s
13248 DPushes remaining with DInf 2.5827885e+04 1970s
13153 DPushes remaining with DInf 2.5923874e+04 1975s
13059 DPushes remaining with DInf 2.5975369e+04 1980s
12965 DPushes remaining with DInf 2.6430358e+04 1986s
12871 DPushes remaining with DInf 2.6688524e+04 1991s
12776 DPushes remaining with DInf 2.6892329e+04 1996s
12681 DPushes remaining with DInf 2.7101490e+04 2001s
12587 DPushes remaining with DInf 2.7381159e+04 2007s
12493 DPushes remaining with DInf 2.7625441e+04 2012s
12398 DPushes remaining with DInf 2.7985119e+04 2018s
12303 DPushes remaining with DInf 2.8095400e+04 2024s
12209 DPushes remaining with DInf 2.8636263e+04 2029s
12124 DPushes remaining with DInf 2.9238236e+04 2035s
12040 DPushes remaining with DInf 2.9268274e+04 2041s
11956 DPushes remaining with DInf 2.9496804e+04 2046s
11872 DPushes remaining with DInf 2.9627738e+04 2052s
11788 DPushes remaining with DInf 2.9705551e+04 2057s
11704 DPushes remaining with DInf 2.9757189e+04 2062s
11620 DPushes remaining with DInf 2.9941223e+04 2067s
11535 DPushes remaining with DInf 2.9967700e+04 2072s
11446 DPushes remaining with DInf 3.0016098e+04 2076s
11271 DPushes remaining with DInf 3.0042145e+04 2083s
11185 DPushes remaining with DInf 3.0048436e+04 2087s
11101 DPushes remaining with DInf 3.0049827e+04 2091s
11017 DPushes remaining with DInf 3.0049812e+04 2095s
10849 DPushes remaining with DInf 3.0049861e+04 2103s
10660 DPushes remaining with DInf 3.0179561e+04 2108s
10449 DPushes remaining with DInf 2.9959205e+04 2112s
10223 DPushes remaining with DInf 3.0897334e+04 2116s
9999 DPushes remaining with DInf 3.0991872e+04 2120s
9730 DPushes remaining with DInf 3.1239285e+04 2126s
9471 DPushes remaining with DInf 3.0188288e+04 2131s
9027 DPushes remaining with DInf 3.1137967e+04 2137s
8745 DPushes remaining with DInf 3.1668538e+04 2142s
8456 DPushes remaining with DInf 3.1946467e+04 2146s
8165 DPushes remaining with DInf 3.2332820e+04 2151s
7865 DPushes remaining with DInf 3.2813853e+04 2156s
7627 DPushes remaining with DInf 3.2980827e+04 2160s
7352 DPushes remaining with DInf 3.3058896e+04 2165s
7094 DPushes remaining with DInf 3.3014099e+04 2170s
6681 DPushes remaining with DInf 3.2754591e+04 2177s
6400 DPushes remaining with DInf 3.2691556e+04 2182s
6147 DPushes remaining with DInf 3.2522269e+04 2186s
5860 DPushes remaining with DInf 3.3266076e+04 2190s
5627 DPushes remaining with DInf 3.3170103e+04 2197s
5389 DPushes remaining with DInf 3.3329986e+04 2201s
5119 DPushes remaining with DInf 3.2720714e+04 2206s
4869 DPushes remaining with DInf 3.1353059e+04 2211s
4555 DPushes remaining with DInf 3.1903965e+04 2215s
4290 DPushes remaining with DInf 3.1784478e+04 2220s
3864 DPushes remaining with DInf 3.2217787e+04 2226s
3628 DPushes remaining with DInf 3.2197681e+04 2232s
3355 DPushes remaining with DInf 3.1951854e+04 2237s
3222 DPushes remaining with DInf 3.1680024e+04 2240s
2878 DPushes remaining with DInf 3.2167754e+04 2246s
2686 DPushes remaining with DInf 3.2156772e+04 2252s
2501 DPushes remaining with DInf 3.2159607e+04 2256s
2330 DPushes remaining with DInf 3.2222933e+04 2263s
2245 DPushes remaining with DInf 3.2227882e+04 2267s
2161 DPushes remaining with DInf 3.2232687e+04 2272s
2076 DPushes remaining with DInf 3.2232505e+04 2276s
1992 DPushes remaining with DInf 3.2261828e+04 2280s
1821 DPushes remaining with DInf 3.2613900e+04 2290s
1652 DPushes remaining with DInf 3.2723706e+04 2299s
1566 DPushes remaining with DInf 3.2902448e+04 2304s
1480 DPushes remaining with DInf 3.3363763e+04 2310s
1389 DPushes remaining with DInf 3.4753351e+04 2316s
1303 DPushes remaining with DInf 3.5401195e+04 2320s
1129 DPushes remaining with DInf 3.8507088e+04 2327s
1043 DPushes remaining with DInf 3.9920425e+04 2331s
959 DPushes remaining with DInf 4.0219304e+04 2336s
875 DPushes remaining with DInf 4.1792158e+04 2340s
707 DPushes remaining with DInf 4.3507839e+04 2348s
623 DPushes remaining with DInf 4.4016589e+04 2351s
455 DPushes remaining with DInf 4.5917903e+04 2358s
371 DPushes remaining with DInf 4.6636137e+04 2361s
287 DPushes remaining with DInf 4.7233298e+04 2365s
203 DPushes remaining with DInf 4.7333184e+04 2370s
119 DPushes remaining with DInf 4.7345527e+04 2375s
35 DPushes remaining with DInf 4.7351889e+04 2381s
0 DPushes remaining with DInf 4.7366652e+04 2384s
309 PPushes remaining with PInf 3.3317099e+09 2384s
205 PPushes remaining with PInf 3.3291659e+09 2386s
9 PPushes remaining with PInf 3.1518587e+09 2390s
Push phase complete: Pinf 3.1518587e+09, Dinf 7.1132421e+04 2390s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
133125 1.4014634e+02 0.000000e+00 7.110081e+04 2391s
133291 1.4012431e+02 1.193671e+02 5.704045e+14 2405s
133441 1.4012440e+02 1.085174e+02 3.565474e+13 2424s
133591 1.4011777e+02 6.640072e+02 1.048994e+15 2440s
133741 1.4009002e+02 3.065173e+03 4.085121e+14 2458s
133891 1.3995089e+02 1.543084e+04 2.875766e+14 2478s
134041 1.3967977e+02 4.822403e+04 6.878897e+14 2496s
134191 1.3966352e+02 5.775908e+04 1.126237e+16 2517s
134341 1.3961846e+02 7.803830e+04 1.303902e+14 2536s
134491 1.3934681e+02 1.777365e+05 2.531230e+14 2555s
134641 1.3896358e+02 3.091616e+05 2.928503e+14 2573s
134791 1.3878908e+02 3.728336e+05 3.466951e+15 2593s
134941 1.3866848e+02 4.155535e+05 7.864158e+14 2615s
135091 1.3848858e+02 4.875193e+05 9.320175e+14 2633s
135241 1.3816216e+02 5.377723e+05 1.473170e+14 2649s
135391 1.3805281e+02 5.571806e+05 6.360041e+16 2665s
135541 1.3799289e+02 5.654689e+05 4.787283e+15 2682s
135691 1.3713071e+02 6.512967e+05 2.784765e+15 2701s
135841 1.3611430e+02 7.865575e+05 1.481098e+14 2718s
135991 1.3538271e+02 8.500413e+05 1.060183e+14 2737s
136141 1.3504688e+02 9.014950e+05 6.119679e+16 2753s
136291 1.3489938e+02 9.322362e+05 1.421543e+16 2769s
136441 1.3482206e+02 1.064947e+06 2.524562e+16 2786s
136591 1.3463370e+02 1.207465e+06 5.103599e+16 2805s
136741 1.3411124e+02 1.521025e+06 1.365566e+17 2824s
136891 1.3362268e+02 1.706834e+06 1.428382e+17 2841s
137041 1.3231330e+02 2.389007e+06 4.605593e+16 2859s
137191 1.3111806e+02 2.751074e+06 9.119945e+16 2877s
137341 1.3039826e+02 2.982300e+06 2.359551e+16 2896s
137491 1.3033251e+02 3.004714e+06 3.768850e+17 2913s
137641 1.2929632e+02 3.358146e+06 4.234248e+16 2929s
137791 1.2969710e+02 3.212979e+06 3.918977e+17 2949s
137941 1.2756028e+02 3.987158e+06 6.503684e+16 2966s
138091 1.2576590e+02 4.617283e+06 2.881614e+16 2982s
138241 1.2545613e+02 4.817492e+06 1.444276e+16 2999s
138391 1.2428331e+02 5.804075e+06 7.186101e+17 3017s
138541 1.2411075e+02 5.900464e+06 6.966254e+16 3036s
138691 1.2405324e+02 5.931669e+06 5.409971e+16 3053s
138841 1.1986994e+02 7.067106e+06 3.113163e+14 3072s
138991 1.1720257e+02 7.686960e+06 3.630847e+16 3091s
139141 1.1644355e+02 8.666342e+06 6.794358e+16 3108s
139291 1.1314379e+02 1.037647e+07 1.105095e+17 3125s
139441 1.1146925e+02 1.104955e+07 1.904935e+18 3143s
139591 1.0967476e+02 1.179408e+07 1.982987e+18 3161s
139741 1.0652708e+02 1.265775e+07 9.749537e+15 3180s
139891 1.0410088e+02 1.331701e+07 8.951208e+14 3197s
140041 1.0022288e+02 1.434827e+07 9.363038e+15 3215s
140191 9.7488132e+01 1.498473e+07 5.800943e+16 3232s
140341 9.9442256e+01 1.436101e+07 1.746861e+15 3248s
140491 1.0142933e+02 1.359831e+07 3.651740e+15 3267s
140641 9.9406619e+01 1.434448e+07 3.402423e+14 3286s
140791 9.3176634e+01 1.622913e+07 2.702986e+15 3305s
140941 8.9742385e+01 1.752954e+07 1.605655e+16 3322s
141091 8.8146223e+01 1.807119e+07 1.446394e+16 3345s
141241 8.1267711e+01 2.043311e+07 1.171835e+16 3366s
141391 7.7046954e+01 2.206079e+07 1.189333e+16 3387s
141541 7.1470270e+01 2.410700e+07 8.572526e+17 3406s
141691 -1.6845971e+36 2.178629e+41 1.684597e+06 3417s
141841 -1.1534648e+36 4.933714e+41 1.153465e+06 3428s
141991 -5.9026784e+35 7.079075e+41 5.902679e+05 3440s
142141 -3.1983053e+35 4.558537e+41 3.198307e+05 3454s
142291 -2.5646287e+35 4.328865e+39 2.564631e+05 3467s
142441 -2.4209554e+35 4.334333e+39 2.420957e+05 3477s
142591 -1.5657693e+35 7.929680e+39 1.565772e+05 3489s
142741 -9.6900166e+34 2.430955e+41 9.690065e+04 3500s
142891 -5.9924874e+34 2.660331e+41 5.992546e+04 3511s
143041 -3.3929784e+34 2.881276e+39 3.393045e+04 3522s
143191 -2.2667240e+34 1.378990e+40 2.266799e+04 3534s
143341 -1.3940294e+34 1.294658e+40 1.394117e+04 3548s
143491 -8.5657031e+33 2.554117e+38 8.566762e+03 3560s
143641 -5.9834471e+33 3.911990e+39 5.984618e+03 3573s
143791 -4.7832348e+33 1.979349e+39 4.784531e+03 3586s
143941 -3.9071076e+33 1.695167e+39 3.908571e+03 3600s
144091 -2.9270342e+33 2.682104e+39 2.928640e+03 3613s
144241 -2.4738598e+33 1.530305e+39 2.475654e+03 3626s
144391 -2.1451362e+33 8.348718e+38 2.147089e+03 3638s
144541 -1.9023106e+33 4.011593e+38 1.904489e+03 3651s
144691 -1.6496233e+33 1.515548e+39 1.652090e+03 3664s
144841 -1.5145334e+33 5.662753e+38 1.517217e+03 3677s
144991 -1.2728477e+33 4.838389e+38 1.276103e+03 3692s
145141 -1.0530252e+33 7.920983e+38 1.056763e+03 3706s
145291 -8.8439298e+32 3.141627e+38 8.884690e+02 3721s
145441 -7.6842279e+32 2.612747e+38 7.729801e+02 3734s
145591 -6.5481994e+32 2.919206e+38 6.600205e+02 3748s
145741 -5.6065398e+32 5.305717e+38 5.662762e+02 3762s
145891 -4.7710713e+32 1.657698e+38 4.832208e+02 3777s
146041 -4.0627931e+32 1.028231e+38 4.128417e+02 3791s
146191 -3.4820475e+32 2.053469e+38 3.554718e+02 3804s
146341 -2.8343107e+32 8.423881e+37 2.915643e+02 3819s
146491 -2.3881935e+32 6.473106e+37 2.474836e+02 3834s
146641 -1.9978953e+32 2.837391e+38 2.090967e+02 3849s
146791 -1.5969871e+32 4.246499e+37 1.703814e+02 3864s
146941 -1.3616598e+32 1.050803e+38 1.482667e+02 3878s
147091 -1.1814319e+32 3.928781e+37 1.321720e+02 3894s
147241 -1.0303552e+32 7.076131e+37 1.187119e+02 3909s
147391 -9.2276463e+31 4.940827e+37 1.092293e+02 3924s
147541 -8.0682329e+31 1.140803e+38 9.881816e+01 3940s
147691 -7.3168418e+31 4.478108e+37 9.207669e+01 3955s
147841 -6.3114416e+31 2.762273e+37 8.360211e+01 3970s
147991 -5.7149223e+31 1.651612e+37 7.856230e+01 3985s
148141 -4.5702918e+31 2.977138e+37 6.945565e+01 3999s
148291 -3.7444405e+31 8.130199e+37 6.303047e+01 4015s
148441 -3.3905659e+31 1.798400e+38 5.976318e+01 4030s
148591 -2.7688565e+31 1.560707e+37 5.496134e+01 4044s
148741 -2.2118192e+31 1.539520e+37 5.214645e+01 4059s
148891 -1.8125586e+31 3.273689e+37 5.043193e+01 4074s
149041 -1.4362746e+31 4.321051e+37 4.846730e+01 4090s
149191 -1.0225791e+31 1.666339e+37 4.697690e+01 4105s
149341 -6.0412932e+30 1.943622e+37 4.606248e+01 4122s
149491 -3.0597337e+30 2.517419e+37 4.572426e+01 4138s
149641 6.8001825e+28 3.793752e+37 4.469225e+01 4155s
149791 2.8779038e+30 1.966213e+37 4.415025e+01 4171s
149941 4.6167168e+30 1.640242e+37 4.385217e+01 4189s
150091 9.5411103e+30 3.321938e+37 4.310793e+01 4205s
150241 1.3372414e+31 2.207151e+37 4.280913e+01 4221s
150391 1.7184655e+31 3.706678e+37 4.241491e+01 4237s
150541 1.9710020e+31 3.343730e+37 4.186079e+01 4254s
150691 2.3338729e+31 2.036642e+37 4.077094e+01 4271s
150841 2.7921845e+31 2.676917e+37 3.972086e+01 4288s
150991 3.1123216e+31 1.739079e+37 3.889274e+01 4306s
151141 3.3752560e+31 1.582694e+37 3.840153e+01 4324s
151291 3.7600053e+31 3.755380e+37 3.730941e+01 4340s
151441 4.0362145e+31 2.364754e+37 3.654741e+01 4357s
151591 4.5331540e+31 1.810175e+37 3.519500e+01 4374s
151741 4.9987292e+31 1.906124e+37 3.432330e+01 4391s
151891 5.3957845e+31 1.449886e+37 3.379957e+01 4407s
152041 5.7167905e+31 1.023695e+37 3.366341e+01 4424s
152191 6.0425929e+31 1.418147e+37 3.387290e+01 4442s
152341 6.5389338e+31 1.402270e+37 3.436103e+01 4460s
152491 6.8139624e+31 1.533802e+37 3.444340e+01 4477s
152641 6.9176187e+31 8.770505e+36 3.463432e+01 4493s
152791 7.2128848e+31 2.736872e+37 3.530133e+01 4511s
152941 7.5751810e+31 2.174266e+37 3.607516e+01 4530s
153091 7.8718993e+31 5.916637e+36 3.654366e+01 4547s
153241 8.0158066e+31 1.081394e+37 3.678695e+01 4566s
153391 8.1376252e+31 1.015162e+37 3.698013e+01 4581s
153541 8.5192173e+31 1.216377e+37 3.729376e+01 4596s
153691 8.7552025e+31 1.413104e+37 3.773272e+01 4612s
153841 9.0153142e+31 1.394597e+37 3.812944e+01 4635s
153991 9.1282165e+31 4.501730e+36 3.818261e+01 4662s
154141 9.5417534e+31 8.181336e+36 3.837846e+01 4688s
154291 9.7017857e+31 2.654388e+37 3.842534e+01 4718s
154441 9.8494453e+31 1.173303e+37 3.821910e+01 4750s
154591 1.0085961e+32 4.648773e+37 3.801959e+01 4772s
154741 1.0418055e+32 8.998184e+36 3.821149e+01 4795s
154891 1.0603065e+32 6.614150e+36 3.843274e+01 4815s
155041 1.0887326e+32 9.027472e+36 3.878819e+01 4839s
155191 1.1099344e+32 1.311060e+37 3.928181e+01 4863s
155341 1.1392853e+32 1.214884e+37 3.973267e+01 4895s
155491 1.1642378e+32 9.997882e+36 4.010968e+01 4915s
155641 1.1991427e+32 1.417159e+37 4.063260e+01 4938s
155791 1.2079249e+32 9.050397e+36 4.072550e+01 4958s
155941 1.2418558e+32 1.572662e+37 4.134930e+01 4978s
156091 1.2558441e+32 1.044100e+37 4.157892e+01 4997s
156241 1.2867555e+32 9.715390e+36 4.198383e+01 5019s
156391 1.3198557e+32 7.985170e+36 4.242643e+01 5038s
156541 1.3476219e+32 7.787452e+36 4.247177e+01 5055s
156691 1.3760943e+32 2.156526e+37 4.261774e+01 5072s
156841 1.3961025e+32 6.892403e+36 4.279250e+01 5090s
156991 1.4170643e+32 1.640682e+37 4.285975e+01 5110s
157141 1.4529979e+32 8.603853e+36 4.307171e+01 5130s
157291 1.4679726e+32 1.554925e+37 4.312753e+01 5150s
157441 1.4982714e+32 8.623335e+36 4.329324e+01 5173s
157591 1.5220836e+32 1.288063e+37 4.340295e+01 5194s
157741 1.5498385e+32 7.767843e+36 4.363423e+01 5217s
157891 1.5719433e+32 2.980349e+37 4.350721e+01 5238s
158041 1.5956189e+32 1.072525e+37 4.336773e+01 5255s
158191 1.6354223e+32 7.901723e+36 4.332815e+01 5273s
158341 1.6590505e+32 1.048258e+37 4.342285e+01 5293s
158491 1.6683646e+32 5.589084e+36 4.332430e+01 5314s
158641 1.6947443e+32 8.691823e+36 4.328191e+01 5337s
158791 1.7147455e+32 1.116076e+37 4.321559e+01 5361s
158941 1.7446741e+32 1.215664e+37 4.324500e+01 5383s
159091 1.7501867e+32 8.771325e+36 4.322909e+01 5404s
159241 1.7673024e+32 7.008569e+36 4.305696e+01 5425s
159391 1.7818957e+32 1.421708e+37 4.305379e+01 5446s
159541 1.7942811e+32 1.324825e+37 4.303210e+01 5480s
159691 1.8057894e+32 3.081169e+37 4.296131e+01 5503s
159841 1.8215791e+32 5.645464e+36 4.274973e+01 5524s
159991 1.8446482e+32 8.394156e+36 4.258029e+01 5545s
160141 1.8641579e+32 1.140859e+37 4.244210e+01 5571s
160291 1.8817161e+32 1.110385e+37 4.224777e+01 5593s
160441 1.9013776e+32 1.061435e+38 4.198413e+01 5616s
160591 1.9155570e+32 8.145529e+36 4.183650e+01 5638s
160741 1.9314973e+32 5.836633e+36 4.166910e+01 5659s
160891 1.9428071e+32 6.832938e+36 4.143545e+01 5682s
161041 1.9581176e+32 1.056778e+37 4.117751e+01 5704s
161191 1.9743404e+32 5.560969e+36 4.105978e+01 5725s
161341 1.9991530e+32 4.689520e+36 4.082486e+01 5751s
161491 2.0173170e+32 1.124337e+37 4.079573e+01 5776s
161641 2.0339611e+32 9.996089e+36 4.075475e+01 5796s
161791 2.0500725e+32 6.848801e+36 4.066425e+01 5812s
161941 2.0626519e+32 7.257966e+36 4.049420e+01 5836s
162091 2.0794108e+32 1.189490e+37 4.029463e+01 5859s
162241 2.0953723e+32 5.185932e+36 4.025122e+01 5884s
162391 2.1105298e+32 3.558050e+36 4.005624e+01 5907s
162541 2.1234552e+32 5.990583e+36 3.971814e+01 5928s
162691 2.1359850e+32 1.252198e+37 3.946829e+01 5954s
162841 2.1521688e+32 8.742852e+36 3.914927e+01 5977s
162916 2.1640056e+32 4.556906e+36 3.896341e+01 5987s
163066 2.1775970e+32 8.761934e+36 3.887054e+01 6007s
163216 2.1999994e+32 7.399424e+36 3.832983e+01 6028s
163366 2.2116283e+32 1.650107e+37 3.811338e+01 6049s
163516 2.2245527e+32 7.413660e+36 3.778964e+01 6069s
163666 2.2368226e+32 8.497139e+36 3.748247e+01 6091s
163816 2.2468868e+32 3.171661e+36 3.731415e+01 6111s
163966 2.2617055e+32 6.796967e+36 3.680112e+01 6131s
164116 2.2743361e+32 7.050590e+36 3.639252e+01 6153s
164266 2.2912480e+32 7.909855e+36 3.587499e+01 6174s
164416 2.3064182e+32 9.395833e+36 3.539471e+01 6196s
164566 2.3154842e+32 4.300016e+36 3.513584e+01 6217s
164716 2.3279001e+32 9.062401e+36 3.487997e+01 6240s
164866 2.3429526e+32 1.109472e+37 3.436662e+01 6264s
165016 2.3602526e+32 6.688637e+36 3.347825e+01 6283s
165166 2.3741613e+32 4.649009e+36 3.300777e+01 6304s
165316 2.3864286e+32 6.055214e+36 3.257793e+01 6328s
165391 2.3920928e+32 8.568360e+36 3.224566e+01 6339s
165541 2.4024120e+32 1.564242e+37 3.187049e+01 6362s
165691 2.4119755e+32 6.730872e+36 3.137752e+01 6388s
165841 2.4233514e+32 7.275555e+36 3.071291e+01 6407s
165991 2.4420786e+32 6.577639e+36 2.904558e+01 6429s
166141 2.4518849e+32 6.081284e+36 2.809756e+01 6442s
166291 2.4563821e+32 5.629776e+36 2.765723e+01 6456s
166441 2.4649919e+32 5.197381e+36 2.681064e+01 6470s
166591 2.4746410e+32 4.615474e+36 2.587260e+01 6484s
166666 2.4859268e+32 2.667196e+36 2.477245e+01 6492s
166816 2.4965396e+32 1.592536e+36 2.372576e+01 6507s
166966 2.5032265e+32 1.577628e+36 2.306668e+01 6520s
167116 2.5099856e+32 1.291767e+36 2.239907e+01 6535s
167266 2.5183430e+32 1.269378e+36 2.157380e+01 6550s
167416 2.5267481e+32 1.765468e+36 2.075661e+01 6571s
167566 2.5329857e+32 1.477256e+37 2.014894e+01 6593s
167716 2.5417054e+32 7.260394e+35 1.928828e+01 6615s
167866 2.5528346e+32 1.063588e+37 1.820553e+01 6637s
168016 2.5636887e+32 5.103635e+36 1.719142e+01 6658s
168166 2.5754507e+32 6.189447e+35 1.606725e+01 6679s
168316 2.5842663e+32 5.147497e+36 1.525278e+01 6703s
168466 2.5906287e+32 9.972568e+35 1.469466e+01 6724s
168616 2.6024725e+32 2.286796e+36 1.357208e+01 6743s
168766 2.6092583e+32 2.218271e+36 1.295633e+01 6764s
168916 2.6179631e+32 6.461472e+35 1.218692e+01 6787s
169066 2.6286355e+32 1.614121e+36 1.114455e+01 6808s
169216 2.6361403e+32 6.334424e+35 1.042023e+01 6829s
169366 2.6426599e+32 9.359460e+35 9.801846e+00 6853s
169516 2.6490450e+32 1.330209e+36 9.172976e+00 6875s
169666 2.6554089e+32 5.380308e+36 8.559676e+00 6899s
169816 2.6608268e+32 1.073071e+36 8.048266e+00 6920s
169966 2.6682365e+32 9.031047e+35 7.346634e+00 6940s
170116 2.6735477e+32 8.745855e+35 6.838076e+00 6960s
170266 2.6797097e+32 6.072022e+35 6.257266e+00 6980s
170416 2.6847801e+32 1.191820e+36 5.765530e+00 7000s
170566 2.6964427e+32 4.204274e+35 4.611242e+00 7020s
170716 2.7015597e+32 3.995253e+35 4.122919e+00 7040s
170791 2.7036107e+32 7.042909e+35 3.926189e+00 7052s
170941 2.7084103e+32 1.267931e+36 3.472743e+00 7075s
171091 2.7133457e+32 8.564698e+35 2.997275e+00 7099s
171241 2.7161189e+32 6.374572e+35 2.743415e+00 7124s
171391 2.7185772e+32 3.646343e+36 2.503740e+00 7150s
171541 2.7223574e+32 1.219659e+36 2.132251e+00 7173s
171691 2.7244473e+32 8.761349e+35 1.955236e+00 7196s
171841 2.7264427e+32 1.174163e+36 1.767216e+00 7216s
171991 2.7289224e+32 9.265432e+35 1.539641e+00 7237s
172141 2.7319978e+32 8.895182e+35 1.236247e+00 7258s
172291 2.7339658e+32 5.922525e+35 1.051099e+00 7282s
172441 2.7354435e+32 7.011677e+35 9.107490e-01 7304s
172591 2.7372485e+32 1.395248e+35 7.376402e-01 7327s
172741 2.7405792e+32 2.381091e+35 4.068366e-01 7344s
172891 2.7421564e+32 3.038636e+35 2.530206e-01 7363s
173041 2.7434011e+32 7.013781e+34 1.325990e-01 7383s
173191 2.7441148e+32 8.634024e+35 6.415998e-02 7406s
173341 2.7445782e+32 7.063418e+34 2.187012e-02 7427s
173469 -1.6027821e+05 8.140798e+09 0.000000e+00 7448s
173544 -1.5342303e+05 7.360836e+09 0.000000e+00 7457s
173619 -1.5194340e+05 6.563668e+09 0.000000e+00 7467s
173694 -1.4992900e+05 6.211750e+09 0.000000e+00 7478s
173769 -1.4834494e+05 6.258771e+09 0.000000e+00 7487s
173844 -1.4683448e+05 1.124530e+11 0.000000e+00 7497s
173919 -1.4500820e+05 8.690878e+09 0.000000e+00 7510s
173994 -1.4419268e+05 1.578886e+10 0.000000e+00 7523s
174069 -1.4329509e+05 1.713731e+10 0.000000e+00 7532s
174144 -1.4152556e+05 1.771211e+10 0.000000e+00 7542s
174219 -1.4019180e+05 8.179961e+09 0.000000e+00 7554s
174369 -1.3828062e+05 1.770677e+10 0.000000e+00 7577s
174519 -1.3564739e+05 2.445958e+10 0.000000e+00 7600s
174669 -1.3286404e+05 5.998973e+10 0.000000e+00 7621s
174744 -1.3142265e+05 3.429133e+10 0.000000e+00 7632s
174819 -1.2997910e+05 6.618782e+10 0.000000e+00 7642s
174969 -1.2648710e+05 4.773137e+10 0.000000e+00 7664s
175119 -1.2503235e+05 3.673676e+10 0.000000e+00 7683s
175269 -1.2344554e+05 6.460719e+09 0.000000e+00 7706s
175344 -1.2243637e+05 6.441858e+10 0.000000e+00 7716s
175494 -1.2018947e+05 8.740329e+10 0.000000e+00 7740s
175644 -1.1747372e+05 2.801387e+10 0.000000e+00 7762s
175794 -1.1511608e+05 3.122537e+10 0.000000e+00 7785s
175944 -1.1269185e+05 3.926118e+10 0.000000e+00 7807s
176094 -1.0892973e+05 1.830213e+10 0.000000e+00 7829s
176244 -1.0474701e+05 2.251770e+10 0.000000e+00 7851s
176394 -1.0205760e+05 8.522531e+09 0.000000e+00 7872s
176469 -1.0121844e+05 8.055343e+09 0.000000e+00 7880s
176619 -9.9529170e+04 2.708239e+10 0.000000e+00 7902s
176769 -9.7272496e+04 2.543928e+10 0.000000e+00 7925s
176844 -9.5877369e+04 2.777090e+10 0.000000e+00 7935s
176994 -9.4197340e+04 2.613091e+10 0.000000e+00 7957s
177144 -9.0807213e+04 1.026938e+10 0.000000e+00 7980s
177294 -8.8375967e+04 1.381998e+11 0.000000e+00 8003s
177444 -8.5970367e+04 3.522644e+10 0.000000e+00 8026s
177594 -8.3222065e+04 2.463459e+10 0.000000e+00 8052s
177744 -8.0782667e+04 1.090058e+10 0.000000e+00 8073s
177894 -7.8870086e+04 2.077009e+10 0.000000e+00 8096s
178044 -7.5958651e+04 3.118633e+10 0.000000e+00 8118s
178194 -7.3214717e+04 1.389944e+10 0.000000e+00 8142s
178344 -7.0475702e+04 1.477775e+10 0.000000e+00 8165s
178494 -6.8028933e+04 2.861412e+10 0.000000e+00 8189s
178644 -6.4941544e+04 1.883424e+10 0.000000e+00 8215s
178794 -6.2701573e+04 4.691379e+10 0.000000e+00 8240s
178944 -6.1337275e+04 2.291725e+10 0.000000e+00 8264s
179094 -5.8461479e+04 9.726575e+10 0.000000e+00 8288s
179169 -5.7009239e+04 1.347479e+10 0.000000e+00 8299s
179319 -5.5115085e+04 3.667634e+10 0.000000e+00 8322s
179394 -5.4194646e+04 2.968814e+10 0.000000e+00 8332s
179544 -5.1501584e+04 2.230431e+10 0.000000e+00 8354s
179694 -4.9211045e+04 1.842034e+10 0.000000e+00 8374s
179844 -4.6888138e+04 8.961948e+09 0.000000e+00 8397s
179919 -4.4813887e+04 2.355772e+10 0.000000e+00 8407s
180069 -4.1764975e+04 3.726644e+10 0.000000e+00 8430s
180219 -3.8417559e+04 2.851877e+10 0.000000e+00 8453s
180369 -3.5509199e+04 2.881885e+10 0.000000e+00 8473s
180519 -3.2804062e+04 2.390335e+10 0.000000e+00 8494s
180669 -2.8914763e+04 1.447719e+10 0.000000e+00 8518s
180744 -2.7480121e+04 3.444839e+10 0.000000e+00 8531s
180894 -2.4714875e+04 2.625537e+10 0.000000e+00 8553s
181044 -2.1916804e+04 9.497233e+10 0.000000e+00 8574s
181119 -2.0266052e+04 1.156793e+10 0.000000e+00 8587s
181269 -1.8373647e+04 9.552591e+09 0.000000e+00 8612s
181419 -1.6598804e+04 5.676989e+09 0.000000e+00 8636s
181569 -1.3879836e+04 2.023675e+10 0.000000e+00 8660s
181719 -1.2288685e+04 3.392245e+10 0.000000e+00 8681s
181869 -9.3285242e+03 1.717904e+10 0.000000e+00 8701s
182019 -6.5299012e+03 6.672336e+09 0.000000e+00 8727s
182169 -5.0202884e+03 1.722706e+10 0.000000e+00 8748s
182319 -1.9251930e+03 2.994903e+10 0.000000e+00 8768s
182469 1.4692441e+03 1.681342e+10 0.000000e+00 8788s
182619 4.0113933e+03 1.599564e+10 0.000000e+00 8809s
182769 6.9657289e+03 2.815524e+10 0.000000e+00 8830s
182919 9.8171224e+03 1.148555e+10 0.000000e+00 8851s
183069 1.2623004e+04 2.604028e+10 0.000000e+00 8871s
183219 1.4999728e+04 1.987854e+10 0.000000e+00 8896s
183369 1.6932743e+04 5.187041e+09 0.000000e+00 8919s
183519 1.8985150e+04 3.077356e+10 0.000000e+00 8941s
183594 2.0379040e+04 1.559058e+10 0.000000e+00 8950s
183669 2.2137849e+04 7.110204e+09 0.000000e+00 8961s
183819 2.4462511e+04 2.898315e+10 0.000000e+00 8981s
183969 2.6484266e+04 1.009090e+10 0.000000e+00 9003s
184119 2.9068783e+04 1.733266e+10 0.000000e+00 9026s
184269 3.1318629e+04 7.026566e+09 0.000000e+00 9047s
184344 3.2612921e+04 3.093958e+10 0.000000e+00 9057s
184494 3.4823324e+04 1.757600e+10 0.000000e+00 9078s
184644 3.6543975e+04 4.409508e+10 0.000000e+00 9098s
184719 3.8052285e+04 7.021335e+10 0.000000e+00 9107s
184794 3.9297042e+04 1.169183e+10 0.000000e+00 9118s
184944 4.1637144e+04 2.181280e+10 0.000000e+00 9142s
185094 4.4675258e+04 1.751756e+10 0.000000e+00 9165s
185244 4.8371349e+04 3.975396e+10 0.000000e+00 9186s
185394 4.9878437e+04 2.530630e+10 0.000000e+00 9205s
185544 5.2475996e+04 1.481185e+10 0.000000e+00 9227s
185694 5.5444272e+04 3.985737e+10 0.000000e+00 9248s
185844 5.8199938e+04 1.537705e+10 0.000000e+00 9269s
185994 6.0809167e+04 1.431179e+10 0.000000e+00 9288s
186069 6.2862231e+04 3.726718e+10 0.000000e+00 9298s
186219 6.5232676e+04 2.021052e+10 0.000000e+00 9317s
186369 6.8315842e+04 1.381754e+10 0.000000e+00 9339s
186519 7.1038848e+04 1.899172e+10 0.000000e+00 9361s
186669 7.3964645e+04 6.125584e+09 0.000000e+00 9383s
186819 7.6195958e+04 1.825998e+10 0.000000e+00 9405s
186969 7.9496698e+04 2.094705e+10 0.000000e+00 9428s
187119 8.1525927e+04 5.515990e+09 0.000000e+00 9451s
187269 8.4656805e+04 3.835414e+10 0.000000e+00 9474s
187419 8.7424982e+04 1.104715e+10 0.000000e+00 9495s
187569 8.9515601e+04 1.712657e+11 0.000000e+00 9517s
187719 9.1156457e+04 6.347538e+09 0.000000e+00 9542s
187869 9.3800579e+04 1.895334e+10 0.000000e+00 9565s
187944 9.5103774e+04 5.034034e+10 0.000000e+00 9574s
188094 9.7789444e+04 2.214047e+10 0.000000e+00 9595s
188244 1.0033198e+05 3.475202e+10 0.000000e+00 9619s
188394 1.0292533e+05 1.956198e+10 0.000000e+00 9641s
188544 1.0678568e+05 9.325822e+09 0.000000e+00 9664s
188694 1.0905155e+05 1.261052e+10 0.000000e+00 9687s
188844 1.1162422e+05 8.086345e+09 0.000000e+00 9711s
188994 1.1475756e+05 2.051425e+10 0.000000e+00 9734s
189144 1.1677774e+05 4.483543e+09 0.000000e+00 9758s
189294 1.1975607e+05 8.910964e+09 0.000000e+00 9782s
189444 1.2266726e+05 1.571795e+10 0.000000e+00 9805s
189594 1.2566255e+05 2.690178e+10 0.000000e+00 9829s
189744 1.2831560e+05 1.027380e+10 0.000000e+00 9852s
189894 1.3090259e+05 2.384077e+10 0.000000e+00 9877s
190044 1.3412315e+05 7.845353e+10 0.000000e+00 9901s
190194 1.3596502e+05 7.844268e+09 0.000000e+00 9927s
190344 1.3804530e+05 5.052675e+09 0.000000e+00 9951s
190494 1.4041556e+05 5.368169e+10 0.000000e+00 9972s
190644 1.4347225e+05 1.609119e+10 0.000000e+00 9997s
190794 1.4698260e+05 6.401803e+09 0.000000e+00 10019s
190944 1.4857362e+05 6.338424e+09 0.000000e+00 10045s
191094 1.5140879e+05 7.999674e+10 0.000000e+00 10071s
191244 1.5233307e+05 7.048828e+09 0.000000e+00 10095s
191394 1.5428850e+05 9.450773e+09 0.000000e+00 10121s
191544 1.5661510e+05 1.316799e+10 0.000000e+00 10148s
191694 1.5954866e+05 1.949144e+10 0.000000e+00 10168s
191769 1.6116021e+05 5.953003e+09 0.000000e+00 10180s
191919 1.6400568e+05 1.856561e+10 0.000000e+00 10205s
192069 1.6587961e+05 9.002905e+09 0.000000e+00 10230s
192219 1.6784819e+05 3.468062e+10 0.000000e+00 10255s
192369 1.7012518e+05 5.322657e+09 0.000000e+00 10281s
192519 1.7214231e+05 8.142047e+09 0.000000e+00 10306s
192594 1.7400126e+05 5.058331e+09 0.000000e+00 10317s
192669 1.7497835e+05 1.045958e+10 0.000000e+00 10329s
192819 1.7714652e+05 6.402963e+09 0.000000e+00 10352s
192969 1.7873173e+05 1.367450e+10 0.000000e+00 10376s
193119 1.8054466e+05 5.289392e+10 0.000000e+00 10401s
193269 1.8290953e+05 2.670351e+10 0.000000e+00 10429s
193419 1.8444572e+05 2.279782e+10 0.000000e+00 10455s
193569 1.8639323e+05 9.004382e+09 0.000000e+00 10481s
193719 1.8821748e+05 4.225091e+10 0.000000e+00 10506s
193794 1.8964841e+05 9.249847e+09 0.000000e+00 10519s
193944 1.9043868e+05 1.764414e+10 0.000000e+00 10543s
194094 1.9352900e+05 1.038077e+10 0.000000e+00 10566s
194244 1.9566942e+05 1.212980e+10 0.000000e+00 10593s
194394 1.9818156e+05 9.984601e+09 0.000000e+00 10618s
194544 2.0062912e+05 9.448050e+09 0.000000e+00 10642s
194694 2.0275131e+05 1.783358e+10 0.000000e+00 10665s
194844 2.0504463e+05 1.083455e+10 0.000000e+00 10689s
194919 2.0786591e+05 2.657730e+09 0.000000e+00 10698s
194994 2.1029716e+05 4.666289e+09 0.000000e+00 10707s
195069 2.1204277e+05 4.248916e+09 0.000000e+00 10715s
195144 2.1360241e+05 4.227443e+09 0.000000e+00 10725s
195219 2.1507443e+05 4.068019e+09 0.000000e+00 10734s
195294 2.1648352e+05 4.191196e+09 0.000000e+00 10743s
195369 2.1750928e+05 1.831457e+09 0.000000e+00 10751s
195444 2.1873732e+05 1.860552e+09 0.000000e+00 10758s
195519 2.2056506e+05 1.821903e+09 0.000000e+00 10765s
195594 2.2208543e+05 1.831192e+09 0.000000e+00 10772s
195669 2.2358881e+05 1.820126e+09 0.000000e+00 10780s
195744 2.2491320e+05 2.623651e+09 0.000000e+00 10789s
195819 2.2571862e+05 2.499390e+09 0.000000e+00 10797s
195894 2.2698124e+05 2.385948e+09 0.000000e+00 10805s
196044 2.2844835e+05 7.629223e+09 0.000000e+00 10831s
196194 2.3052909e+05 1.576120e+10 0.000000e+00 10856s
196344 2.3242640e+05 9.097545e+09 0.000000e+00 10881s
196494 2.3411641e+05 2.617497e+10 0.000000e+00 10906s
196644 2.3621593e+05 1.012845e+11 0.000000e+00 10931s
196794 2.3778098e+05 5.334172e+09 0.000000e+00 10955s
196944 2.3986800e+05 7.672542e+09 0.000000e+00 10980s
197094 2.4158813e+05 4.722237e+09 0.000000e+00 11005s
197244 2.4418569e+05 1.326355e+10 0.000000e+00 11024s
197394 2.4631022e+05 8.455074e+09 0.000000e+00 11044s
197544 2.4799908e+05 1.119989e+10 0.000000e+00 11062s
197694 2.4967612e+05 7.560244e+09 0.000000e+00 11084s
197844 2.5180063e+05 6.816714e+09 0.000000e+00 11105s
197994 2.5346410e+05 1.208034e+10 0.000000e+00 11126s
198144 2.5544767e+05 9.382112e+09 0.000000e+00 11149s
198294 2.5755052e+05 5.487108e+09 0.000000e+00 11174s
198444 2.5967678e+05 3.325848e+10 0.000000e+00 11200s
198519 2.6049939e+05 1.546124e+10 0.000000e+00 11209s
198669 2.6207429e+05 1.258016e+10 0.000000e+00 11228s
198819 2.6392457e+05 5.946010e+09 0.000000e+00 11252s
198969 2.6552253e+05 1.313111e+10 0.000000e+00 11276s
199119 2.6723109e+05 1.473886e+10 0.000000e+00 11301s
199269 2.6915350e+05 1.364484e+10 0.000000e+00 11325s
199419 2.7138560e+05 1.193436e+10 0.000000e+00 11349s
199569 2.7337733e+05 5.194627e+09 0.000000e+00 11370s
-
Hi Antonios,
Your model is quite large, and according to your log, the progress does not even pass the root relaxation phase. It seems that the simplex algorithm has a hard time with your model, this is why the barrier finishes first. But barrier solutions need to be transformed into a basic solution in the crossover phase (where, again, simplex comes into play). This crossover phase takes far longer than barrier took. However, for using simplex during branch-and-bound, you need a basic solution. Alternatively, you could completely switch to barrier, both in the root relaxation and during branch-and-bound, and deactivate crossover (with parameters Method=2, Crossover=0, NodeMethod=2). This could, however, harm the branch-and-bound progress. Still worth a try.
If you quickly need a feasible solution, you might try the NoRel heuristic, by setting parameter NoRelHeurTime=<# seconds> to the amount of seconds that NoRel is allowed to run. This heuristic runs before the root relaxation and often finds solutions even for very large models.
Best regards,
Mario0 -
Dear Mario,
thank you for the quick reply. In my present mathematical program, I minimize two objective functions. To cast this in a tractable format, I utilize the ε-constraint technique, where I minimize the first objective function, but I need to respect the ε-constraint that I have imposed.
Let us consider the case where ε=0. This completely disregards the effect of the second objective function, and I optimize solely based on the first objective function.
In other words, I want to solve the optimization problem for different values of ε, i.e., ε=0,10,20,...,100.For the question I have posed in the post, I have considered that ε=0, which essentially is the simplest case, for which I know beforehand the optimal solution.
I followed your suggestion and set Method=2, CrossOver=0, NodeMethod=2, and indeed, I was able to receive a feasible solution for the optimization for each value of ε mentioned above. However, the solution I received was the same for each value of ε, which is not what I want to achieve.
I guess that setting the above-mentioned values for these parameters triggered the behavior that you predicted before in terms of harming the branch-and-bound progress when considering different values of ε.My current objective is to pinpoint the optimal solution for each value of ε. Hence, the feasibility aspect alone is not enough.
I saw from the Gurobi manual that when one needs to focus on optimality rather than feasibility, then setting MIPFocus=2 might help.It appears that setting: CrossoverBasis=1, Method=2, presolve=2, DegenMoves=0, MIPFocus=2, NodeMethod=2, and Crossover=-1 (default value) leads to a significant reduction in terms of the root crossover phase. Still, the root simplex log continues indefinitely until the time-limit=36000 seconds, parameter is exceeded, where I get a message stating that my optimization formulation leads to Infeasibility.
I attach a part of the log for ε=0:Set parameter Username
Set parameter TimeLimit to value 36000
Set parameter Method to value 2
Set parameter CrossoverBasis to value 1
Set parameter DegenMoves to value 0
Set parameter MIPFocus to value 2
Set parameter NodeMethod to value 2
Set parameter Presolve to value 2
Academic license - for non-commercial use only - expires 2025-01-15
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 11+.0 (22631.2))
CPU model: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 5788538 rows, 33964001 columns and 20903685 nonzeros
Model fingerprint: 0x42bb536f
Variable types: 33963001 continuous, 1000 integer (1000 binary)
Coefficient statistics:
Matrix range [4e-03, 7e+01]
Objective range [8e-03, 8e-03]
Bounds range [1e+00, 3e+03]
RHS range [1e-02, 5e+03]
Presolve removed 0 rows and 0 columns (presolve time = 5s) ...
Presolve removed 2157164 rows and 31156761 columns (presolve time = 10s) ...
Presolve removed 4564546 rows and 32859778 columns (presolve time = 15s) ...
Presolve removed 4564546 rows and 32859778 columns
Presolve time: 16.61s
Presolved: 1223992 rows, 1104223 columns, 5898957 nonzeros
Variable types: 1102060 continuous, 2163 integer (0 binary)
Root relaxation presolve removed 1018 rows and 879 columns
Root relaxation presolved: 300131 rows, 289373 columns, 1349671 nonzeros
Root barrier log...
Ordering time: 7.09s
Barrier statistics:
AA' NZ : 2.119e+06
Factor NZ : 5.954e+07 (roughly 700 MB of memory)
Factor Ops : 8.835e+10 (roughly 2 seconds per iteration)
Threads : 4
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -1.83776659e+06 -9.22270921e+07 6.60e+04 1.66e-01 2.17e+03 184s
1 -1.15607668e+06 -8.26299870e+07 4.15e+04 9.18e-01 1.37e+03 186s
2 -2.44687059e+05 -5.06140893e+07 8.82e+03 2.24e-14 3.16e+02 189s
3 -5.48555135e+04 -1.62430242e+07 2.01e+03 2.15e-14 7.19e+01 191s
4 -3.58659859e+04 -7.76871845e+06 1.34e+03 1.83e-14 4.07e+01 194s
5 -1.53869121e+04 -3.83820064e+06 6.03e+02 1.37e-13 1.79e+01 197s
6 -3.60422842e+03 -1.80446322e+06 1.82e+02 7.86e-14 5.92e+00 199s
7 -4.41503269e+02 -7.94178764e+05 6.85e+01 1.59e-13 2.24e+00 202s
8 4.21437881e+02 -4.59696030e+05 3.67e+01 9.15e-14 1.20e+00 205s
9 9.40556606e+02 -2.51454189e+05 1.63e+01 8.48e-14 5.81e-01 209s
10 1.10006292e+03 -1.84091525e+05 9.52e+00 1.28e-13 3.86e-01 212s
11 1.16722208e+03 -1.46670565e+05 6.37e+00 9.95e-14 2.88e-01 215s
12 1.20630052e+03 -1.05760933e+05 4.35e+00 1.71e-13 2.02e-01 218s
13 1.23144111e+03 -7.50210468e+04 2.76e+00 1.71e-13 1.38e-01 222s
14 1.23506049e+03 -7.01291034e+04 2.49e+00 1.85e-13 1.27e-01 225s
15 1.24221200e+03 -4.51251108e+04 1.77e+00 3.41e-13 8.30e-02 229s
16 1.24147357e+03 -3.26602717e+04 1.12e+00 3.55e-13 5.82e-02 233s
17 1.21926128e+03 -2.65944978e+04 6.29e-01 1.56e-13 4.46e-02 237s
18 1.21229171e+03 -1.68446065e+04 5.38e-01 1.53e-13 2.98e-02 240s
19 1.18471255e+03 -1.64844871e+04 3.99e-01 2.40e-13 2.80e-02 243s
20 1.15612857e+03 -9.72894147e+03 2.96e-01 7.53e-13 1.75e-02 247s
21 1.09270379e+03 -6.69935105e+03 1.80e-01 5.42e-13 1.22e-02 250s
22 1.03967957e+03 -5.22180658e+03 1.37e-01 4.14e-13 9.70e-03 254s
23 9.43192262e+02 -3.95305696e+03 8.73e-02 3.28e-13 7.41e-03 258s
24 7.89004189e+02 -1.83771506e+03 5.07e-02 2.42e-13 3.98e-03 261s
25 5.73835954e+02 -9.57789084e+02 2.16e-02 2.20e-13 2.26e-03 265s
26 4.15135280e+02 -3.92385290e+02 1.06e-02 3.55e-13 1.19e-03 269s
27 2.93036113e+02 -9.89520440e+01 4.71e-03 4.12e-13 5.73e-04 272s
28 2.18067624e+02 4.58911476e+01 1.95e-03 5.68e-13 2.51e-04 276s
29 1.76404572e+02 1.01254516e+02 8.16e-04 6.82e-13 1.09e-04 280s
30 1.62453304e+02 1.28193720e+02 4.80e-04 9.09e-13 5.05e-05 284s
31 1.54194918e+02 1.34656058e+02 2.88e-04 7.11e-13 2.89e-05 287s
32 1.52656882e+02 1.35718868e+02 2.52e-04 6.96e-13 2.51e-05 290s
33 1.49602103e+02 1.37365179e+02 1.83e-04 8.24e-13 1.81e-05 294s
34 1.46819020e+02 1.38614104e+02 1.23e-04 9.52e-13 1.21e-05 297s
35 1.44813476e+02 1.39767533e+02 7.55e-05 8.38e-13 7.45e-06 300s
36 1.43274081e+02 1.40571489e+02 3.97e-05 4.69e-13 3.98e-06 305s
37 1.42586064e+02 1.41045031e+02 2.42e-05 5.83e-13 2.27e-06 311s
38 1.42058131e+02 1.41219043e+02 1.23e-05 6.11e-13 1.22e-06 317s
39 1.41820194e+02 1.41312766e+02 6.94e-06 4.69e-13 7.35e-07 322s
40 1.41684093e+02 1.41364804e+02 4.02e-06 3.69e-13 4.59e-07 329s
41 1.41636565e+02 1.41406575e+02 2.93e-06 2.27e-13 3.30e-07 333s
42 1.41591631e+02 1.41442005e+02 1.90e-06 1.56e-13 2.14e-07 336s
43 1.41557305e+02 1.41472143e+02 1.12e-06 1.07e-13 1.22e-07 341s
44 1.41533775e+02 1.41486450e+02 5.92e-07 8.17e-14 6.73e-08 345s
45 1.41522027e+02 1.41498212e+02 3.29e-07 3.20e-14 3.38e-08 350s
46 1.41515677e+02 1.41503151e+02 1.91e-07 3.07e-13 1.78e-08 355s
47 1.41511790e+02 1.41504567e+02 1.05e-07 5.03e-13 1.02e-08 358s
48 1.41510154e+02 1.41505621e+02 6.94e-08 6.83e-13 6.41e-09 362s
49 1.41509030e+02 1.41505949e+02 4.49e-08 1.09e-12 4.34e-09 365s
50 1.41508222e+02 1.41506242e+02 2.74e-08 1.87e-12 2.78e-09 368s
51 1.41507805e+02 1.41506542e+02 1.86e-08 1.55e-12 1.77e-09 372s
52 1.41507529e+02 1.41506729e+02 1.26e-08 1.12e-12 1.12e-09 376s
53 1.41507324e+02 1.41506835e+02 8.24e-09 1.40e-12 6.82e-10 380s
54 1.41507187e+02 1.41506866e+02 5.38e-09 9.25e-13 4.48e-10 384s
55 1.41507096e+02 1.41506887e+02 6.18e-08 7.87e-13 2.91e-10 388s
56 1.41507046e+02 1.41506906e+02 1.27e-07 6.16e-13 1.94e-10 392s
57 1.41507012e+02 1.41506911e+02 1.84e-07 4.89e-13 1.40e-10 395s
58 1.41506990e+02 1.41506919e+02 1.31e-07 3.07e-13 9.82e-11 400s
59 1.41506968e+02 1.41506924e+02 8.38e-08 2.36e-13 6.09e-11 405s
60 1.41506958e+02 1.41506928e+02 8.34e-08 1.67e-13 4.17e-11 409s
Barrier solved model in 60 iterations and 409.15 seconds (131.30 work units)
Optimal objective 1.41506958e+02
Root crossover log...
Warning: 1 variables dropped from basis
Warning: 7 variables dropped from basis
Warning: 3 variables dropped from basis
Warning: 1 variables dropped from basis
Restart crossover...
155050 DPushes remaining with DInf 2.3193758e+00 413s
45282 DPushes remaining with DInf 2.2681186e+00 418s
25378 DPushes remaining with DInf 2.8049372e+00 420s
9378 DPushes remaining with DInf 1.6338431e+01 425s
7070 DPushes remaining with DInf 1.4328665e+02 430s
6760 DPushes remaining with DInf 1.4304647e+02 435s
6540 DPushes remaining with DInf 1.4314778e+02 440s
6310 DPushes remaining with DInf 1.4419668e+02 447s
6148 DPushes remaining with DInf 1.4213751e+02 451s
5761 DPushes remaining with DInf 1.4183685e+02 458s
5460 DPushes remaining with DInf 1.4186856e+02 460s
5025 DPushes remaining with DInf 1.4190322e+02 469s
4755 DPushes remaining with DInf 1.4253893e+02 473s
4473 DPushes remaining with DInf 1.4255367e+02 477s
4243 DPushes remaining with DInf 1.4252963e+02 482s
4053 DPushes remaining with DInf 1.4253040e+02 487s
3761 DPushes remaining with DInf 1.4238763e+02 492s
3527 DPushes remaining with DInf 1.4225116e+02 497s
3367 DPushes remaining with DInf 1.4176143e+02 502s
3182 DPushes remaining with DInf 1.4158194e+02 507s
2972 DPushes remaining with DInf 1.4124914e+02 511s
2800 DPushes remaining with DInf 1.4140023e+02 516s
2629 DPushes remaining with DInf 1.4142658e+02 520s
2274 DPushes remaining with DInf 1.4088455e+02 529s
2048 DPushes remaining with DInf 1.4091375e+02 534s
1813 DPushes remaining with DInf 9.5401829e+05 539s
1638 DPushes remaining with DInf 9.5059732e+05 542s
1405 DPushes remaining with DInf 9.4984910e+05 546s
943 DPushes remaining with DInf 9.3858874e+05 553s
733 DPushes remaining with DInf 9.4386758e+05 556s
148 DPushes remaining with DInf 9.4367720e+05 562s
0 DPushes remaining with DInf 8.9608356e+05 564s
3354 PPushes remaining with PInf 5.6353371e+06 564s
2800 PPushes remaining with PInf 5.5306680e+06 566s
1182 PPushes remaining with PInf 4.4791295e+06 571s
0 PPushes remaining with PInf 3.9397902e+06 575s
Push phase complete: Pinf 3.9397902e+06, Dinf 2.9455736e+02 576s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
91280 1.3690781e+02 0.000000e+00 2.945574e+02 576s
91420 1.3690781e+02 0.000000e+00 1.556222e+01 580s
91700 1.3690781e+02 0.000000e+00 2.600401e+01 589s
91840 1.3690781e+02 0.000000e+00 4.294042e+02 594s
91980 1.3690780e+02 0.000000e+00 4.174520e+03 599s
92120 1.3690777e+02 0.000000e+00 7.386196e+02 604s
92270 1.3690759e+02 0.000000e+00 5.380789e+03 609s
92460 1.3690724e+02 0.000000e+00 6.821016e+06 614s
92630 1.3690620e+02 0.000000e+00 1.354219e+05 620s
92780 1.3690557e+02 0.000000e+00 3.663916e+03 625s
92950 1.3690547e+02 0.000000e+00 8.712810e+04 630s
93110 1.3690335e+02 0.000000e+00 6.271512e+05 636s
93230 1.3690312e+02 0.000000e+00 7.540669e+05 641s
93340 1.3690302e+02 0.000000e+00 8.410555e+05 647s
93440 1.3690299e+02 0.000000e+00 1.005486e+06 652s
93540 1.3690264e+02 0.000000e+00 4.220777e+05 656s
93640 1.3690173e+02 0.000000e+00 5.300029e+06 660s
93850 1.3690115e+02 0.000000e+00 5.156432e+05 670s
93950 1.3690053e+02 0.000000e+00 1.634074e+06 676s
94050 1.3689991e+02 0.000000e+00 4.538791e+03 682s
94150 1.3689975e+02 0.000000e+00 1.494716e+05 691s
94250 1.3689972e+02 0.000000e+00 7.784185e+04 695s
94370 1.3689950e+02 0.000000e+00 4.034519e+05 700s
94490 1.3689949e+02 0.000000e+00 2.884548e+05 706s
94610 1.3689934e+02 0.000000e+00 2.229441e+06 711s
94740 1.3689931e+02 0.000000e+00 1.875407e+06 716s
94860 1.3689918e+02 0.000000e+00 1.118993e+06 721s
94980 1.3689913e+02 0.000000e+00 1.795967e+06 726s
95100 1.3689909e+02 0.000000e+00 1.072492e+06 731s
95220 1.3689903e+02 0.000000e+00 8.564352e+05 736s
95340 1.3689861e+02 0.000000e+00 2.103654e+03 741s
95480 1.3689849e+02 0.000000e+00 1.925698e+05 747s
95610 1.3689846e+02 0.000000e+00 8.037324e+05 753s
95740 1.3689843e+02 0.000000e+00 3.862034e+05 760s
95870 1.3689836e+02 0.000000e+00 1.007762e+06 768s
95990 1.3689795e+02 0.000000e+00 3.254240e+07 778s
96110 1.3689781e+02 0.000000e+00 1.371776e+06 786s
96250 1.3689778e+02 0.000000e+00 5.009658e+06 793s
96400 1.3689752e+02 0.000000e+00 5.652216e+06 801s
96540 1.3689749e+02 0.000000e+00 2.522830e+05 807s
96690 1.3689747e+02 0.000000e+00 3.422328e+05 819s
96870 1.3689686e+02 0.000000e+00 8.157110e+04 835s
96970 1.3689680e+02 0.000000e+00 1.182152e+05 842s
97080 1.3689668e+02 0.000000e+00 2.285819e+05 849s
97190 1.3689667e+02 0.000000e+00 4.367865e+05 857s
97340 1.3689615e+02 0.000000e+00 1.948211e+06 869s
97490 1.3689534e+02 0.000000e+00 1.011943e+07 878s
97680 1.3689269e+02 0.000000e+00 1.651718e+03 886s
97840 1.3689262e+02 0.000000e+00 9.189352e+04 896sWhat would you suggest so that I can force Gurobi to try to find the optimal solution for each value of ε? So far, I have 5788538 constraints and 33964001 decision variables, out of which 1000 are binary. Do you think that Gurobi has trouble finding the optimal solution for such a model?
Could it be the case that my problem is subject to numerical instability?
Any advice would be more than welcome.
Thank you.0 -
Hello there,
as a side comment relevant to the discussion above, to reduce the number of d.v. and constraints, respectively, I tried to remove the constraints, which contained the binary quantities, and solve an LP instead. This version of the original problem makes sense only for the case where ε=0. In this case, I expect to obtain exactly the same response solving the LP with the solution obtained from the MILP.
As it turns out, though, for a horizon K=200, LP cannot provide me a feasible solution, either.
I also switched to a much stronger PC, and I have left it running for nearly a day, but still Gurobi is still running.
I attach a part of the log file for the LP.
Set parameter Username
Set parameter Method to value 3
Set parameter Crossover to value 0
Set parameter Presolve to value 2
Academic license - for non-commercial use only - expires 2025-01-15
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 10.0 (19044.2))
CPU model: Intel(R) Core(TM) i9-10980XE CPU @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 18 physical cores, 36 logical processors, using up to 18 threads
Optimize a model with 5728812 rows, 33483000 columns and 20773610 nonzeros
Model fingerprint: 0xab138f5f
Coefficient statistics:
Matrix range [8e-03, 7e+01]
Objective range [8e-03, 8e-03]
Bounds range [1e+01, 3e+03]
RHS range [4e-03, 5e+03]
Presolve removed 4786349 rows and 32760936 columns (presolve time = 6s) ...
Presolve removed 5222063 rows and 33168554 columns (presolve time = 10s) ...
Presolve removed 5398704 rows and 33168554 columns (presolve time = 16s) ...
Presolve removed 5398704 rows and 33168554 columns
Presolve time: 19.02s
Presolved: 330108 rows, 314446 columns, 1541173 nonzeros
Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Warning: Concurrent optimizer requires crossover - forcing it on
Elapsed ordering time = 5s
Ordering time: 9.55s
Barrier statistics:
AA' NZ : 2.559e+06
Factor NZ : 1.170e+08 (roughly 1.2 GB of memory)
Factor Ops : 4.201e+11 (roughly 1 second per iteration)
Threads : 16
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -1.36228938e+07 -5.84032845e+06 3.34e+06 2.49e-03 7.00e+03 32s
1 -4.85496197e+06 -5.33746124e+06 1.19e+06 5.16e-02 2.58e+03 33s
2 -1.02199515e+06 -3.07473539e+06 2.51e+05 5.00e-15 5.92e+02 35s
3 -2.68729925e+05 -1.14055368e+06 6.64e+04 8.47e-16 1.54e+02 37s
4 -1.16316785e+05 -4.71436607e+05 2.90e+04 1.05e-15 6.05e+01 39s
5 -5.82280927e+04 -2.39332011e+05 1.47e+04 1.49e-15 2.90e+01 41s
6 -3.27473707e+04 -1.31532010e+05 8.43e+03 3.47e-15 1.55e+01 43s
7 -1.65170676e+04 -8.74630966e+04 4.44e+03 2.84e-15 8.53e+00 45s
8 -9.25344329e+03 -5.33385694e+04 2.65e+03 2.46e-15 4.86e+00 46s
9 -4.74520613e+03 -3.32345406e+04 1.53e+03 2.11e-15 2.79e+00 48s
10 -2.53825441e+03 -2.74463357e+04 9.81e+02 2.69e-15 2.02e+00 49s
11 -1.28385001e+03 -1.74961915e+04 6.64e+02 4.53e-15 1.32e+00 51s
12 2.49569840e+02 -9.63840698e+03 2.63e+02 4.19e-15 6.59e-01 53s
13 7.05573576e+02 -5.34815464e+03 1.05e+02 4.76e-15 3.43e-01 55s
14 7.54448303e+02 -2.59927525e+03 3.38e+01 5.20e-15 1.63e-01 57s
15 6.11320117e+02 -1.59257273e+03 1.48e+01 4.48e-15 9.94e-02 58s
16 3.90384864e+02 -5.23774867e+02 6.67e+00 5.31e-15 4.07e-02 60s
17 2.73083377e+02 -1.66152446e+02 3.29e+00 3.93e-15 1.93e-02 62s
18 1.93370850e+02 -1.42198061e+01 1.41e+00 3.65e-15 8.96e-03 63s
19 1.57184904e+02 4.84961549e+01 7.35e-01 2.62e-15 4.66e-03 65s
20 1.38357689e+02 8.07257485e+01 4.15e-01 2.21e-15 2.46e-03 67s
21 1.26904076e+02 9.44426891e+01 2.27e-01 1.30e-15 1.38e-03 69s
22 1.20916303e+02 1.00388916e+02 1.32e-01 8.76e-16 8.68e-04 71s
23 1.17476352e+02 1.04815043e+02 7.84e-02 1.11e-15 5.33e-04 75s
24 1.15443649e+02 1.08333087e+02 4.76e-02 5.73e-16 3.00e-04 80s
25 1.14183473e+02 1.10776209e+02 2.88e-02 4.83e-16 1.45e-04 85s
26 1.13340696e+02 1.11381577e+02 1.65e-02 4.72e-16 8.33e-05 89s
27 1.12908588e+02 1.11642475e+02 1.01e-02 5.23e-16 5.37e-05 93s
28 1.12621031e+02 1.11880038e+02 6.00e-03 3.96e-13 3.14e-05 98s
29 1.12459987e+02 1.11999342e+02 3.71e-03 7.52e-13 1.95e-05 102s
30 1.12346172e+02 1.12071032e+02 2.11e-03 8.65e-13 1.16e-05 106s
31 1.12294133e+02 1.12136224e+02 1.38e-03 7.71e-13 6.71e-06 111s
32 1.12250497e+02 1.12159344e+02 7.74e-04 6.60e-13 3.87e-06 115s
33 1.12227002e+02 1.12176405e+02 4.48e-04 4.73e-13 2.15e-06 120s
34 1.12214870e+02 1.12185059e+02 2.83e-04 3.23e-13 1.27e-06 124s
35 1.12205286e+02 1.12187640e+02 1.56e-04 2.59e-13 7.50e-07 129s
36 1.12202094e+02 1.12189629e+02 1.12e-04 2.10e-13 5.30e-07 133s
37 1.12199912e+02 1.12192118e+02 8.15e-05 1.42e-13 3.34e-07 137s
38 1.12197049e+02 1.12192953e+02 4.27e-05 1.06e-13 1.76e-07 142s
39 1.12195639e+02 1.12193359e+02 2.33e-05 8.08e-14 9.76e-08 147s
40 1.12194823e+02 1.12193635e+02 1.21e-05 5.51e-14 5.08e-08 151s
41 1.12194516e+02 1.12193802e+02 7.86e-06 3.17e-14 3.07e-08 156s
42 1.12194305e+02 1.12193841e+02 5.00e-06 2.48e-14 1.99e-08 160s
43 1.12194187e+02 1.12193891e+02 3.39e-06 1.44e-14 1.28e-08 164s
44 1.12194080e+02 1.12193908e+02 1.95e-06 9.44e-15 7.41e-09 168s
45 1.12194015e+02 1.12193918e+02 1.07e-06 6.43e-15 4.17e-09 173s
46 1.12193983e+02 1.12193923e+02 6.46e-07 4.54e-15 2.58e-09 178s
47 1.12193963e+02 1.12193928e+02 3.75e-07 2.83e-15 1.51e-09 182s
48 1.12193952e+02 1.12193931e+02 2.24e-07 1.65e-15 8.90e-10 187s
Barrier solved model in 48 iterations and 187.27 seconds (104.59 work units)
Optimal objective 1.12193952e+02
Crossover log...
139696 DPushes remaining with DInf 0.0000000e+00 188s
2723 DPushes remaining with DInf 0.0000000e+00 190s
0 DPushes remaining with DInf 0.0000000e+00 192s
554 PPushes remaining with PInf 2.8812486e-01 192s
0 PPushes remaining with PInf 2.6714164e-02 193s
Push phase complete: Pinf 2.6714164e-02, Dinf 1.4622707e-01 193s
Iteration Objective Primal Inf. Dual Inf. Time
116685 1.1219393e+02 0.000000e+00 1.462271e-01 193s
116874 1.1219393e+02 2.254370e+00 0.000000e+00 195s
117174 1.1219393e+02 4.223246e+01 0.000000e+00 200s
117454 1.1219393e+02 5.389088e+00 0.000000e+00 206s
117744 1.1219393e+02 3.938426e+01 0.000000e+00 212s
117884 1.1219393e+02 4.837359e+00 0.000000e+00 216s
118174 1.1219393e+02 6.655419e+00 0.000000e+00 222s
118304 1.1219393e+02 8.920969e+01 0.000000e+00 226s
118584 1.1219393e+02 2.106979e+01 0.000000e+00 232s
118714 1.1219393e+02 3.197743e+00 0.000000e+00 235s
118974 1.1219393e+02 2.024033e+01 0.000000e+00 242s
119084 1.1219393e+02 1.378090e+01 0.000000e+00 247s
119354 1.1219393e+02 1.757188e+01 0.000000e+00 253s
119484 1.1219393e+02 4.493260e+01 0.000000e+00 256s
119724 1.1219393e+02 1.174536e+02 0.000000e+00 263s
119844 1.1219393e+02 3.977736e+01 0.000000e+00 267s
119954 1.1219393e+02 3.102618e+01 0.000000e+00 271s
120064 1.1219393e+02 8.474358e+00 0.000000e+00 275s
120304 1.1219393e+02 5.400832e+00 0.000000e+00 284s
120414 1.1219393e+02 6.832231e+01 0.000000e+00 289s
120534 1.1219393e+02 8.862741e+00 0.000000e+00 292s
120644 1.1219393e+02 3.257071e+01 0.000000e+00 297s
120754 1.1219393e+02 4.985082e+01 0.000000e+00 301s
120864 1.1219393e+02 2.238688e+01 0.000000e+00 305s
121114 1.1219393e+02 2.705567e+01 0.000000e+00 312s
121224 1.1219393e+02 2.520392e+01 0.000000e+00 317s
121334 1.1219393e+02 9.999440e+00 0.000000e+00 321s
121444 1.1219393e+02 9.164429e+00 0.000000e+00 325s
121684 1.1219393e+02 5.715591e+00 0.000000e+00 334s
121804 1.1219393e+02 1.193015e+01 0.000000e+00 338s
121934 1.1219393e+02 4.972224e+00 0.000000e+00 342s
122064 1.1219393e+02 1.236829e+01 0.000000e+00 346s
122184 1.1219393e+02 2.970491e+01 0.000000e+00 351s
122324 1.1219393e+02 2.837768e+01 0.000000e+00 355s
122624 1.1219393e+02 2.193168e+01 0.000000e+00 364s
122824 1.1219393e+02 1.072201e+01 0.000000e+00 368s
122954 1.1219393e+02 1.284792e+01 0.000000e+00 372s
123094 1.1219393e+02 4.519194e+00 0.000000e+00 376s704883 2.9073335e+00 3.046197e+10 0.000000e+00 84473s
704965 2.9485023e+00 3.224106e+09 0.000000e+00 84485s
705047 3.0058571e+00 6.477419e+09 0.000000e+00 84497s
705129 3.0529927e+00 5.247282e+09 0.000000e+00 84509s
705211 3.0875018e+00 7.677923e+09 0.000000e+00 84522s
705293 3.1417447e+00 6.748626e+09 0.000000e+00 84534s
705375 3.2089049e+00 8.996742e+09 0.000000e+00 84546s
705457 3.2552455e+00 2.183582e+09 0.000000e+00 84560s
705539 3.3260879e+00 3.983228e+09 0.000000e+00 84574s
705621 3.3696096e+00 3.002335e+09 0.000000e+00 84586s
705703 3.4143499e+00 2.849120e+09 0.000000e+00 84599s
705785 3.4789302e+00 1.342194e+10 0.000000e+00 84612s
705867 3.5314868e+00 5.890742e+10 0.000000e+00 84625s
705949 3.5758631e+00 5.415225e+09 0.000000e+00 84637s
706031 3.6296801e+00 3.719260e+09 0.000000e+00 84650s
706113 3.6727097e+00 3.721645e+09 0.000000e+00 84662s
706195 3.7206641e+00 3.011163e+09 0.000000e+00 84674s
706277 3.7558270e+00 1.596684e+10 0.000000e+00 84685s
706359 3.7985990e+00 4.542603e+09 0.000000e+00 84697s
706441 3.8583435e+00 3.756144e+09 0.000000e+00 84710s
706523 4.0361014e+00 5.696311e+09 0.000000e+00 84722s
706605 4.0830197e+00 1.886730e+11 0.000000e+00 84734s
706687 4.1343751e+00 5.683547e+09 0.000000e+00 84747s
706769 4.1778727e+00 6.165751e+09 0.000000e+00 84760s
706851 4.7204975e+00 3.448853e+09 0.000000e+00 84773s
706933 4.9771278e+00 4.416990e+09 0.000000e+00 84785s
707015 5.2292974e+00 4.164623e+10 0.000000e+00 84798s
707097 5.2701552e+00 1.239990e+10 0.000000e+00 84810s
707179 5.3151071e+00 5.271186e+09 0.000000e+00 84823s
707261 5.3648799e+00 5.112130e+09 0.000000e+00 84835s
707343 5.4246979e+00 1.535598e+10 0.000000e+00 84848s
707425 5.5130759e+00 5.223042e+10 0.000000e+00 84861s
707507 5.5502431e+00 1.031650e+10 0.000000e+00 84874s
707589 5.6003449e+00 1.668026e+10 0.000000e+00 84887s
707671 5.6535677e+00 3.864215e+09 0.000000e+00 84898s
707753 5.6787237e+00 1.441807e+10 0.000000e+00 84910sObviously, my problem is prone to scalability and even casting the original MILP problem to an LP equivalent version, the problem still pertains. Could you please tell me how I should proceed to solve these two problems, namely the LP first and later the MILP?
It seems to me that playing with the parameters will not change significantly the performance of the optimizer. Or, it could work for a single value of ε, while for a different value of ε, I need again to select a new pair of parameters.
Could the automatic parameter tuning tool be considered? Unfortunately, I am using Matlab and If I recall correctly, this toolbox cannot be invoked from the Matlab environment.
Kind Regards,Antonis
0 -
Hi Antonis,
Since your model is a significant challenge for the simplex algorithms, I still think avoiding simplex is the way to go, i.e., Method=2, Crossover=0, NodeMethod=2. I do not think that tuning simplex parameters will significantly improve your situation.
The question is why do you get the same solution for each epsilon value? Where does the progress get stuck when using the parameters above? Does it hit the time limit or stop before that? Your additional parameters Presolve=2, DegenMoves=0, and MIPFocus=2 make sense here and can be beneficial.
Usually, there is one direction for the epsilon values (low to high, or high to low) where the solution of the previous iteration is feasible for the current one, but potentially can be improved because of the relaxed eps value.
As you already mentioned, the tuning tool is not available in Matlab but you can run it from the command line (grbtune) with your model exported in Matlab as an MPS file. Still, the runtimes are very long, so you would need a large compute cluster to test 100+ parameter settings.
Mario
0 -
Hello Mario,
I experimented a little bit with the constraints, and I realized that one constraint was the source of the problem for the LP. When I deactivated this constraint, I was able to solve the LP in less than 5 minutes.
I deactivated the same constraint for the MILP as well and again, when I solve the MILP for different values of epsilon, I also obtain the same solution. Altough the optimization deems that this solution is feasible, when I provide it as input to my simulator, then I get a message that I violate some equations in the simulator.
The behavior that I am expecting from the optimization is that while I increase the value of epsilon, the corresponding value of my objective function will decrease until it converges around a value. This means that after a point when I increase the value of epsilon, I will not experience any further reduction in the value of objective value.
Maybe there is something wrong going on with the branching, and I haven't expressed the dynamics in the optimization properly.
Do you have any other idea why I could be getting this behavior?
I attach a log from the MILP when setting epsilon=10
Set parameter Username
Set parameter Method to value 3
Set parameter BarHomogeneous to value 1
Set parameter CrossoverBasis to value 1
Set parameter MIPFocus to value 2
Set parameter Presolve to value 2
Academic license - for non-commercial use only - expires 2025-01-15
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 10.0 (19044.2))
CPU model: Intel(R) Core(TM) i9-10980XE CPU @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 18 physical cores, 36 logical processors, using up to 18 threads
Optimize a model with 10467386 rows, 61304216 columns and 37558905 nonzeros
Model fingerprint: 0x34fdcf2a
Variable types: 61303216 continuous, 1000 integer (1000 binary)
Coefficient statistics:
Matrix range [4e-03, 7e+01]
Objective range [8e-03, 8e-03]
Bounds range [1e+00, 3e+03]
RHS range [1e-02, 5e+03]
Presolve removed 63004 rows and 52859731 columns (presolve time = 5s) ...
Presolve removed 6734816 rows and 57505595 columns (presolve time = 10s) ...
Presolve removed 8177870 rows and 59261607 columns (presolve time = 15s) ...
Presolve removed 8233497 rows and 59294014 columns
Presolve time: 18.12s
Presolved: 2233889 rows, 2010202 columns, 10663726 nonzeros
Variable types: 2008028 continuous, 2174 integer (25 binary)
Root relaxation presolve removed 2071 rows and 1616 columns
Root relaxation presolved: 669564 rows, 637506 columns, 2962093 nonzeros
Concurrent LP optimizer: primal simplex, dual simplex, and barrier
Showing barrier log only...
Root barrier log...
Elapsed ordering time = 10s
Elapsed ordering time = 15s
Ordering time: 22.23s
Barrier statistics:
Dense cols : 18
AA' NZ : 4.663e+06
Factor NZ : 2.377e+08 (roughly 2.4 GB of memory)
Factor Ops : 8.163e+11 (roughly 1 second per iteration)
Threads : 15
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -4.60116967e+06 -5.00305391e+08 7.23e+04 1.87e-01 5.75e+03 150s
1 -1.82372639e+06 -4.08257762e+08 2.85e+04 1.76e-01 2.28e+03 153s
2 -5.37871013e+05 -2.18979865e+08 8.47e+03 2.93e-14 6.77e+02 156s
3 -1.37824596e+05 -8.93114191e+07 2.21e+03 4.06e-14 1.83e+02 160s
4 -4.69408034e+04 -3.31266220e+07 7.89e+02 5.02e-14 5.44e+01 165s
5 -1.55225856e+04 -9.73601567e+06 2.97e+02 3.94e-14 1.49e+01 169s
6 -4.05641450e+03 -3.60961181e+06 1.17e+02 7.69e-14 4.58e+00 174s
7 -1.30515951e+02 -1.53208638e+06 5.48e+01 5.33e-14 1.72e+00 179s
8 1.24625492e+03 -9.99173435e+05 3.27e+01 1.23e-13 1.02e+00 183s
9 1.87569665e+03 -5.07355059e+05 2.22e+01 3.72e-13 5.58e-01 187s
10 2.40389344e+03 -3.72505803e+05 1.25e+01 3.36e-13 3.61e-01 191s
11 2.56368127e+03 -3.00135566e+05 9.17e+00 1.99e-13 2.80e-01 199s
12 2.62198018e+03 -2.29297226e+05 7.81e+00 2.54e-13 2.19e-01 206s
13 2.70948892e+03 -1.74765804e+05 5.48e+00 3.41e-13 1.60e-01 215s
14 2.73610093e+03 -1.36125043e+05 4.73e+00 2.94e-13 1.27e-01 223s
15 2.75614471e+03 -1.09159828e+05 3.89e+00 4.50e-13 1.02e-01 232s
16 2.76162563e+03 -1.05117001e+05 3.53e+00 4.13e-13 9.58e-02 240s
17 2.76803684e+03 -7.25704922e+04 2.67e+00 2.83e-13 6.69e-02 248s
18 2.75851952e+03 -4.72568435e+04 2.03e+00 4.31e-13 4.50e-02 257s
19 2.72648929e+03 -3.03455920e+04 1.45e+00 9.32e-13 2.95e-02 266s
20 2.66552198e+03 -2.58956497e+04 1.07e+00 7.03e-13 2.41e-02 274s
21 2.63827245e+03 -2.29330412e+04 9.62e-01 6.30e-13 2.14e-02 283s
22 2.54922058e+03 -1.58752835e+04 7.19e-01 4.69e-13 1.53e-02 292s
23 2.46198572e+03 -1.49490023e+04 5.87e-01 4.47e-13 1.39e-02 301s
24 2.39065473e+03 -1.23688661e+04 5.05e-01 3.86e-13 1.17e-02 310s
25 2.25980492e+03 -9.17221754e+03 3.96e-01 2.93e-13 8.96e-03 319s
26 2.08291170e+03 -8.27891484e+03 2.99e-01 2.82e-13 7.81e-03 328s
27 1.97718735e+03 -7.08563931e+03 2.62e-01 3.59e-13 6.80e-03 337s
28 1.66620844e+03 -3.94583185e+03 1.78e-01 1.74e-13 4.20e-03 346s
29 1.33655554e+03 -2.70601395e+03 1.25e-01 3.38e-13 2.98e-03 354s
30 1.09688075e+03 -2.27489586e+03 9.28e-02 4.54e-13 2.43e-03 364s
31 8.88186559e+02 -1.90925388e+03 6.78e-02 3.41e-13 1.98e-03 374s
32 6.77886726e+02 -6.28800247e+02 4.54e-02 1.28e-12 9.48e-04 384s
33 5.40294178e+02 -4.15331106e+02 3.23e-02 9.31e-13 6.86e-04 393s
34 4.27406523e+02 -3.09985423e+02 2.22e-02 9.64e-13 5.19e-04 402s
35 3.33552255e+02 -2.07205940e+02 1.35e-02 1.38e-12 3.72e-04 411s
36 2.91861118e+02 -1.82374324e+01 1.02e-02 1.35e-12 2.18e-04 420s
37 2.40955407e+02 5.03769909e+01 6.56e-03 2.24e-13 1.34e-04 428s
38 2.05071575e+02 8.44590327e+01 4.12e-03 2.47e-13 8.41e-05 437s
39 1.86920682e+02 1.03766816e+02 2.93e-03 4.36e-13 5.80e-05 446s
40 1.77924171e+02 1.12007456e+02 2.34e-03 3.39e-13 4.59e-05 453s
41 1.67985135e+02 1.19995406e+02 1.71e-03 6.54e-13 3.33e-05 461s
42 1.60068118e+02 1.27305637e+02 1.21e-03 1.26e-12 2.28e-05 469s
43 1.53883514e+02 1.31992218e+02 8.22e-04 9.92e-13 1.52e-05 478s
44 1.49735091e+02 1.35118811e+02 5.63e-04 6.34e-13 1.01e-05 487s
45 1.47198747e+02 1.37113541e+02 4.05e-04 6.45e-13 7.02e-06 496s
46 1.44677257e+02 1.37885403e+02 2.46e-04 5.44e-13 4.67e-06 504s
47 1.43546727e+02 1.38638243e+02 1.76e-04 8.17e-13 3.36e-06 513s
48 1.42543497e+02 1.39563462e+02 1.13e-04 8.89e-13 2.05e-06 522s
49 1.41897662e+02 1.39972108e+02 7.34e-05 8.47e-13 1.32e-06 531s
50 1.41490866e+02 1.40189750e+02 4.82e-05 1.27e-12 8.85e-07 540s
51 1.41219168e+02 1.40418615e+02 3.12e-05 1.29e-12 5.44e-07 549s
52 1.41032767e+02 1.40536129e+02 1.94e-05 6.82e-13 3.36e-07 558s
53 1.40923357e+02 1.40622329e+02 1.25e-05 3.92e-13 2.03e-07 567s
54 1.40870565e+02 1.40675002e+02 9.09e-06 2.97e-13 1.32e-07 575s
55 1.40819335e+02 1.40698527e+02 5.78e-06 1.90e-13 8.13e-08 584s
56 1.40791139e+02 1.40715430e+02 3.94e-06 2.19e-13 5.09e-08 593s
57 1.40771099e+02 1.40722062e+02 2.60e-06 1.77e-13 3.28e-08 602s
58 1.40760492e+02 1.40726969e+02 1.89e-06 8.56e-14 2.24e-08 611s
59 1.40751529e+02 1.40729140e+02 1.28e-06 1.02e-13 1.49e-08 620s
60 1.40744575e+02 1.40730520e+02 7.95e-07 5.80e-14 9.30e-09 629s
61 1.40740548e+02 1.40731790e+02 5.17e-07 4.00e-14 5.78e-09 638s
62 1.40738363e+02 1.40732123e+02 3.64e-07 1.83e-14 4.10e-09 646s
63 1.40736700e+02 1.40732563e+02 2.45e-07 3.63e-14 2.70e-09 655s
64 1.40735670e+02 1.40732898e+02 1.71e-07 5.90e-14 1.80e-09 665s
65 1.40734965e+02 1.40733067e+02 1.19e-07 2.92e-14 1.23e-09 674s
66 1.40734544e+02 1.40733166e+02 8.80e-08 3.30e-14 8.91e-10 683s
67 1.40734202e+02 1.40733216e+02 6.26e-08 4.09e-14 6.35e-10 692s
68 1.40733965e+02 1.40733274e+02 4.49e-08 4.39e-14 4.44e-10 702s
69 1.40733783e+02 1.40733319e+02 3.12e-08 8.97e-14 2.97e-10 714s
70 1.40733647e+02 1.40733339e+02 4.29e-07 6.82e-14 1.97e-10 728s
71 1.40733564e+02 1.40733355e+02 3.01e-07 4.62e-14 1.35e-10 741s
72 1.40733522e+02 1.40733363e+02 2.65e-07 3.90e-14 1.03e-10 753s
73 1.40733506e+02 1.40733365e+02 2.38e-07 3.57e-14 9.14e-11 763s
74 1.40733499e+02 1.40733365e+02 2.25e-07 2.72e-14 8.66e-11 773s
75 1.40733472e+02 1.40733367e+02 2.59e-07 2.27e-14 6.84e-11 784s
76 1.40733452e+02 1.40733371e+02 2.36e-07 6.20e-14 5.30e-11 794s
77 1.40733444e+02 1.40733372e+02 2.59e-07 5.32e-14 4.75e-11 804s
78 1.40733433e+02 1.40733373e+02 2.13e-07 4.24e-14 3.93e-11 814s
79 1.40733421e+02 1.40733374e+02 1.72e-07 2.19e-14 3.08e-11 824s
80 1.40733414e+02 1.40733375e+02 1.45e-07 2.61e-14 2.59e-11 834s
Barrier solved model in 80 iterations and 833.76 seconds (454.25 work units)
Optimal objective 1.40733414e+02
Root crossover log...
Warning: 1 variables dropped from basis
Warning: 1 variables dropped from basis
Restart crossover...
465564 DPushes remaining with DInf 3.2886588e-01 837s
31539 DPushes remaining with DInf 2.4721683e-01 840s
14696 DPushes remaining with DInf 2.4141226e-01 845s
11336 DPushes remaining with DInf 2.4141226e-01 850s
7976 DPushes remaining with DInf 2.4141226e-01 855s
5035 DPushes remaining with DInf 2.4141226e-01 860s
2516 DPushes remaining with DInf 2.4141226e-01 866s
1256 DPushes remaining with DInf 2.4086236e-01 871s
0 DPushes remaining with DInf 2.4086236e-01 876s
740 PPushes remaining with PInf 1.4109479e-03 876s
0 PPushes remaining with PInf 2.5412004e-02 878s
Push phase complete: Pinf 2.5412004e-02, Dinf 7.3294286e+00 878s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
263186 1.4073444e+02 0.000000e+00 7.329429e+00 878s
263483 1.4073338e+02 0.000000e+00 0.000000e+00 880s
Solved with barrier
263483 1.4073338e+02 0.000000e+00 0.000000e+00 882s
Root relaxation: objective 1.407334e+02, 263483 iterations, 765.34 seconds (394.07 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 140.73338 0 1 - 140.73338 - - 895s
H 0 0 140.7333794 140.73338 0.00% - 900s
Explored 1 nodes (267145 simplex iterations) in 1418.30 seconds (476.49 work units)
Thread count was 18 (of 36 available processors)
Solution count 2: 140.733 140.733
Optimal solution found (tolerance 1.00e-04)
Warning: max constraint violation (2.9022e-06) exceeds tolerance
Warning: max bound violation (1.2568e-06) exceeds tolerance
Best objective 1.407333794148e+02, best bound 1.407333794148e+02, gap 0.0000%
Elapsed time is 1457.046333 seconds.Thank you in advance.
Kind Regards,
Antonis
0 -
As you can see at the end of the solver output, the solution has slight violations in the order of 1e-6. Does your simulator account for tolerances, especially when checking equalities?
If you obtain the same solutions for increasing epsilon values, then you are probably already at the point where you cannot improve anymore. Can you construct a counter-example, i.e., a better solution for a higher eps value that the solver cannot find?
Sometimes it helps to write out the model as a readable file with model.write("model.lp"), then you can check whether your simulator and your model consider the same constraints. For example, if the simulator says that the solution is not feasible, what about the corresponding constraint in the model?
0 -
Dear Mario,
the difficult part with my simulator is that I cannot find the optimal value of the objective function of interest, since the combinations increase exponentially as I increase the value of epsilon. Just as an indication, in my case, I have 5^25 candidate combinations. What I want is to find a high-quality solution that can be close to the optimal one through the optimization framework, without having to analytically compute each possible combination in a brute force format.
For example, when ε=0, I get only 1 possible combination.
When ε=10, I get 26 combinations and so on and so forth.
Regarding what you said, I have made some comparisons between the solution obtained from the optimization.
1. For ε=0, the solution (derived pair of actual school start times - this is reflected in my binary variables) perfectly coincides between the simulation and the optimization and is FEASIBLE for both of them.2. For ε=10, the solution obtained from the optimization is FEASIBLE and when inserted to the simulator I get an INFEASIBILITY.
I get a similar behaviour for different values of ε. However, as I stated before, I cannot easily construct a counter-example in the simulator, because it would entail the analytic evaluation of a very large number of combinations.
What would you suggest I try to identify why the optimization gives a solution that is later infeasible in the simulator?
I also did what you stated in terms of the readable file and both the optimization and the simulation consider the same constraints.
Thank you.Antonis
0 -
Hi Antonis,
I think you really need to dig deeper into case 2, where the solver returns a feasible solution, and the simulator says this is infeasible. I am not aware of the details of your simulator, but can you adapt it to give you more information on why the solution is infeasible? Is it just a numerical issue that the simulator realizes that some constraints are not satisfied by a very small amount?
The solver will give you a solution that satisfies all constraints and bounds in the model (subject to tolerances or small violations). If the simulator detects infeasibility, not just by a small amount, then some constraints might be missing in the model.
It often helps to reduce the problem instance as much as possible in terms of size, then debugging is usually easier.
0 -
Hi Mario,
I dug into case 2, and I also considered many other cases considering different values of epsilon as input to the solver, and I realized that there were some mistakes in terms of the simulation horizon. At this point, I solve a separate MILP for the following values, ε=0,10,20,...50. The solution I obtain from the optimization is later fed to the simulator to check if I get feasibility issues. I do not face a problem up to ε=40. However, when ε=50, the solution I get from optimization leads to Infeasibility in the simulator.
I checked why I obtained an infeasibility in the simulator, and it is not a numerical issue. Let us say that I consider a simulation horizon of K=360 time steps in the simulation and the optimization alike. When I run the simulation (for ε=50) considering as input the solution from the optimization, a specific constraint is violated at the time step, k=83. The strange thing is that for the previous values of epsilon, I didn't face any problems, and none of the constraints of the simulation was violated. However, I am still trying to figure out what is going wrong with the current value of epsilon.
Any idea why this might be happening? Do I need to play with the parameter tuning part, or this issue does not have to do with that?
Thank you.
Antonis0 -
Hi Mario,
I am not sure if you read my response, but do you have any suggestions related to this issue?
Antonis
0 -
I do not think that this is related to solver parameters.
You said that you considered all time steps both in your simulator and in your model. If your simulator says that the solution is infeasible for k=83, then how are those values different from the solution values for k=83 in the solver's result?
0 -
Mario,
maybe I did not express my concern properly.
The original optimization problem is a Mixed Integer Nonlinear Program (MINLP). Therefore, the dynamics associated with the traffic simulator have a nonlinear and nonconvex nature. As these problems are difficult to handle with nonlinear optimization solvers, we have pursued a relaxation procedure to approximate each nonconvex and nonlinear constraint of the original MINLP with a block of linear constraints. In this sense, we obtain a Mixed Integer Linear Program (MILP) in which the ε-constraint technique is employed. This is why I mentioned the notion of ε-constraint in the conversation.
So, the conversation that has already taken place in this post concerns the MILP, after a relaxation procedure has been performed. Therefore, the solution I obtain from the MILP is an approximate one with respect to the original problem. This is why the solution obtained from the MILP violates a specific constraint when being fed to the nonlinear and nonconvex simulator.0 -
Hello there,
does anybody have an idea why I get such a behavior?
Thank you.
Antonis
0 -
Well, this is indeed an important information. If your MILP is just an approximation of your original MINLP, then it is not surprising that there are MILP solutions that violate constraints of your original model. The solver just does not know the original MINLP.
There are several options:
- You improve your MILP approximation of the original MINLP.
- You use lazy constraints in a callback to add further constraints to the MILP dynamically, or just reject a solution that you checked in a callback (probably with your simulator) and that turned out to be infeasible.
- You model and solve the original MINLP with Gurobi. The newest v11 includes an exact global MINLP solver.
0 -
Dear Mario,
I really appreciate these suggestions. I will have a look and I hope that some of them might be able to resolve the current problem I face.
Thank you.
Antonis
0
Please sign in to leave a comment.
Comments
15 comments