How to linearize If-then constraint in linear programming?

Question

I have the following decision variables:

$a_i, x_i^t$ and $x_i^0$ are binary variables.

I want to realize the following four conditions:

• if $a_i = 1, \sum_{t=0}^n x_i^t = 0$, then $x_i^0 = 0$;
• if $a_i = 1, \sum_{t=0}^n x_i^t = 1$, then $x_i^0 = 1$;
• if $a_i = 0, \sum_{t=0}^n x_i^t = 0$, then $x_i^0 = 0$;
• if $a_i = 0, \sum_{t=0}^n x_i^t = 1$, then $x_i^0 = 0$ or $1$;

There is another necessary constraint: $$\sum_{t=0}^n x_i^t \leq 1$$

Can anyone help me?

Thank you.

Answer 1

While it's not completely necessary, I will define $X_i = \sum_{t = 0}^n x_i^t$. We'll also note that $X_i = 0$ if and only if all of the $x_i^t = 0$, and $X_i = 1$ if and only if exactly one of the $x_i^t = 1$.

To linearise the first condition, we want to create a constraint that looks like

$$x_i^0 \leq P(a_i, X_i)$$

where $P$ is some linear function that is equal to zero when $a_i = 1$ and $X_i = 0$, and bigger than or equal to 1 otherwise. So an easy choice is:

$$x_i^0 \leq (1 - a_i) + X_i$$

You can do something very similar for the third constraint.

If you have another constraint that means that $X_i$ can never be greater than 1, then you can do exactly the same thing for the second constraint as well. However, if such a constraint doesn't exist then you would need to be a bit more careful if you need to test for exactly the situation where $a_i = 1$ and $X_i = 1$ (and in fact you might need to create a number of constraints to test for the individual cases where each single $x_i^t = 1$).

Answer 2

I will assume that your $\sum_{t=0}^n$ should instead be $\sum_{t=1}^n$. Otherwise the conditions are trivial because $x_i^0$ appears on both sides of each implication.

The first and third conditions reduce to $$\left(\bigwedge_{t=1}^n \lnot x_i^t\right) \implies \lnot x_i^0.$$ Rewriting in conjunctive normal form somewhat automatically yields linear constraints: $$ \left(\lnot \bigwedge_{t=1}^n \lnot x_i^t\right) \lor \lnot x_i^0 \\ \left(\bigvee_{t=1}^n x_i^t\right) \lor \lnot x_i^0 \\ \sum_{t=1}^n x_i^t + (1-x_i^0) \ge 1 \\ x_i^0 \le \sum_{t=1}^n x_i^t $$

---

Here is an updated answer based on your latest changes. Note that the fourth condition is automatically satisfied because $x_i^0$ is binary. Also, because $a_i$ is binary the first and third conditions can be combined as $$\sum_{t=0}^n x_i^t = 0 \implies x_i^0 = 0,$$ but this also holds automatically because $x_i^t \ge 0$.

So only the second condition needs to be enforced. You want $$\left(a_i = 1 \land \sum_{t=0}^n x_i^t = 1\right) \implies x_i^0 = 1.$$ Because $\sum_{t=0}^n x_i^t \le 1$, the desired implication is equivalent to $$\left(a_i \land y_i\right) \implies x_i^0,$$ where $y_i=\sum_{t=0}^n x_i^t\in\{0,1\}$. Rewriting in conjunctive normal form somewhat automatically yields linear constraints: $$ \lnot \left(a_i \land y_i\right) \lor x_i^0 \\ \lnot a_i \lor \lnot y_i \lor x_i^0 \\ (1-a_i) + (1-y_i) + x_i^0 \ge 1 \\ a_i + y_i - x_i^0 \le 1 \\ a_i + \sum_{t=0}^n x_i^t - x_i^0 \le 1 \\ a_i + \sum_{t=1}^n x_i^t \le 1 $$