# Constraint on groups of variables

Assume a LP/MILP with a large number of variables.

It is easy to formulate constraints to group variables such that each variable in a group takes the same value, if we know which variables are in a group. Consider another case, where we want to impose a constraint that in total 5 groups should be created without explicitly setting out which variable should in which group, so the solver determines the grouping. How can this constraint be formulated? (Grouping here just means that variables in a particular group takes same values)

For your first question, let binary decision variable $$y_{i,g}$$ indicate whether variable $$x_i$$ is assigned to group $$g$$, and let variable $$z_g$$ represent the common value of variables in group $$g$$. You want to enforce: \begin{align} \sum_g y_{i,g} &= 1 &&\text{for all i} \tag1 \\ \sum_g y_{i,g} z_g &= x_i &&\text{for all i} \tag2 \end{align} You can linearize $$(2)$$ via big-M constraints as follows: \begin{align} L_{i,g}(1-y_{i,g}) \le x_i - z_g &\le U_{i,g}(1-y_{i,g}) &&\text{for all i and g} \tag3 \end{align} If your solver supports indicator constraints, you can replace $$(3)$$ with: $$y_{i,g} = 1 \implies x_i = z_g \tag4$$
• Thank you @RobPratt If $i = 21$, so I have 21 $x$ variables. Do I need to define 21x5 = 105 binary variables $y_{i,g}$ and 5 variables $z_g$, if I want to create 5 groups? The first constraint in your answer requires summation of all binary variables in a group. It is unclear to me how this can be applied in this case, without explicitly setting out which of the $x_{i}$ variable falls in which group. Could you please explain?
• Yes, your variable counts are correct. The $y_{i,g}$ variables are defined for all $i$ and $g$, whether or not variable $x_i$ gets assigned to group $g$. The values for $y_{i,g}$ (found by the solver) determine the assignments. Jan 10, 2022 at 15:57