7
$\begingroup$

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.

$\endgroup$

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Commented Aug 1, 2023 at 12:55
  • 1
    $\begingroup$ Thanks @RobPratt for the helpful comment. May I ask what you mean by the logarithmic formulation? $\endgroup$
    – Kuifje
    Commented Aug 1, 2023 at 13:10
  • 1
    $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Commented Aug 1, 2023 at 13:51
  • 1
    $\begingroup$ And does this also work for stuff like $X_t \geq X_{t-1}$ ? $\endgroup$
    – orpanter
    Commented Aug 1, 2023 at 14:06
  • 1
    $\begingroup$ @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. $\endgroup$
    – Kuifje
    Commented Aug 1, 2023 at 20:19
10
$\begingroup$

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$$

$\endgroup$
2
  • $\begingroup$ +1 but would be good to show the resulting CNF that leads to these constraints. $\endgroup$
    – RobPratt
    Commented Aug 1, 2023 at 12:45
  • $\begingroup$ $(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)$ $\endgroup$
    – xd y
    Commented Aug 3, 2023 at 3:32
3
$\begingroup$

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) $$

$\endgroup$

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.