Say I have constraints of the form:
c1.a1 + ... + c100.a100 <= K
c51.a51 + ... + c150.a150 <= K
...
where the coefficients are in the range of [0,20] and all a's are binary (0-1 integer) variables.
Is it better (from runtime perspective) to introduce the intermediate sum variables and use them as follows:
A_1_50 = c1.a1 + ... + c50.a50
A_51_100 = c51.a51 + ... + c100.a100
...
A_1_50 + A_51_100 <= K
A_51_100 + A_101_150 <= K
...
Say I am using some industrial solver like CPLEX or Gurobi. My questions are:
1) Is the second way better performance wise? 2) If it gives us better runtimes, why is that the case? I am looking for some technical explanation here.
Thank you
PS: Although I don't believe the goal is too relevant. But if that is required to answer the question, assume it is something like:
Maximize k1.a1 + ...
Assume that there are many other constraints in the program.
It is probably not a good idea. Those constraints are called Knapsack Constraints. Commercial solvers such as CPLEX and GUROBI can recognize those constraints if they exist in the model. These solvers can generate different valid inequalities (such as cover cuts) which can strengthen the formulation. If you write the inequalities using those intermediate variables then the solver probably cannot recognize that special structure in the model and therefore cannot strengthen the problem. Besides, you are adding some additional decision variables and constraints to the model which is usually not a good idea (unless they somehow strengthen the model which is not the case here).
In order to see how cover cuts work, consider the constraint $$ 5x + 3y + 2z\le 7, $$ in which $x,y,z \in \{0,1\}$ are binary variables. It is clear that $x$ and $y$ cannot take value $1$ at the same time. In this case, the cover cut $$x+y \le 1,$$ can be generated by the solver which can strengthen the model. Note that commercial solvers are advancing rapidly and we can expect that in the near future solvers become more intelligent.