11
$\begingroup$

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)?

$\endgroup$
16
$\begingroup$

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).

| improve this answer | |
$\endgroup$
8
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.