# ILP and number of variables in constraints

This question is about the time impact of the length (i.e. number of variables) of the constraints in an Integer Linear Programming formulation. Most people try to reach the minimum number of constraints/variables, but I couldn't find anything that considers the size of the constraints.

In more concrete terms, I have some maximization problem for which I can make two different formulations $A$ and $B$. Both have $O(n^2)$ variables, $n$ being the size of the input.

Formulation $A$ has $O(n^3)$ constraints, each having a constant number of variables (say each constraint is a summation over four variables).

Formulation $B$ has $O(n^2)$ constraints, but many constraints are of linear size - i.e. they include summations over $O(n)$ variables.

In terms of performance, does $B$ have an advantage over $A$ ?

To take your example, suppose you have a variable $$y$$ that is 1 only if all variables $$x_0, x_2, \ldots, x_{n-1}$$ have value 1, and all values are binary. You could write a single constraint $$ny \le \sum_{i=0}^n x_i$$
or $$n$$ constraints $$y \le x_i, \forall i \in \{0, \ldots n-1\}$$
Both sets of constraints will have the same integer-feasible set, but the $$n$$ constraints have a much smaller continuous-feasible set, so it is probably be much faster to solve.