Solver behaviour when giving fixed variable a start value
AnsweredDear Gurobi staffers,
my model is a capacity expansion of a power plant to meet a given electrical demand for an entire year (8760 timesteps). In general I model existing components (only variable costs) and new component options (also investment costs). Lets say I have two options. Option 1 already exists option 2 is an investment option.
For each option I use an integer variable to modell its existence. Integer because for each option multiple blocks might be modelled. (code examples in Pseudo-Julia/JuMP-code)
# Variable declaration:
@variable(model, I_1>=0,Int)
@variable(model, I_2>=0,Int)
Lets say option 1 consists of 2 blocks and option 2 should be less than 10 blocks it gives. Due to easier programming I add these as constraints, rather than fixing the variable upon declaration( but from my point of view it shouldn't make any difference)
@constraint(model, I_1 == 2)
@constraint(model, I_2 <= 10)
To aid the solver and assuming that it is cheaper to first use the already existing components rather than new ones, I provide start values for existence Variables:
set_start_value(I_1, 2)
set_start_value(I_2, 0)
which then Gurobi uses to process the MIP start and improved model performance significantly. The start_value for I_1 was actually never really intended, but as my actual model is more complicated and uses variable-sets and arrays, it was easier to simple set start values for all existence variables then rather the new ones.
So far so good and everything works as expected. Now comes what I did not expect:
When I run my model for past years, I do not give the model any investment options, because all capacities are known and fixed. However, as i use the same code structure, the start_values are set anyway, however all variables are already fixed to the same start value using the equality constraints anyway. The code would now look like this:
# Variable declaration:
@variable(model, I_1>=0,Int)
@variable(model, I_2>=0,Int)
@constraint(model, I_1 == 2)
@constraint(model, I_2 == 3)
set_start_value(I_1, 2)
set_start_value(I_2, 3)
I had assumend that providing start_values for fixed variables would not influence the solver behavior, but it does. I ran the model two times it completely identical settings (same computer, solver settings and model). The only difference is that in the first run I used the option set_start_values and I did not use start_values in the second run.
Here is the log file of the run when providing the start values:
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 16 physical cores, 32 logical processors, using up to 2 threads
Optimize a model with 3661558 rows, 1927245 columns and 14409595 nonzeros
Model fingerprint: 0x6292d718
Variable types: 1454192 continuous, 473053 integer (78844 binary)
Coefficient statistics:
Matrix range (1e-04, 3e+03)
Objective range (1e+00, 1e+00)
Bounds range (0e+00, 0e+00)
RHS range (1e+00, 5e+06)
Warning: Completing partial solution with 473040 unfixed non-continuous variables out of 473053
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 5s
[removed a lot of MIP start lines to shorten the log]
Loaded user MIP start with objective 1.24075e+06
Processed MIP start in 1409.45 seconds (1068.25 work units)
Presolve removed 1200169 rows and 1252725 columns (presolve time = 5s) ...
Presolve removed 2542053 rows and 1339089 columns (presolve time = 10s) ...
Presolve removed 2867602 rows and 1349287 columns (presolve time = 15s) ...
Presolve removed 2867602 rows and 1350494 columns (presolve time = 21s) ...
Presolve removed 2867602 rows and 1350494 columns (presolve time = 25s) ...
Presolve removed 2867602 rows and 1350494 columns
Presolve time: 29.67s
Presolved: 793956 rows, 576751 columns, 2632070 nonzeros
Variable types: 340231 continuous, 236520 integer (131400 binary)
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Root relaxation presolved: 793956 rows, 576751 columns, 2632070 nonzeros
Root barrier log...
Ordering time: 0.39s
Barrier statistics:
AA' NZ : 5.305e+06
Factor NZ : 1.527e+07 (roughly 700 MB of memory)
Factor Ops : 6.143e+08 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -7.62927743e+06 -1.71132632e+08 1.08e+03 1.19e+00 1.32e+03 1447s
1 1.97672504e+06 -1.50404396e+08 2.39e+02 1.24e+00 3.07e+02 1448s
2 3.48213917e+06 -5.32976621e+07 3.16e+01 3.36e-03 5.14e+01 1448s
3 3.26102700e+06 -1.06538645e+07 1.48e+00 8.39e-14 8.40e+00 1449s
4 2.33909588e+06 -5.10697324e+05 1.79e-01 3.91e-14 1.65e+00 1451s
5 1.72297028e+06 4.20769277e+05 5.25e-02 1.60e-14 7.49e-01 1451s
6 1.44942959e+06 8.32190087e+05 1.85e-02 7.11e-15 3.55e-01 1452s
7 1.33821976e+06 9.95055332e+05 8.33e-03 5.33e-15 1.97e-01 1453s
8 1.28877113e+06 1.08774622e+06 4.30e-03 3.55e-15 1.15e-01 1454s
9 1.26934444e+06 1.14650793e+06 2.86e-03 5.33e-15 7.05e-02 1454s
10 1.24263065e+06 1.17876179e+06 1.07e-03 3.55e-15 3.66e-02 1455s
11 1.23031259e+06 1.19952299e+06 3.87e-04 3.55e-15 1.77e-02 1456s
12 1.22576674e+06 1.20907925e+06 1.80e-04 3.55e-15 9.57e-03 1457s
13 1.22402199e+06 1.21321522e+06 1.11e-04 5.33e-15 6.20e-03 1458s
14 1.22282193e+06 1.21658397e+06 6.76e-05 5.33e-15 3.58e-03 1459s
15 1.22157807e+06 1.21813298e+06 2.51e-05 5.33e-15 1.98e-03 1460s
16 1.22116919e+06 1.21942861e+06 1.27e-05 5.33e-15 9.98e-04 1460s
17 1.22093580e+06 1.21992414e+06 6.20e-06 3.55e-15 5.80e-04 1461s
18 1.22080466e+06 1.22024207e+06 2.74e-06 5.33e-15 3.23e-04 1462s
19 1.22072742e+06 1.22043680e+06 9.12e-07 5.33e-15 1.67e-04 1463s
20 1.22070579e+06 1.22057487e+06 4.16e-07 5.33e-15 7.50e-05 1465s
21 1.22069845e+06 1.22061181e+06 2.69e-07 3.55e-15 4.97e-05 1465s
Barrier performed 21 iterations in 1465.67 seconds (1101.81 work units)
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Root relaxation: objective 1.220683e+06, 264354 iterations, 25.67 seconds (24.75 work units)
Total elapsed time = 1470.00s
Total elapsed time = 1475.04s
Total elapsed time = 1483.40s
Total elapsed time = 1487.92s
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1220682.80 0 16968 1240754.01 1220682.80 1.62% - 1503s
0 0 1230485.18 0 21429 1240754.01 1230485.18 0.83% - 1636s
0 0 1232863.09 0 18121 1240754.01 1232863.09 0.64% - 1710s
0 0 1233432.82 0 17866 1240754.01 1233432.82 0.59% - 1736s
0 0 1233437.88 0 17906 1240754.01 1233437.88 0.59% - 1741s
0 0 1233437.94 0 17912 1240754.01 1233437.94 0.59% - 1742s
0 0 1236167.59 0 20597 1240754.01 1236167.59 0.37% - 1912s
H 0 0 1240748.3080 1236167.59 0.37% - 1917s
0 0 1237007.40 0 18870 1240748.31 1237007.40 0.30% - 1944s
0 0 1237370.64 0 19264 1240748.31 1237370.64 0.27% - 1969s
0 0 1237392.93 0 19454 1240748.31 1237392.93 0.27% - 1972s
0 0 1237394.83 0 19451 1240748.31 1237394.83 0.27% - 1974s
0 0 1239125.19 0 16676 1240748.31 1239125.19 0.13% - 2125s
0 0 1239464.95 0 14258 1240748.31 1239464.95 0.10% - 2140s
0 0 1239555.02 0 14003 1240748.31 1239555.02 0.10% - 2146s
0 0 1239562.00 0 14038 1240748.31 1239562.00 0.10% - 2148s
0 0 1239563.15 0 14061 1240748.31 1239563.15 0.10% - 2150s
0 0 1240160.50 0 10324 1240748.31 1240160.50 0.05% - 2212s
0 0 1240262.90 0 8547 1240748.31 1240262.90 0.04% - 2222s
0 0 1240273.09 0 8715 1240748.31 1240273.09 0.04% - 2227s
0 0 1240274.91 0 8562 1240748.31 1240274.91 0.04% - 2231s
0 0 1240422.86 0 5423 1240748.31 1240422.86 0.03% - 2284s
0 0 1240441.66 0 4949 1240748.31 1240441.66 0.02% - 2293s
0 0 1240443.64 0 5123 1240748.31 1240443.64 0.02% - 2298s
0 0 1240476.38 0 3340 1240748.31 1240476.38 0.02% - 2338s
0 0 1240480.23 0 3283 1240748.31 1240480.23 0.02% - 2349s
0 0 1240491.32 0 3186 1240748.31 1240491.32 0.02% - 2388s
0 0 1240493.26 0 2831 1240748.31 1240493.26 0.02% - 2399s
0 0 1240497.35 0 2822 1240748.31 1240497.35 0.02% - 2434s
H 0 0 1240744.0081 1240497.35 0.02% - 2441s
0 0 1240498.44 0 2692 1240744.01 1240498.44 0.02% - 2443s
0 0 1240500.99 0 2482 1240744.01 1240500.99 0.02% - 2480s
0 0 1240501.56 0 2270 1240744.01 1240501.56 0.02% - 2485s
0 0 1240503.31 0 2287 1240744.01 1240503.31 0.02% - 2510s
0 0 1240503.31 0 2287 1240744.01 1240503.31 0.02% - 2519s
H 0 0 1240671.8692 1240503.31 0.01% - 2536s
H 0 0 1240648.5164 1240503.31 0.01% - 2745s
H 0 0 1240641.9222 1240503.31 0.01% - 2749s
H 0 0 1240626.5463 1240503.31 0.01% - 2753s
Cutting planes:
Gomory: 315
Lift-and-project: 22
MIR: 33328
StrongCG: 14
Flow cover: 13793
Relax-and-lift: 2136
Explored 1 nodes (489966 simplex iterations) in 2753.66 seconds (2264.25 work units)
Thread count was 2 (of 32 available processors)
Solution count 10: 1.24063e+06 1.24064e+06 1.24067e+06 ... 1.24083e+06
Optimal solution found (tolerance 1.00e-04)
Best objective 1.240626546281e+06, best bound 1.240503306683e+06, gap 0.0099%
User-callback calls 171405, time in user-callback 0.40 sec
And here when no start values were provided
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 16 physical cores, 32 logical processors, using up to 2 threads
Optimize a model with 3661558 rows, 1927245 columns and 14409595 nonzeros
Model fingerprint: 0xc598e863
Variable types: 1454192 continuous, 473053 integer (78844 binary)
Coefficient statistics:
Matrix range (1e-04, 3e+03)
Objective range (1e+00, 1e+00)
Bounds range (0e+00, 0e+00)
RHS range (1e+00, 5e+06)
Presolve removed 2461465 rows and 1258501 columns (presolve time = 5s) ...
Presolve removed 2858842 rows and 1349287 columns (presolve time = 10s) ...
Presolve removed 2867602 rows and 1350494 columns (presolve time = 15s) ...
Presolve removed 2867602 rows and 1350494 columns (presolve time = 20s) ...
Presolve removed 2867602 rows and 1350494 columns
Presolve time: 22.00s
Presolved: 793956 rows, 576751 columns, 2632070 nonzeros
Variable types: 340231 continuous, 236520 integer (131400 binary)
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Root relaxation presolved: 793956 rows, 576751 columns, 2632070 nonzeros
Root barrier log...
Ordering time: 0.19s
Barrier statistics:
AA' NZ : 5.305e+06
Factor NZ : 1.527e+07 (roughly 700 MB of memory)
Factor Ops : 6.143e+08 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -7.62927743e+06 -1.71132632e+08 1.08e+03 1.19e+00 1.32e+03 31s
1 1.97672504e+06 -1.50404396e+08 2.39e+02 1.24e+00 3.07e+02 31s
2 3.48213917e+06 -5.32976621e+07 3.16e+01 3.36e-03 5.14e+01 32s
3 3.26102700e+06 -1.06538645e+07 1.48e+00 7.46e-14 8.40e+00 33s
4 2.33909588e+06 -5.10697324e+05 1.79e-01 3.55e-14 1.65e+00 34s
5 1.72297028e+06 4.20769277e+05 5.25e-02 1.60e-14 7.49e-01 34s
6 1.44942959e+06 8.32190087e+05 1.85e-02 8.88e-15 3.55e-01 35s
7 1.33821976e+06 9.95055332e+05 8.33e-03 5.33e-15 1.97e-01 35s
8 1.28877113e+06 1.08774622e+06 4.30e-03 5.33e-15 1.15e-01 36s
9 1.26934444e+06 1.14650793e+06 2.86e-03 5.33e-15 7.05e-02 36s
10 1.24263065e+06 1.17876179e+06 1.07e-03 5.33e-15 3.66e-02 37s
11 1.23031259e+06 1.19952299e+06 3.87e-04 3.55e-15 1.77e-02 38s
12 1.22576674e+06 1.20907925e+06 1.80e-04 3.55e-15 9.57e-03 38s
13 1.22402199e+06 1.21321522e+06 1.11e-04 3.55e-15 6.20e-03 39s
14 1.22282193e+06 1.21658397e+06 6.76e-05 3.55e-15 3.58e-03 40s
15 1.22157807e+06 1.21813298e+06 2.51e-05 3.55e-15 1.98e-03 40s
16 1.22116919e+06 1.21942861e+06 1.27e-05 5.33e-15 9.98e-04 41s
17 1.22093580e+06 1.21992414e+06 6.20e-06 3.55e-15 5.80e-04 41s
18 1.22080466e+06 1.22024207e+06 2.74e-06 5.33e-15 3.23e-04 42s
19 1.22072742e+06 1.22043680e+06 9.12e-07 5.33e-15 1.67e-04 43s
20 1.22070579e+06 1.22057487e+06 4.16e-07 3.55e-15 7.50e-05 44s
21 1.22069845e+06 1.22061181e+06 2.69e-07 3.55e-15 4.97e-05 44s
22 1.22069109e+06 1.22064121e+06 1.14e-07 3.55e-15 2.86e-05 45s
23 1.22068613e+06 1.22067423e+06 3.93e-08 7.11e-15 6.82e-06 46s
24 1.22068333e+06 1.22067905e+06 1.25e-08 5.33e-15 2.45e-06 46s
Barrier performed 24 iterations in 46.41 seconds (37.02 work units)
Barrier solve interrupted - model solved by another algorithm
Solved with dual simplex
Root relaxation: objective 1.220683e+06, 264354 iterations, 19.13 seconds (24.75 work units)
Total elapsed time = 50.17s
Total elapsed time = 61.61s
Total elapsed time = 65.05s
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1220682.80 0 16968 - 1220682.80 - - 76s
0 0 1229914.40 0 21448 - 1229914.40 - - 184s
0 0 1232886.23 0 18525 - 1232886.23 - - 245s
0 0 1233423.05 0 17983 - 1233423.05 - - 266s
0 0 1233437.91 0 17928 - 1233437.91 - - 268s
0 0 1233437.94 0 17928 - 1233437.94 - - 269s
0 0 1236131.66 0 22082 - 1236131.66 - - 408s
0 0 1237191.82 0 20493 - 1237191.82 - - 435s
0 0 1237377.85 0 19287 - 1237377.85 - - 445s
0 0 1237385.94 0 19239 - 1237385.94 - - 447s
0 0 1237386.82 0 19442 - 1237386.82 - - 449s
0 0 1239073.15 0 17823 - 1239073.15 - - 582s
0 0 1239497.17 0 15147 - 1239497.17 - - 592s
0 0 1239556.21 0 13772 - 1239556.21 - - 597s
0 0 1239561.04 0 13933 - 1239561.04 - - 599s
0 0 1239561.73 0 14050 - 1239561.73 - - 601s
0 0 1240135.46 0 11342 - 1240135.46 - - 656s
0 0 1240247.69 0 8657 - 1240247.69 - - 664s
0 0 1240262.73 0 8817 - 1240262.73 - - 666s
0 0 1240265.63 0 8876 - 1240265.63 - - 668s
0 0 1240419.12 0 5778 - 1240419.12 - - 720s
0 0 1240433.73 0 4897 - 1240433.73 - - 725s
0 0 1240435.54 0 4937 - 1240435.54 - - 727s
0 0 1240469.40 0 3599 - 1240469.40 - - 767s
0 0 1240473.60 0 3253 - 1240473.60 - - 771s
0 0 1240488.75 0 3005 - 1240488.75 - - 794s
0 0 1240490.28 0 3037 - 1240490.28 - - 800s
0 0 1240498.71 0 2862 - 1240498.71 - - 828s
0 0 1240499.93 0 2789 - 1240499.93 - - 834s
0 0 1240503.18 0 2381 - 1240503.18 - - 853s
0 0 1240503.59 0 2504 - 1240503.59 - - 858s
0 0 1240506.41 0 2492 - 1240506.41 - - 879s
0 0 1240506.41 0 2492 - 1240506.41 - - 896s
0 2 1240506.41 0 2492 - 1240506.41 - - 945s
3 6 1240508.16 2 2484 - 1240507.67 - 272 951s
9 22 1240511.26 5 2151 - 1240510.52 - 245 958s
21 68 1240511.72 5 2101 - 1240510.76 - 143 967s
67 114 1240514.35 3 2255 - 1240511.11 - 72.3 973s
113 160 1240511.78 4 2269 - 1240511.14 - 60.1 981s
159 206 1240513.36 6 2185 - 1240511.26 - 54.0 989s
205 252 1240511.88 7 2110 - 1240511.28 - 52.0 996s
251 298 1240511.79 7 2071 - 1240511.45 - 48.6 1003s
297 344 1240513.98 9 2065 - 1240511.75 - 47.7 1009s
343 385 1240512.57 9 2080 - 1240511.78 - 45.3 1016s
384 427 1240512.11 7 2116 - 1240511.81 - 43.4 1023s
426 471 1240512.12 8 2124 - 1240511.83 - 42.1 1030s
470 512 1240512.46 9 2074 - 1240511.83 - 41.2 1037s
Resetting heuristic parameters to focus on improving solution
(using Heuristics=0.5 and RINS=10)...
511 536 1240520.35 26 1695 - 1240511.87 - 40.0 1045s
535 582 1240525.44 29 1774 - 1240511.87 - 39.3 1061s
581 623 1240535.23 41 1354 - 1240511.87 - 37.5 1076s
622 668 1240545.34 51 1186 - 1240511.87 - 35.9 1091s
667 710 1240564.94 64 1115 - 1240511.87 - 34.3 1106s
709 753 1240587.17 72 1036 - 1240511.87 - 33.1 1122s
753 754 1240522.06 26 2492 - 1240511.87 - 32.2 1131s
755 755 1240521.24 29 16968 - 1240511.87 - 32.1 1211s
756 756 1240519.15 21 21385 - 1240511.87 - 32.1 1274s
757 757 1240513.24 13 23156 - 1240511.87 - 32.0 1350s
758 757 1240518.65 23 20949 - 1240511.87 - 32.0 1401s
759 758 1240519.56 24 17248 - 1240511.87 - 31.9 1429s
760 759 1240530.51 43 10746 - 1240511.87 - 31.9 1446s
761 759 1240514.07 12 3546 - 1240511.87 - 31.8 1451s
763 761 1240590.79 79 2579 - 1240511.87 - 31.8 1456s
765 762 1240519.98 22 2524 - 1240511.87 - 31.7 1460s
767 763 1240519.89 21 2393 - 1240511.87 - 31.6 1503s
768 764 1240516.23 15 2363 - 1240511.87 - 31.6 1505s
769 765 1240512.23 9 2333 - 1240511.87 - 31.5 1530s
770 765 1240516.18 11 2196 - 1240514.79 - 31.5 1555s
772 767 1240519.46 22 2370 - 1240515.02 - 31.4 1562s
773 767 1240551.71 72 2029 - 1240517.45 - 31.3 1577s
774 768 1240519.68 19 2017 - 1240517.56 - 31.3 1582s
775 769 1240524.24 23 1979 - 1240518.30 - 31.3 1598s
776 769 1240527.16 36 1989 - 1240518.39 - 31.2 1603s
777 770 1240518.67 22 1985 - 1240518.67 - 31.2 1619s
778 771 1240544.96 55 2002 - 1240518.69 - 31.1 1624s
779 771 1240518.92 15 1987 - 1240518.92 - 31.1 1640s
781 773 1240519.00 20 1952 - 1240519.00 - 31.0 1659s
782 773 1240519.02 10 1974 - 1240519.02 - 31.0 1664s
783 774 1240520.93 23 1972 - 1240519.04 - 30.9 1679s
784 775 1240522.45 26 1972 - 1240519.04 - 30.9 1683s
785 775 1240519.04 13 1972 - 1240519.04 - 30.9 1690s
H 785 735 2736985.0980 1240519.05 54.7% 30.9 1784s
H 785 698 1240617.8008 1240519.05 0.01% 30.9 1796s
Cutting planes:
Gomory: 247
Lift-and-project: 68
Projected implied bound: 14
MIR: 24262
StrongCG: 6
Flow cover: 9084
RLT: 13
Relax-and-lift: 1794
Explored 785 nodes (899093 simplex iterations) in 1796.53 seconds (2090.51 work units)
Thread count was 2 (of 32 available processors)
Solution count 2: 1.24062e+06 2.73699e+06
Optimal solution found (tolerance 1.00e-04)
Warning: max constraint violation (7.8263e-06) exceeds tolerance
Warning: max bound violation (6.7371e-06) exceeds tolerance
Best objective 1.240617800791e+06, best bound 1.240519046854e+06, gap 0.0080%
User-callback calls 206724, time in user-callback 0.27 sec
Providing the start values leads to a faster first solution (after 1500 s instead of 1700 s in the second case), but takes longer to get to the desired MIP-gap. Additionally the run without start values leads to numeric warnings, while the one with start values does not give any warnings.
How can these differences be explained? Is a different solver strategy used to solve the MIPstart before the presolve then after? Is the presolve influenced by the result of the MIPstart? After presolve the model in the first run is as tight as the model in the second.
-
Dear Sebastian,
The start solution you provide triggers a "initial solution phase". As can be seen from the two logs, this phase is triggered before the presolve step. What happens in your case, is that completing and computing an initial solution takes a significant amount of time and the found solution does not improve the presolve step (both presolved models are of same size and #nonzeros). Now going into the B&B tree, one run has an initial solution and the other does not. If we cross out the time required for the "initial solution phase" then the run with a starting solution takes ~1200 seconds while the second run without an initial solution takes ~1700 seconds. The downside in this case is that completing the partial solution takes a significant amount of time and the performance tradeoff is bad. To not alter your code too much, you could try experimenting with the StartNodeLimit and SubMIPNodes parameters to limit the time spent to complete a partial MIP start.
Best regards,
Jaromił1
Please sign in to leave a comment.
Comments
1 comment