# Binary logical constraint dependent on indices

I don't know if I can ask this here, but I've been pulling my hair out trying to think of how to represent this in constraints.

I have two sets of binary variables: $$X_t$$ and $$Y_{it}$$. So, I want to represent that,

• if $$X_t=X_{t-1}$$ then $$Y_{it}=Y_{it-1}$$ I can't seem to find a way that works without enforcing other behaviors.

Maybe this is basic and I am just blocked.

You can enforce $$X_t=X_{t-1}\implies Y_{it}=Y_{it-1}$$ with additional binary variables $$\omega_{0t},\omega_{1t},\omega_{2t}$$ as follows:

\begin{align} X_t+X_{t-1}&=0\omega_{0t}+1\omega_{1t}+2\omega_{2t} \tag{1} \\ \omega_{0t}+\omega_{1t}+\omega_{2t} &= 1 \tag{2}\\ \omega_{0t} &\le 1-Y_{it}+Y_{it-1} \tag{3}\\ \omega_{0t} &\le 1-Y_{it-1}+Y_{it} \tag{4}\\ \omega_{2t} &\le 1-Y_{it}+Y_{it-1} \tag{5}\\ \omega_{2t} &\le 1-Y_{it-1}+Y_{it} \tag{6}\\ \end{align}

Constraints $$(1)$$ encapsulate the different possible values of the sum $$X_t+X_{t-1}$$. Constraints $$(2)$$ make sure that exactly one these options is active. Constraints $$(3)-(6)$$ enforce $$\omega_{0t} \vee \omega_{2t} \implies Y_{it}=Y_{it-1}$$.

Note that you could use constraint $$(2)$$ to get rid of one of the $$\omega$$ variables, but I think the model is more readable as it is.

Alternatively, you want to enforce $$(X_t \wedge X_{t-1})\implies (Y_{it}\wedge Y_{it-1})\vee (\neg Y_{it}\wedge \neg Y_{it-1}) \tag{7}$$ and $$(\neg X_t \wedge \neg X_{t-1})\implies (Y_{it}\wedge Y_{it-1})\vee (\neg Y_{it}\wedge \neg Y_{it-1}) \tag{8}$$ Constraint $$(7)$$ is equivalent to \begin{align} &\quad\; \neg (X_t \wedge X_{t-1})\vee (Y_{it}\wedge Y_{it-1})\vee (\neg Y_{it}\wedge \neg Y_{it-1}) \\ &\equiv (\neg X_t \vee \neg X_{t-1})\vee (Y_{it}\wedge Y_{it-1})\vee (\neg Y_{it}\wedge \neg Y_{it-1}) \\ &\equiv (1- X_t + 1- X_{t-1} + Y_{it}+ 1-Y_{it-1} \ge 1) \wedge (1- X_t + 1- X_{t-1} + 1-Y_{it}+ Y_{it-1} \ge 1)\\ &\equiv (X_t + X_{t-1} - Y_{it} +Y_{it-1}\le 2) \wedge (X_t + X_{t-1} +Y_{it}- Y_{it-1} \le 2) \\ \end{align}

Similarly, constraint $$(8)$$ is equivalent to $$(X_t + X_{t-1} - Y_{it} +Y_{it-1}\ge 0) \wedge (X_t + X_{t-1} +Y_{it}- Y_{it-1} \ge 0)$$ The resulting model is $$0 \le X_t + X_{t-1} - Y_{it} +Y_{it-1}\le 2 \\ 0 \le X_t + X_{t-1} + Y_{it} -Y_{it-1}\le 2$$ as proposed by @user1502040.

