4
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Why not just $x_i \le z_G$ for all $G \in \cal{G}$, $i \in G$ for the second constraint? $\endgroup$
    – fontanf
    Dec 21, 2021 at 14:48
  • $\begingroup$ $s_G$ can be replaced with $C$ and then you won't need a separate constraint on $C$ $\endgroup$
    – Ben Voigt
    Dec 21, 2021 at 22:16
  • $\begingroup$ @fontanf This would also work! I included your comment in the answer. Thank you! $\endgroup$
    – YukiJ
    Dec 22, 2021 at 11:31
  • $\begingroup$ 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. $\endgroup$ Mar 15, 2022 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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