1
$\begingroup$

Let, $\mathcal{C}=\{1,2,\cdots,C\}$, $\mathcal{U}=\{1,2,\cdots,U\}$

$\mathcal{S}_u$ is a subset of $\mathcal{C}$ with $u\in \mathcal{U}$

$d_{u,c}$ is a binary variable with $u=1,2,\cdots,U$ and $c=1,2,\cdots,C$

Now, with $u=1$, if $d_{1,2}=1$ and $d_{1,5}=1$, then we want to enforce that both $2\in\mathcal{S}_u$ and $5\in\mathcal{S}_1$

Similarly,

with $u=3$, if $d_{3,2}=1$ and $d_{3,7}=1$, then we want to enforce that both $2\in\mathcal{S}_3$ and $7\in\mathcal{S}_3$

What is an efficient way of generalising this constraint for any $u\in \mathcal{U}$?

$\endgroup$
2
  • 1
    $\begingroup$ Is the set $S_u$ known or a decision variable? $\endgroup$
    – RobPratt
    Commented Dec 19, 2022 at 13:30
  • $\begingroup$ $\mathcal{S}_u$ is a known set. $d_{u,c}$ is a decision variable. If $d_{u,c}=1$, then $c$ must be in the set $\mathcal{S}_u$. How can I mathematically express this constraint without 'If-Then' constraint. I think I can express this constraint as: $\text{If }d_{u,c}=1, \text{ Then }c\in \mathcal{S}_u$. $\endgroup$
    – KGM
    Commented Dec 19, 2022 at 13:42

2 Answers 2

3
$\begingroup$

Just use a sparse index set of ordered pairs $(u,c)$ for $d_{u,c}$. Explicitly, the set is $\{(u,c):u\in\mathcal{U},c\in S_u\}$. This way, instead of defining variables that must take the value $0$, you just omit them from the problem.

$\endgroup$
1
$\begingroup$

So if $d_{u,c_1} \cdot d_{u,c_2} =1$ then $\{c_1,c_2\}$ part of $S_u$.

$d_{u,c_1} + d_{u,c_2} -1 \le z_{u,c_1,c_2}$
$z_{u,c_1,c_2} \le d_{u,c_1}$
$z_{u,c_1,c_2} \le d_{u,c_2}$
$z_{u,c_1,c_2} \in\ \{0,1\}$

If using set,
$S_u \cup z_{u,c_1,c_2}\cdot\{c_1,c_2\}$

$\endgroup$

Your Answer

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

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