Constraint on groups of variables

Question

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)

Answer 1

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$$