3
$\begingroup$

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)

$\endgroup$
1
  • 3
    $\begingroup$ Please ask only one question per post. Your second question is answered here. $\endgroup$
    – RobPratt
    Jan 10 at 1:09
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Simply op
    Jan 10 at 15:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Jan 10 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.