3
$\begingroup$

Is there a benefit in using integer variables instead of binaries?

I have modeled an optimization model declaring variables that equal sums of binaries to be treated as continuous variables (by declaring them to be continuous); the solver finds it obviously advantageous, during preprocessing, to change their type to integer. What could be a reason for this?

$\endgroup$
1
  • 1
    $\begingroup$ Could you please disambiguate 'their' in your question? I think you mean changing the type of the sum variable from continuous to integer; the title implies changing from binary to integer. $\endgroup$
    – TLW
    Oct 2, 2022 at 0:35

2 Answers 2

5
$\begingroup$

The solver may be able to use the integrality of the sums to do some bound tightening. For instance, if $X$ is one of your sum variables and, at some node in the tree, appears in a constraint that the solver targets for a Gomory cut, knowing that $X$ is integer and cannot have a fractional portion will factor into the computation of the cut.

$\endgroup$
5
  • 1
    $\begingroup$ Isn't it true that variables declared as binary/integer will all take part in the b&b process making the process of finding the optimum more complex? The statement "it is advantageous to work with as few as possible integral variables" is then probably only a heuristic. There is no reason to try to keep the number of integral variables low? $\endgroup$
    – Clement
    Oct 1, 2022 at 18:23
  • 1
    $\begingroup$ The only valid generalization about integer programs is that there are no other valid generalizations about integer programs. If variables are declared binary/integer, they hypothetically could be branched on, but there is no guarantee they will be. Also, with some (most?) solvers you have the option to specify branching priorities, which lets you declare them integer while discouraging the solver from branching on them (until other, higher priority variables have all been used). $\endgroup$
    – prubin
    Oct 1, 2022 at 18:41
  • 2
    $\begingroup$ Once upon a time, when solvers were less sophisticated, computers were slower and memory was in very short supply, I lived by the rule that no variable should be integer unless it absolutely had to be. I still lean that way, but with the understanding that on any given problem (and subject to the alignment of various astral bodies), declaring them to be integer might either help or hurt (or have no effect). $\endgroup$
    – prubin
    Oct 1, 2022 at 18:42
  • $\begingroup$ But if it is that bad, we should then ask astrologists about which paths in the BaB tree should be taken? :-) Just trying to be funny, I understand what you are saying. I really appreciate your help! $\endgroup$
    – Clement
    Oct 1, 2022 at 18:50
  • 1
    $\begingroup$ The problem is that with so many astral bodies, the number of possible arrangement blows up combinatorially, and astrologers only understand full enumeration. ;-) $\endgroup$
    – prubin
    Oct 1, 2022 at 20:32
5
$\begingroup$

The solver may be able to avoid spending time unnecessarily propagating obviously-incorrect partial solutions around. Imagine for instance I have the following partial problem fragment:

$$ s,t,u,v,w \in R \\ c,d,e,f \in Z \\ b_{i} \in \lbrace 0,1\rbrace \\ s = b_{0} + 2^1 b_{1} + 2^2 b_{2} + 2^3 b_{3} \\ s + c = t \\ t + d = u \\ u + e = v \\ v + f = w \\ $$

Imagine the solver, while working on the larger problem, comes up with a bound for $1.1 \le w \le 1.9$, with the other variables in this fragment still unknown. If you're treating $s$ as continuous, this appears to be valid thus far, and you're going to go ahead and do a bunch of work before realizing that there's no way to make this work.

However, if you did some up-front work, and realized that $s \in Z$ (as it is a sum of binary variables), then you can show $t \in Z$, and $u \in Z$, and $v \in Z$, and $w \in Z$. Which then means that if you're solving and come up with a bound for $1.1 \le w \le 1.9$, you can immediately stop (and likely backtrack).

Is this always worth it? No. However, your solver obviously thought it advantageous in your particular case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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