Using Gurobi heuristic parameter to achieve a feasible solution
AnsweredDear support team,
I'm working on an optimization problem (MIP) which in the medium/large scale takes too much time to solve optimality. Then I tried to use Gurobi heuristic parameter to invoke a feasible solution. I'm working on the model with 2452 rows, 2549 columns and 12006 nonzeros as an instance.
While I run the model with the default parameters of the solver, it is solved in the 800 Sec. In the second case, I'm using "(GRB.IntParam.NoRelHeuristic, 1)" and solving the problem again. In this case, it takes about 1500 Sec. The log file is as follows:
Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (win64)
Optimize a model with 2452 rows, 2549 columns and 12006 nonzeros
Model fingerprint: 0xb4a37fd2
Variable types: 49 continuous, 2500 integer (2500 binary)
Coefficient statistics:
Matrix range [1e+00, 5e+01]
Objective range [4e01, 1e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 5e+01]
Presolve removed 0 rows and 50 columns
Presolve time: 0.07s
Presolved: 2452 rows, 2499 columns, 11956 nonzeros
Variable types: 49 continuous, 2450 integer (2450 binary)
Starting NoRel heuristic
NoRel heuristic complete
Root relaxation: objective 4.525617e+02, 288 iterations, 0.03 seconds
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
0 0 452.56171 0 79  452.56171   1s
0 0 520.19773 0 103  520.19773   1s
0 0 526.29345 0 96  526.29345   1s
0 0 529.80279 0 96  529.80279   1s
0 0 529.80279 0 96  529.80279   1s
0 0 529.80279 0 96  529.80279   1s
0 0 529.80279 0 96  529.80279   1s
0 0 529.80279 0 96  529.80279   1s
0 0 529.80279 0 96  529.80279   2s
H 0 0 2441.5172916 529.80279 78.3%  3s
H 0 0 2159.0333221 529.80279 75.5%  4s
0 2 529.80279 0 96 2159.03332 529.80279 75.5%  4s
15 17 532.07543 14 57 2159.03332 530.01676 75.5% 21.5 5s
H 155 152 851.8794522 530.01676 37.8% 11.9 10s
.
.
.
H102505 4751 557.1377144 555.21955 0.34% 19.6 1409s
102627 4725 556.86462 149 28 557.13771 555.23020 0.34% 19.6 1410s
103359 4399 cutoff 134 557.13771 555.33086 0.32% 19.6 1415s
104240 3979 cutoff 155 557.13771 555.47495 0.30% 19.5 1420s
105118 3562 556.41376 135 6 557.13771 555.60947 0.27% 19.5 1425s
105892 3123 cutoff 152 557.13771 555.74680 0.25% 19.4 1430s
106710 2678 cutoff 137 557.13771 555.89232 0.22% 19.4 1435s
107593 2122 cutoff 147 557.13771 556.07536 0.19% 19.3 1440s
108385 1606 556.38328 144 16 557.13771 556.27035 0.16% 19.2 1445s
109402 817 cutoff 140 557.13771 556.62776 0.09% 19.2 1450s
Cutting planes:
Learned: 39
Gomory: 35
Cover: 150
MIR: 25
Flow cover: 264
Inf proof: 98
Zero half: 27
Explored 110269 nodes (2104458 simplex iterations) in 1454.30 seconds
Thread count was 1 (of 1 available processors)
Solution count 10: 557.138 557.422 563.814 ... 592.227
Optimal solution found (tolerance 1.00e04)
Best objective 5.571377216268e+02, best bound 5.570821525287e+02, gap 0.0100%
Optimal objective: 557.1377216268239
I'm wondering if,
1) Is there any way to speed up the solving time using Gurobi heuristic parameters?
2) Can I solve the model by using Gurobi heuristic setting to achieve a feasible solution without starting the branch and cut alg. ?
Regards
Abbas

Hi Abbas,
I would run some experiments with different cut settings to see whether a stronger LP relaxation can help to find good solutions. Apart from that, heuristics are often quite unpredictable in their performance, but if you want to invest more time in heuristics, you can increase the Heuristics parameter.
If you have some computing resources available, you might also want to try running the automatic tuning tool, maybe with relaxed termination criteria to speed up the process.
Cheers,
Matthias0
Please sign in to leave a comment.
Comments
1 comment