9
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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