12
$\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$ Jul 9, 2021 at 17:02
  • 5
    $\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, 2021 at 17:04
  • $\begingroup$ Brilliant. Very useful for future visitors. $\endgroup$ Jul 9, 2021 at 17:59

1 Answer 1

20
$\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$
4
  • $\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, 2021 at 18:59
  • $\begingroup$ No, the relationship between $s_i$ and $i$ is instead $\text{ord}(s_i)=i$. $\endgroup$
    – RobPratt
    Jul 13, 2021 at 14:00
  • $\begingroup$ For case 4 in your special cases, shouldn't "...introduce integer variable $y \in [0,k]$..." instead be "...introduce integer variable $y \in \{0,1,\dots,k\}$..."? I initially read "$y \in [0,k]$" as "$0 \leq y \leq k, y \in \mathbb R$". $\endgroup$
    – mhdadk
    Oct 14, 2023 at 17:52
  • 1
    $\begingroup$ @mhdadk Yes, that is equivalent. “Integer” implies intersection with $\mathbb{Z}$. $\endgroup$
    – RobPratt
    Oct 14, 2023 at 21:08

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.