3

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!

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Nicolas Kaiser
  • 33
  • 3

1 Answers1

3

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

joni
  • 1,572
  • 7
  • 14
  • 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$ – Nicolas Kaiser Sep 18 '23 at 09:31
  • @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. – joni Sep 18 '23 at 09:39
  • Oh yes of course, thanks for your help. Funny I tried both ways but did not come to the idea of combining them. – Nicolas Kaiser Sep 18 '23 at 12:18
  • 2
    +1 for using CNF. An alternative viewpoint is to apply the usual linearization of the product $\beta_t=\delta_{t-1}(1-\delta_t)$. – RobPratt Sep 18 '23 at 12:18