In general, will the ILP be solved faster if the number of variables is smaller?

Question

This question might be a little bit vague. Suppose I have a variable $x$ in an ILP formulation such that $x$ can choose $\{0,1,2,3,4\}$. Now I use four binary variables to replace $x$, ($x_1+x_2+x_3+x_4$ to replace $x$). Will the new ILP be solved slower than the original one because we have more variables?

In general, is there any relationship between the speed of solving ILP and the number of variables or the number of constraints?

Thanks!

Answer 1

In general of course the more variables and constraints - the bigger the program - the slower it will be to solve. But I would not expect any straightforward, easily reversible transformations to cause a massive slowdown in solving, for two reasons:

1. The speed of solving also depends on something intangible about the structure of the ILP, and this is harder to change than it looks;
2. ILP solvers vary, but they are pretty smart. So for example if you replaced an unrestricted ($\mathbb R$-valued) variable $x$ by the difference of two nonnegative variables $y-z$, I think it wouldn't make much of a difference because the solver is capable of doing such things on its own.

Specifically, in a replacement like changing a variable $x \in \{0,1,2,3,4\}$ into a sum $x_1+x_2+x_3+x_4$ where $x_1, x_2, x_3, x_4 \in \{0,1\}$, I would not worry from harsh consequences due to the number of variables. I would worry about a potential slowdown for a different reason: the new ILP has many symmetric and identical-looking solutions that are often hard to deal with. (For example, $x=2$ can be represented as $(x_1, x_2, x_3, x_4) = (1,1,0,0)$ or as $(x_1,x_2,x_3,x_4) = (0,1,0,1)$ or in four other ways.) So, I suspect adding a symmetry-breaking inequality like $x_1 \le x_2 \le x_3 \le x_4$ would help a lot - especially if you are doing this many times, or with a variable with a bigger range than $0$ to $4$.

At that point, I don't expect a major difference between the formulation with $x$ and the formulation with $x_1, x_2, x_3, x_4$, though it probably depends on the specific ILP solver and the approach taken. (Branch-and-bound-based algorithms might not even notice, but certain cutting plane algorithms might be happier working with one or the other.)