3

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.

xd y
  • 1,186
  • 3
  • 9
  • 1
    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. – Erwin Kalvelagen Jul 27 '21 at 10:47
  • @Erwin Kalvelagen Which solvers do this? I was unaware of such a thing. – Mark L. Stone Jul 27 '21 at 16:04
  • 1
    @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. – Erwin Kalvelagen Jul 27 '21 at 16:33
  • Search phrase: “implied integer” – RobPratt Dec 09 '23 at 14:39

1 Answers1

5

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • In theory, shouldn't the integer version with lower branching priority dominate the continuous version? The variables would never be branched on and their integrality could be used in the presolve to tighten the bounds more – fontanf Oct 29 '21 at 14:00
  • @fontanf That seems plausible, but I think it would need to be supported by significant experimentation. I'm not sure about the "never be branched on" part, because I don't know whether solvers necessarily consider branching priorities absolute. For instance, if using CPLEX with "strong" or "pseudocost" branching, do we know that a variable that is less attractive on those criteria but has higher priority will be selected in preference to a variable that is more attractive but has lower priority? To me it's unclear from the documentation. – prubin Oct 29 '21 at 15:30
  • For Cplex, I think so even if it's not very clear from the doc https://www.ibm.com/docs/en/icos/12.8.0.0?topic=cm-setpriority-method for Gurobi, it's more explicit that it's the primary criteria https://www.gurobi.com/documentation/9.1/refman/branchpriority.html Xpress offers more flexibility, in the doc, it's mentioned how to have this behavior https://www.fico.com/fico-xpress-optimization/docs/dms2019-01/solver/optimizer/HTML/chapter4_sec_section4003.html – fontanf Oct 31 '21 at 07:16
  • However, to temper what I wrote, even if this should be advantageous for branching and for the presolve, this should also have an impact on heuristics and cuts, and I'm not sure whether this impact is positive or not – fontanf Oct 31 '21 at 07:17
  • When it comes to MIPs and MIP solvers, I agree with just about any statement that contains the phrase "not sure". :-) – prubin Oct 31 '21 at 18:19