# How to linearize membership in a finite set

Given finite set $$S$$ and variable $$x$$, how do I linearize the set membership constraint $$x\in S$$?

• Based on the timestamps, this question appears to be made as a more generalized response to this question. Very clever and very sly. – SecretAgentMan Jul 9 at 17:02
• Yes, there were several recent questions related to this. I didn't find any existing question/answer to reference, so I created one. – RobPratt Jul 9 at 17:04
• Brilliant. Very useful for future visitors. – SecretAgentMan Jul 9 at 17:59

First, some special cases:

• If $$S=\{c\}$$, fix $$x=c$$.
• If $$S=\{0,1\}$$, declare $$x$$ to be binary.
• If $$S=\{a,b\}\not=\{0,1\}$$, introduce binary variable $$y$$ and impose linear constraint $$x=a(1-y)+by$$.
• If $$S=\{a,a+c,a+2c,\dots,a+kc\}$$, introduce integer variable $$y\in[0,k]$$ and impose linear constraint $$x=a+cy$$. (The previous bullet is the special case $$c=b-a$$ and $$k=1$$.)

Otherwise proceed as follows.

For each $$s\in S$$, introduce a binary variable $$y_s$$. Impose linear constraints \begin{align} \sum_{s\in S} y_s &= 1 \tag1 \\ \sum_{s\in S} s y_s &= x \tag2 \end{align} Constraint $$(1)$$ chooses exactly one $$s$$ with $$y_s=1$$, and constraint $$(2)$$ forces $$x=s$$ for that $$s$$.

Alternatively (if your modeling language does not allow arbitrary index values), let $$I=\{1,\dots,|S|\}$$ for 1-based indexing or $$I=\{0,\dots,|S|-1\}$$ for 0-based indexing, with $$S=\{s_i: i \in I\}$$. For each $$i\in I$$, introduce a binary variable $$y_i$$. Impose linear constraints \begin{align} \sum_{i\in I} y_i &= 1 \tag3 \\ \sum_{i\in I} s_i y_i &= x \tag4 \end{align} Constraint $$(3)$$ chooses exactly one $$i$$ with $$y_i=1$$, and constraint $$(4)$$ forces $$x=s_i$$ for that $$i$$.

• For set S, would it be more accurate if it was defined as $S = \{s_i: s_i = ord(i), i \in I \}$ ? – holger3000 Jul 12 at 18:59
• No, the relationship between $s_i$ and $i$ is instead $\text{ord}(s_i)=i$. – RobPratt Jul 13 at 14:00