Gurobi's solution time far exceeds the set time.

Hi,

I used matlab+yalmip+gurobi to solve mixed integer nonlinear programming, and the results are as follows:

Academic license - for non-commercial use only - expires 2022-06-11
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (win64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 287688 rows, 62843 columns and 1146043 nonzeros
Model fingerprint: 0x88657e7c
Model has 1043 quadratic constraints
Variable types: 2620 continuous, 60223 integer (60212 binary)
Coefficient statistics:
Matrix range [1e-05, 1e+05]
QMatrix range [8e-01, 1e+01]
QLMatrix range [1e+00, 4e+04]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-05, 1e+05]
QRHS range [4e+04, 4e+04]
Presolve removed 216762 rows and 54175 columns (presolve time = 6s) ...
Presolve removed 217976 rows and 54528 columns
Presolve time: 7.60s
Presolved: 74171 rows, 9107 columns, 320106 nonzeros
Presolved model has 97 quadratic constraint(s)
Presolved model has 1187 bilinear constraint(s)
Variable types: 2610 continuous, 6497 integer (6448 binary)

Root simplex log...

Iteration Objective Primal Inf. Dual Inf. Time
0 handle free variables 9s
Warning: Markowitz tolerance tightened to 0.125
15970 -6.1672936e+05 0.000000e+00 0.000000e+00 10s
15970 -6.1672936e+05 0.000000e+00 0.000000e+00 10s
15974 -6.1672936e+05 0.000000e+00 0.000000e+00 10s
Extra simplex iterations from dual to original model: 4

Use crossover to convert LP symmetric solution to basic solution...

Root crossover log...

32 DPushes remaining with DInf 0.0000000e+00 10s
0 DPushes remaining with DInf 0.0000000e+00 10s

1809 PPushes remaining with PInf 1.4135656e-05 10s
1 PPushes remaining with PInf 2.6935159e-04 10s

Push phase complete: Pinf 2.6935159e-04, Dinf 3.2534204e+02 10s

Root simplex log...

Iteration Objective Primal Inf. Dual Inf. Time
17814 -6.1672936e+05 0.000000e+00 3.253420e+02 10s
18057 -6.1672936e+05 0.000000e+00 0.000000e+00 10s
18064 -6.1672936e+05 0.000000e+00 0.000000e+00 10s
Extra simplex iterations after uncrush: 7

Root relaxation: objective -6.167294e+05, 18064 iterations, 1.97 seconds (1.44 work units)

0 0 -616729.36 0 1223 - -616729.36 - - 19s
H 0 0 -522664.0760 -616729.36 18.0% - 20s
0 0 -614401.44 0 1302 -522664.08 -614401.44 17.6% - 30s
0 0 -614143.20 0 1822 -522664.08 -614143.20 17.5% - 35s
0 0 -613362.36 0 1413 -522664.08 -613362.36 17.4% - 42s
0 0 -613362.36 0 635 -522664.08 -613362.36 17.4% - 67s
H 0 0 -557498.5230 -613362.36 10.0% - 67s
0 0 -609380.98 0 1053 -557498.52 -609380.98 9.31% - 71s
0 0 -603343.96 0 959 -557498.52 -603343.96 8.22% - 74s
0 0 -600378.91 0 1050 -557498.52 -600378.91 7.69% - 79s
0 0 -600163.56 0 1124 -557498.52 -600163.56 7.65% - 81s
0 0 -599979.00 0 1110 -557498.52 -599979.00 7.62% - 84s
0 0 -599947.15 0 1175 -557498.52 -599947.15 7.61% - 85s
0 0 -599902.23 0 1116 -557498.52 -599902.23 7.61% - 87s
0 0 -599898.07 0 1147 -557498.52 -599898.07 7.61% - 88s
0 0 -599875.24 0 1184 -557498.52 -599875.24 7.60% - 90s
0 0 -599872.83 0 1104 -557498.52 -599872.83 7.60% - 91s
0 0 -599838.58 0 1278 -557498.52 -599838.58 7.59% - 94s
0 0 -599830.93 0 1298 -557498.52 -599830.93 7.59% - 94s
0 0 -599775.04 0 1193 -557498.52 -599775.04 7.58% - 97s
0 0 -599763.64 0 1278 -557498.52 -599763.64 7.58% - 98s
0 0 -599714.09 0 1078 -557498.52 -599714.09 7.57% - 99s
0 0 -599711.71 0 1030 -557498.52 -599711.71 7.57% - 100s
0 0 -599704.89 0 1226 -557498.52 -599704.89 7.57% - 101s
0 0 -599703.11 0 1197 -557498.52 -599703.11 7.57% - 102s
0 0 -599685.20 0 1150 -557498.52 -599685.20 7.57% - 103s
0 0 -599685.14 0 1151 -557498.52 -599685.14 7.57% - 124s

Cutting planes:
Learned: 17
Gomory: 3
Cover: 100
Implied bound: 249
Clique: 1760
MIR: 131
StrongCG: 10
Flow cover: 89
GUB cover: 52
Zero half: 5
Mod-K: 1
RLT: 137
Relax-and-lift: 275
BQP: 2
PSD: 14

Explored 1 nodes (141611 simplex iterations) in 209.29 seconds (148.67 work units)
Thread count was 4 (of 4 available processors)

Solution count 2: -557499 -522664

Time limit reached
Best objective -5.574985230197e+05, best bound -5.996731379844e+05, gap 7.5650%

Elapsed time is 1128.248866 secends.

But I've set the parameters for the solution.

gurobi_stop_gap = 10^(-4);
longest_solve_time = 200;
NumericFocus = 2;
options = sdpsettings('verbose',2,'solver','GUROBI', 'debug', 1, 'gurobi.NonConvex', 2,'gurobi.timelimit',longest_solve_time,...
'gurobi.MIPGap', gurobi_stop_gap);

Excuse me, why did I set the time to 200s, but the solution took so long? How can I solve this problem?Thank you for your kindness help.

Official comment

Gwyneth Butera

Gurobi Staff

June 05, 2022 12:38

Thanks for providing the log. You can see that the Gurobi solve does terminate in just about 200s:

Explored 1 nodes (141611 simplex iterations) in 209.29 seconds (148.67 work units)

I suspect that the "Elapsed time" also includes some pre or post processing of the model. If you could add some timestamps before and after the optimization, you might be able to arrow down where the time is being spent outside of the optimization.

wangyu hu

June 05, 2022 13:30

Thank you. I want to ask one more question：What does this part do? Because the previous result didn't have this, it did after adding several parameters (including: variable matrix multiplication).

June 07, 2022 13:57

Gurobi solves your model with the barrier method. As an interior point method, the barrier does not compute a basic solution (i.e., one in a vertex of the feasible region) but an interior one, that is then pushed to the boundary (and hence transformed into a basic solution) by an additional step called crossover.

PPushes is the number of primary push steps that remain, specifically the number of variables that must be pushed to their bounds in order to obtain a basic (vertex) solution. Likewise, DPushes is the number of dual push steps that remain.

Gurobi's solution time far exceeds the set time.

Comments

Didn't find what you were looking for?