4
$\begingroup$

There are sometimes variables that automatically take integer values in feasible solutions, like MTZ-formulation of TSP. They could be declared continuous or integer, and I find the solver performs differently, but it seems neither is generally better. I wonder if there is any experience or suggestions on this topic.

$\endgroup$
3
  • 1
    $\begingroup$ In some cases the solver will reclassify a continuous variable as binary. It may require careful inspection of the solver log to find this out. $\endgroup$ Jul 27 at 10:47
  • $\begingroup$ @Erwin Kalvelagen Which solvers do this? I was unaware of such a thing. $\endgroup$ Jul 27 at 16:04
  • 1
    $\begingroup$ @MarkL.Stone I have seen this for sure with Cplex. The presolver makes (in some cases) relaxed variables integer again. You can see this in the presolver statistics (the count of binary variables is suddenly increasing). I am not sure how to turn off this behavior. $\endgroup$ Jul 27 at 16:33
5
$\begingroup$

If the variable is declared integer (and assuming the solver leaves it that way in the presolve stage), there is at least a chance that the solver will branch on it. In some cases this might be a good thing (getting the solver to a feasible solution faster, improving the bound faster) and in some cases this might be a bad thing (distracting the solver from more productive branching strategies). My personal inclination is to relax the integrality restriction unless something in the structure of the problem makes me think that partitioning the solution spaced based on that variable would be beneficial ... which in practice means that I pretty much always relax integrality. As with so many things MIP-related, it's a roll of the dice.

$\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.