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

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.

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

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