Consider the following set of values: $S := \{3, 9, 17, 19, 36, 67, 1893\}$.Suppose that we want to add to an IP the condition that the variable $x$ takes only one of the values in $S$. Show how to satisfy this requirement so that the resulting formulation is an IP (Integer Program).
HINT: add a binary variable for each number in the set $S$.
I am dealing with the formulation of the problems for the IP tasks and I am not sure how to deal with this one. My current thoughts are: $$ x = 3y_1 $$, $$ x=9y_2(1-y_1) $$, $$ x = 17y_3*(1-y_2(1-y_1)) $$And so on. Where $y_i \in \{0,1\}$
The second term $9y_2(1 - y_1)$ is not a linear expression because $y_2 y_1$ is a quadratic term.
An alternative way is to order (sort) the set $S$ ascending such that if $S = \{ s_1, s_2, \dots, s_k \}$ that $s_i < s_j$ if $i < j$.
Then introduce variables $y_1, y_2, \dots, y_{k - 1} \in \{ 0, 1 \}$.
Now add constraints such that if we want to pick $x = s_i$ that we set $y_1, \dots, y_{i - 1} = 1$, and all other $y$ variables to zero.
Then we need the constraint $y_i \geq y_j$ if $i < j$, and $$x = s_1 + \sum_{i = 1}^{k - 1} \underbrace{\left( s_{i + 1} - \sum_{j = 1}^{i} s_j \right)}_{(*)} y_i$$ Note that the expression $(*)$ for $i$ is equal to the number you need to add to all previous terms in order to find $s_{i + 1}$.
The formulation is quite ill when it comes to the relaxation, but works great with branching. Suppose that we branch on some variable $y_i$ in the middle of the sequence $y_1, \dots, y_{k-1}$. If we set it to 0, then $y_{j}$ for $j > i$ is also forced to zero. Similarly if we set $y_i$ to 1 thenthe terms $y_{j}$ for $j < i$ are forced to zero. That's quite good news!