Formulation of binary constraint with the least binary variables for linear programming

Question

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!

Answer 1

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