Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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,
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.
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$$
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) $$
