4

I have a problem where I have N binary decision variables where each one of them belongs to a group (Where the number of groups G is less than N) and I have to choose a subset of them to maximize some criteria but there are two constraints on the valid solutions.

1- The sum of the decision variables should not exceed a predefined value C.

2- The chosen decision variables should belong to the same group.

So the first constraint is pretty straightforward to model mathematically but I still have not managed to find a way to represent the second constraint in a mathematical fashion.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
A. H
  • 147
  • 2

1 Answers1

3

Say your variables are $x_1,\ldots, x_n$. The first constraint could be modeled as $$\sum_{i=1}^n x_i \leq C.$$ This makes sure that not more than $C$ variables are chosen.

If understood your question correctly the optimal solution may only have non-zero values for variables in the same group and not all variables from the group are mandatory to be selected.This can modeled as follows:

Let $\mathcal{G}$ be the set of groups. For each group $G \in \mathcal{G}$ you add a new variable $z_G \in \{0,1\}$ which indicates whether or not the group is picked. By adding the constraint $$\sum_{G\in\mathcal{G}} z_G \leq 1$$ you ensure that only 1 group makes it to the optimal solution.

Let $s_G$ indicate the number of variables in group $G$. The constraints $$\sum_{i \in G} x_i \leq z_G \cdot s_G ~\forall G \in \mathcal{G}$$ enforce that variables can only be chosen if the corresponding $z_G$ is equal to 1. The previous constraint, however, makes sure that this will only be the case for a single group.

Alternatively, you can (following fontanf's comment below) replace these constraints by a non-aggregated version: $$x_i\leq z_G ~~ \forall G \in \mathcal{G}, i\in G$$ If only one group has to be picked and the optimal solution would additionally require that all variables belonging to that group are chosen, then it would already suffice to set them equal to each other:

$$x_1=\ldots=x_l, ~ (1,\ldots,l)\in \mathcal{G}.$$

Typically, the non-aggregated constraints will result in a better relaxation.

In this case the presolve would eliminate all but one representative of each group automatically. But if I understood your question correctly not all variables of a group have to be picked. This can be modeled by the other two sets of constraints mentioned above.

YukiJ
  • 2,023
  • 12
  • 39
  • 1
    Why not just $x_i \le z_G$ for all $G \in \cal{G}$, $i \in G$ for the second constraint? – fontanf Dec 21 '21 at 14:48
  • $s_G$ can be replaced with $C$ and then you won't need a separate constraint on $C$ – Ben Voigt Dec 21 '21 at 22:16
  • @fontanf This would also work! I included your comment in the answer. Thank you! – YukiJ Dec 22 '21 at 11:31
  • If I understood the problem well, can't this be solved by clique constraints without introducing new variables? $x_i + x_j \leq 1 ; \forall G_1 \in \mathcal{G}, ; \forall G_2 \in \mathcal{G} \setminus {G_1}, ; \forall i \in G_1, ; \forall j \in G_2$. These are a lot of constraints, but modern solvers are usually good at aggregating these. – Alberto Santini Mar 15 '22 at 07:51