6
$\begingroup$

I have a set of binary variables $X = \{ x_1, x_2, x_3, ... x_N \}$ which are connect and used with the rest of the model.

I want to define a set of binary variables which represents the change between the variables in $X$ with adjacency. Let this set be $Y = \{ y_1._2, y_2._3, y_3._4, ... y_{N-1}._{N} \}$.

This set $Y$ is expected to behave like this,

$$y_i._{i+1} = \begin{cases} 0 & \text{if $x_i=x_{i+1}$ } \\ 1 & \text{otherwise} \end{cases} $$

Eventually, I wish to limit the summation of these $y_i._{i+1}$ variables, but that is an easy part. Question is, how can I define $y_i._{i+1}$ variables in the OR model in terms of $X$ variables which reflects the multi-definition above?

$\endgroup$
0

1 Answer 1

7
$\begingroup$

You want to enforce $$ \lnot y_{i,i+1}\iff (x_i\iff x_{i+1}). $$ Rewriting in conjunctive normal form yields $$ (\lnot y_{i,i+1} \lor \lnot x_i \lor \lnot x_{i+1})\land (\lnot y_{i,i+1} \lor x_i \lor x_{i+1}) \land (y_{i,i+1} \lor \lnot x_i \lor x_{i+1}) \land (y_{i,i+1} \lor x_i \lor \lnot x_{i+1}), $$ from which we obtain linear constraints \begin{align} (1-y_{i,i+1}) +(1-x_i)+(1-x_{i+1})&\ge1\\ (1-y_{i,i+1})+x_i+x_{i+1}&\ge 1\\ y_{i,i+1} +(1-x_i)+x_{i+1}&\ge 1\\ y_{i,i+1} +x_i +(1-x_{i+1})&\ge 1 \end{align} Equivalently, \begin{align} y_{i,i+1}+x_i+x_{i+1}&\le 2\\ -y_{i,i+1}+x_i+x_{i+1}&\ge 0\\ y_{i,i+1} -x_i+x_{i+1}&\ge 0\\ y_{i,i+1} +x_i -x_{i+1}&\ge 0 \end{align}

$\endgroup$
3
  • $\begingroup$ Dear Dr. Pratt, as all the above model variables are binary, can we apply the usual big-M formulation to linearize such constraint? By changing the equality constraint (x=x) into two inequality (x>=x and x<=x) and adding the auxiliary binary variable for linking these constraints? $\endgroup$
    – A.Omidi
    Commented Feb 5, 2022 at 8:11
  • 2
    $\begingroup$ Yes, in this case, the big-M approach would yield the same set of constraints. For example, you can view the first of the four constraints as $x_i+x_{i+1}-1\le M(1-y_{i,i+1})$, with $M=1$, which enforces $y_{i,i+1}=1\implies x_i+x_{i+1}\le 1$. $\endgroup$
    – RobPratt
    Commented Feb 5, 2022 at 15:01
  • $\begingroup$ Many thanks Dr. Pratt for your hints. 👍👍 $\endgroup$
    – A.Omidi
    Commented Feb 5, 2022 at 18:59

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.