• Looks better now (+1) but you need to explicitly impose $\sum \omega_i=1$. Alternatively, you can use the logarithmic formulation that requires only two binaries and no SOS constraint. Aug 1 at 12:55
• Thanks @RobPratt for the helpful comment. May I ask what you mean by the logarithmic formulation? Aug 1 at 13:10
• You can introduce (logarithmically many) binary variables $z_{0,t}$ and $z_{1,t}$ and replace constraint $(1)$ with $X_t + X_{t-1}=2^0 z_{0,t} + 2^1 z_{1,t}$. Then $X_t = X_{t-1}$ corresponds to $z_{0,t}=0$. Aug 1 at 13:51
• And does this also work for stuff like $X_t \geq X_{t-1}$ ? Aug 1 at 14:06
• @orpanter yes, this "framework" works for any logical contraints with binary variables. For example, enforcing $X_t\ge X_{t-1} \implies Y_{it} = Y_{it-1}$ is equivalent to $(X_t \wedge X_{t-1})\vee (\neg X_t \wedge \neg X_{t-1})\vee (X_t \wedge \neg X_{t-1}) \implies (Y_{it} \wedge Y_{it-1})\vee (\neg Y_{it} \wedge \neg Y_{it-1})$. From there you could derive the correponding linear constraints with boolean algebraic manipulations. Aug 1 at 20:19

You could convert to CNF.

$$(a = b) \implies (c = d)$$ can be expressed by:

$$0 \le a + b + c - d \le 2$$ $$0 \le a + b + d - c \le 2$$

• +1 but would be good to show the resulting CNF that leads to these constraints. Aug 1 at 12:45
• $(a\wedge b\wedge c\wedge \neg d)\vee (a\wedge b\wedge \neg c\wedge d)\vee (\neg a\wedge \neg b\wedge c\wedge \neg d)\vee (\neg a\wedge \neg b\wedge \neg c\wedge d)$
– xd y
Aug 3 at 3:32

With the common $$\text{BigM}$$ approach, we can linearize the logical expression as follows:

$$if: \quad (x_{t}-x_{t-1} = 0) \implies (y_{i,t} - y_{i,t-1} = 0) \quad \equiv$$ $$if: \quad (x_{t}-x_{t-1} = 0) \implies (z_{i,t} = 1) \implies(y_{i,t} - y_{i,t-1} = 0) \quad \equiv$$

The first part would be:

$$if: \quad (z_{i,t} = 0) \implies ((x_{t}-x_{t-1} \geq 1) \lor (x_{t}-x_{t-1} \leq -1)) \quad \equiv$$ $$if: \quad (z_{i,t} = 0) \implies (((w_{t} = 1) \implies (x_{t}-x_{t-1} \geq 1)) \lor ((o_{t} = 1) \implies (x_{t}-x_{t-1} \leq -1))) \quad \equiv$$

That yields the following three linear expressions:

$$z_{i,t} + w_{t} + o_{t} \geq 1 \quad (1)$$ $$x_{t} - x_{t-1} \geq 1 - m(1-w_{t}) \quad (2)$$ $$x_{t} - x_{t-1} \leq -1 + M(1-o_{t}) \quad (3)$$

The second part also would be:

$$(z_{i,t} = 1) \implies(y_{i,t} - y_{i,t-1} = 0) \quad$$

That translating into the following expressions:

$$y_{i,t} - y_{i,t-1} \geq 0 - m(1-z_{i,t}) \quad (4)$$ $$y_{i,t} - y_{i,t-1} \leq 0 + M(1-z_{i,t}) \quad (5)$$

Where the value of $$m$$ and $$M$$ should be $$\leq 2$$.

Also, based on the indicator variables the corresponding CNF is:

$$(z_{i,t}) \bigvee ((x_{t} \land \lnot x_{t-1}) \lor (\lnot x_{t} \land x_{t-1}))$$

Thant yields following inequalities:

$$z_{i,t} + x_{t} + x_{t-1} \geq 1 \quad (1)$$ $$z_{i,t} - x_{t} - x_{t-1} \geq -1 \quad (2)$$

And the second part would be:

$$(\lnot z_{i,t}) \bigvee ((y_{i,t} \land y_{i,t-1}) \lor (\lnot y_{i,t} \land \lnot y_{i,t-1}))$$

Thant yields following inequalities:

$$-z_{i,t} + y_{i,t} - y_{i,t-1} \geq -1 \quad (1)$$ $$-z_{i,t} - y_{i,t} + y_{i,t-1} \geq -1 \quad (2)$$