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.
4
-
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$– Erwin KalvelagenCommented Jul 27, 2021 at 10:47
-
$\begingroup$ @Erwin Kalvelagen Which solvers do this? I was unaware of such a thing. $\endgroup$– Mark L. StoneCommented Jul 27, 2021 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$– Erwin KalvelagenCommented Jul 27, 2021 at 16:33
-
$\begingroup$ Search phrase: “implied integer” $\endgroup$– RobPrattCommented Dec 9, 2023 at 14:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ 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 $\endgroup$– fontanfCommented Oct 29, 2021 at 14:00
-
$\begingroup$ @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. $\endgroup$– prubin ♦Commented Oct 29, 2021 at 15:30
-
$\begingroup$ For Cplex, I think so even if it's not very clear from the doc 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 gurobi.com/documentation/9.1/refman/branchpriority.html Xpress offers more flexibility, in the doc, it's mentioned how to have this behavior fico.com/fico-xpress-optimization/docs/dms2019-01/solver/… $\endgroup$– fontanfCommented Oct 31, 2021 at 7:16
-
$\begingroup$ 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 $\endgroup$– fontanfCommented Oct 31, 2021 at 7:17
-
$\begingroup$ When it comes to MIPs and MIP solvers, I agree with just about any statement that contains the phrase "not sure". :-) $\endgroup$– prubin ♦Commented Oct 31, 2021 at 18:19