I am trying to reformulate an optimisation problem with unknown $x$ of dimension $K\times 1$ into a mixed-integer program using big-M transformation.
In this respect, among my constraints, I have that
$$
\text{ $(\star)$
for $i=1,…,21$: $r_i(x)=0$ $\Rightarrow$ $l_{i,j}(x)=0$ for $j=1,…,8$}
$$
where $r_i, l_{i,j}$ are linear functions of $x$ mapping from $\mathbb{R}^K$ to $\mathbb{R}$.
Following the answers to my previous questions (e.g., here) $(\star)$ can be rewritten introducing $3$ binary variables $\gamma_{1,i,j},\gamma_{2,i,j},\gamma_{3,i,j}$ and a tolerance level $\epsilon>0$
$$
\begin{cases}
\gamma_{1,i,j}=1\Rightarrow r_i(x)\leq -\epsilon\\
\gamma_{3,i,j}=1\Rightarrow r_i(x)\geq \epsilon\\
\gamma_{2,i,j}=1\Rightarrow -\epsilon\leq r_i(x)\leq \epsilon\text{, } l_{i,j}(x)=0\\
\gamma_{1,i,j}+\gamma_{2,i,j}+\gamma_{3,i,j}=1
\end{cases}
$$
Now, the rewriting above means introducing $3*21$ binary variables. This, combined with my other constraints (that include many other big-M transformations), slow things down tremendously.
I have noticed that in my problem BY CONSTRUCTION there are some relations of the type
$$
r_i(x)=0 \Rightarrow r_t(x)=0
$$
for some $i=1,…,8$, $t=1,…,8$ (these are not constraints; they just happen by construction).
Using the same logic as above, this can be rewritten
introducing $3$ binary variables $\beta_{1,i},\beta_{2,i},\beta_{3,i}$ and a tolerance level $\epsilon>0$
$$
\begin{cases}
\beta_{1,i}=1\Rightarrow r_i(x)\leq -\epsilon\\
\beta_{3,i}=1\Rightarrow r_i(x)\geq \epsilon\\
\beta_{2,i}=1\Rightarrow -\epsilon\leq r_i(x)\leq \epsilon\text{, } r_{t}(x)=0\\
\beta_{1,i}+\beta_{2,i}+\beta_{3,i}=1
\end{cases}
$$
Question: does adding these additional constraints make the solver any faster? Or, since we are including even more binary variables, things get worse?
Best Answer
I think the question of whether redundant constraints help is in general an empirical one. Sometimes they do, sometimes they don't. The extra binary variables might indeed slow things down, but they also might not.
One concern I would have would be whether the $\beta$ variables might "distract" the solver from focusing on other integer variables that perhaps would be more important. If I thought that were happening, I would try adding branching priorities (which at least some solvers let you supply). Branching priorities are basically weights assigned to the integer variables, such that the solver is encouraged/compelled to branch first on the variables with higher priority. Giving the $\beta$ variables lower priorities would at least keep the solver focused on the other integer variables.