MIP faster than its relaxation

Answered

Steffan Widemann

October 20, 2020 15:00 Edited

• 
• 
• 

Hello,

I have a MIP model and its relaxed counterpart, and when running (1 thread each) them the MIP is always faster, is there any explanation for this behavior?

I keep both models and over a number of iterations I change the RHS of the same constraints for both models and re-optimize them, and on average the MIP takes 24.9s to solve while the relaxation takes 393.56s.

The model has integer flow constraints and knapsack constraints related to the established flow.

Could it be for the presolve on the MIP?

 

Here are snippets of the log for the first iteration of the MIP:

Optimize a model with 261933 rows, 258723 columns and 967383 nonzeros

Variable types: 90243 continuous, 168480 integer (167400 binary)

Coefficient statistics:

Matrix range [3e-01, 5e+04]

Objective range [4e+01, 6e+04]

Bounds range [1e+00, 1e+00]

RHS range [1e+00, 6e+00]

Presolve removed 218956 rows and 217216 columns (presolve time = 5s) ...

Presolve removed 223213 rows and 221193 columns

Presolve time: 7.64s

Presolved: 38720 rows, 37530 columns, 173928 nonzeros

Variable types: 19 continuous, 37511 integer (37442 binary)

Root simplex log...

Iteration Objective Primal Inf. Dual Inf. Time

02.4984535e+068.956603e+030.000000e+00 8s

...

421828.1872935e+050.000000e+000.000000e+00 28s

Root relaxation: objective 8.187293e+05, 42182 iterations, 19.91 seconds

Nodes | Current Node | Objective Bounds | Work

Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

00818729.3460492 - 818729.346 - - 29s

H 0 0 503991.05160 818729.346 62.4% - 29s

H 0 0 814573.03880 818729.346 0.51% - 29s

Explored 1 nodes (45007 simplex iterations) in 29.91 seconds

Thread count was 1 (of 8 available processors)

 

 

 

And here for the first iteration of the relaxation:

 

Optimize a model with 261933 rows, 258723 columns and 967383 nonzeros

Coefficient statistics:

Matrix range [3e-01, 5e+04]

Objective range [4e+01, 6e+04]

Bounds range [1e+00, 1e+00]

RHS range [1e+00, 6e+00]

Presolve removed 199711 rows and 197457 columns

Presolve time: 1.49s

Presolved: 62222 rows, 61266 columns, 252112 nonzeros

Iteration Objective Primal Inf. Dual Inf. Time

02.5168822e+063.266041e+040.000000e+00 2s

...

1908881.2143059e+065.531245e+030.000000e+00 410s

Extra one simplex iteration after uncrush

1917441.2143059e+060.000000e+000.000000e+00 415s

Solved in 191744 iterations and 414.56 seconds

 

 

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 03:06 Edited

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Eli Towle

  • Gurobi Staff

  October 20, 2020 22:11

  Yes, the difference is probably due to presolve. LP presolve isn't exactly the same as MIP presolve. On the LP:

  Presolve removed 199711 rows and 197457 columns
  Presolve time: 1.49s
  Presolved: 62222 rows, 61266 columns, 252112 nonzeros

  On the MIP, Gurobi reduces the model even further:

  Presolve removed 223213 rows and 221193 columns
  Presolve time: 7.64s
  Presolved: 38720 rows, 37530 columns, 173928 nonzeros

  The presolved LP model is ~50% larger than the presolved MIP model and takes awhile to solve. Meanwhile, Gurobi solves the root relaxation of the presolved MIP model fairly quickly, then finds a near-optimal heuristic solution at the root node almost instantly. I agree this behavior is strange, but it makes sense when considering the size differences of the presolved models.

  1
• 

  Steffan Widemann

  October 21, 2020 04:12

  • 
  • 
  • 

  Thanks for the answer Eli!

  0

Post is closed for comments.