Skip to main content

MIP faster than its relaxation

Answered

Comments

2 comments

  • Eli Towle
    Gurobi Staff Gurobi Staff

    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
    Gurobi-versary
    First Comment
    First Question

    Thanks for the answer Eli!

    0

Please sign in to leave a comment.