11

For integer programs solvers (like Gurobi, Cplex, ...) report the value of the linear programming relaxation for integer programs, i.e.

Root relaxation: objective 2.648400e+02, 233 iterations, 0.01 seconds

Is this value independent of the presolve reductions? Is this value always the same for all solvers/versions (if we ignore numerical problems)?

user3680510
  • 3,655
  • 6
  • 26

2 Answers2

17

the answer is even worse than "no"; I recently used SCIP to compute an LP relaxation, and the outcome (the value of the dual bound) depended on the branching rule I activated (even though I never branched!).

How come?

I had strong branching activated by default, so some conflicts were evaluated, and once these were known to the solver, it used them to strengthen the dual bound in the root node. Very smart, but if you are really interested in the LP value of your integer program, you need to deactive "a lot" (I ended up asking a pure LP solver).

Marco Lübbecke
  • 5,919
  • 22
  • 64
8

Adding to Marco's answer, the value is most definitely affected. The way problem reduction algorithms work is that we often exploit problem information as it's processed to tighten variable bounds in real time, which of course affects the relaxation.

This not only means that problem reduction will often change variable bounds, but the exact changes depend on the reduction algorithms used and on the order in which the calculations were performed.

W.r.t. your second question, this value generally varies wildly, even among different versions of the same solver, because it's affected by many many things, e.g., domain reduction algorithms, convexity/integer cuts, whether the solver defaults to a non-linear relaxation (for MINLPs) etc.

Nikos Kazazakis
  • 12,121
  • 17
  • 59