3
$\begingroup$

I am currently working on a formulation for a linear program of a complex problem. At the moment I am facing to formulate the following logical condition:

There are two binary variables. Let's name them $\beta$ and $\delta$, there are existing for $ \forall t \in T$. $\beta$ should take the value 1 only if $\delta^{t-1} = 1$ and $\delta^t = 0$. For all other cases, it should be zero.

My first approach was the following inequality: $\delta^t - \delta^{t-1} + \beta^t = 0 \quad \forall t \in T$

It's working for the described case, but it forbids also the feasible solutions of $\delta^{t-1} = 0$ and $\delta^{t} = 1$. Also $\delta^{t-1}=1$ and $\delta^{t}=1$ is feasible. Is there any way of formulating additional or other (inequality) equations to model this?

I guess with an additional binary variable I can formulate this but of course, i would like to prevent this.

Thanks for your help!

$\endgroup$

1 Answer 1

3
$\begingroup$

You want to impose the following two logical constraints:

$$ \begin{align} \delta_{t-1} = 1 \wedge \delta_t = 0 &\implies \beta_t = 1 \tag{1} \\ \neg (\delta_{t-1} = 1 \wedge \delta_t = 0) &\implies \beta_t = 0 \tag{2} \end{align} $$

For the first one, the conjunctive normal form reads

$$ \begin{align} \delta_{t-1} \wedge \neg \delta_t \implies \beta_t \\ \neg (\delta_{t-1} \wedge \neg \delta_t ) \vee \beta_t \\ \neg \delta_{t-1} \vee \delta_t \vee \beta_t \end{align} $$

and thus (1) can be modelled by $1 - \delta_{t-1} + \delta_t + \beta_t \geq 1$ which is equivalent to $\delta_t - \delta_{t-1} + \beta_t \geq 0$.

For the second one, the conjunctive normal form reads

$$ \begin{align} \neg(\delta_{t-1} \wedge \neg \delta_t) \implies \neg \beta_t \\ (\delta_{t-1} \wedge \neg \delta_t) \vee \neg \beta_t \\ (\delta_{t-1} \vee \neg \beta_t ) \wedge (\neg \delta_t \vee \neg \beta_t) % \end{align} $$

Hence, you can model (2) by imposing the linear constraints $\delta_{t-1} + 1 - \beta_t \geq 1$ and $1 - \delta_t + 1 - \beta_t \geq 1$ which are equivalent to

$$ \begin{align} \delta_{t-1} - \beta_t &\geq 0, \\ \beta_t + \delta_t &\leq 1. \end{align} $$


As @RobPratt mentioned in the comments, we can also derive these constraints by linearizing the product $\beta_t = \delta_{t-1} \cdot (1- \delta_{t})$. To see why, note that (2) is equivalent to the contraposition $\beta_t = 1 \implies \delta_{t-1} = 1 \wedge \delta_t = 0$ and thus we have

$$\delta_{t-1} = 1 \wedge \delta_t = 0 \iff \beta_t = 1.$$

Obviously, this is equivalent to

$$ \delta_{t-1} = 1 \wedge 1 - \delta_t = 1 \iff \beta_t = 1 $$

which yields $\beta_t = \delta_{t-1} \cdot (1- \delta_{t})$.

$\endgroup$
4
  • $\begingroup$ Thanks for your quick answer! The problem with this formulation is, that the feasible solution $\delta^t = 1 \land \delta^{t-1} = 1$ is infeasible due to the linear constraint $\delta^t - \delta^{t-1} + \beta^t \geq 1$ $\endgroup$ Sep 18 at 9:31
  • $\begingroup$ @NicolasKaiser Oh, my bad, there was a tiny typo. The linear constraint for (1) should be $\delta_t - \delta_{t-1} + \beta_t \geq 0$. Thanks for the hint. $\endgroup$
    – joni
    Sep 18 at 9:39
  • $\begingroup$ Oh yes of course, thanks for your help. Funny I tried both ways but did not come to the idea of combining them. $\endgroup$ Sep 18 at 12:18
  • 2
    $\begingroup$ +1 for using CNF. An alternative viewpoint is to apply the usual linearization of the product $\beta_t=\delta_{t-1}(1-\delta_t)$. $\endgroup$
    – RobPratt
    Sep 18 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.