How to linearize membership in a finite set

Question

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

Answer 1

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$.