# How to express this constraint efficiently?

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

• Is the set $S_u$ known or a decision variable? Dec 19, 2022 at 13:30
• $\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$.
– KGM
Dec 19, 2022 at 13:42

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.
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\}$$
$$S_u \cup z_{u,c_1,c_2}\cdot\{c_1,c_2\}$$