4

Given a model with a binary variable $b_s$ that describes whether taking an item $s$ from a set $S$ or not. Consider that some other constraint in the model depends upon whether all items of the set are taken (so to say the minimum of all $b_s$).

That other constraint can also be described with the help of a further binary variable, but given that $b_s$ and $c$ are "tightly connected" (for lack of a better term), I could also use a continuous variable $c$ in the domain $[0, 1]$ as given:

$$ c \leq b_s \quad \forall \, s \in S \\ c \geq \sum_{s \in S} b_s - |S| + 1 \\ b_s \in \{0, 1\} \quad \forall \, s \in S \\ c \in [0, 1] $$

Even though $c$ is continuous, in a feasible solution it can only take the values 0 or 1 due to the constraints.

What are the dis/advantages in this approach compared to describing $c$ as binary variable when solving such a model using existing solvers (CBC, Gurobi, CPLEX, etc.)?

Andreas
  • 313
  • 1
  • 6
  • 1
    prubin answered this question here. Spoiler: its a "roll of the dice"! – Kuifje Oct 29 '21 at 13:00
  • Thanks, indeed. However, to expand on his advice. In this case here, it would be necessary to think of whether taking all items is an expected case in an optimal solution or rather a corner case. If it was the latter, then probably the better approach is to go with a continuous variable, otherwise the solver could consider the case of taking all items faster. – Andreas Oct 29 '21 at 13:07
  • 2
    If you think you know the answer to whether all units would be taken (i.e., you think you know whether it is an "expected case" or "edge case"), it might be worthwhile to make the variable integer (regardless of which case you anticipate), give it maximal branching priority (or use a callback to force the solver to branch on it first), and induce the solver (via parameter settings or callback) to work on the subtree you think is applicable first, hoping to get an incumbent that will let the solver prune the other subtree quickly. – prubin Oct 29 '21 at 15:40

0 Answers0