# How to linearize If-then constraint in linear programming?

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.

• Realize using what? Nov 6, 2023 at 14:07
• @SassatelliGiulio Add these constraints to the gurobi.
– Long
Nov 6, 2023 at 14:19
• Is $x_i^0$ distinct from $x_i^t$ with $t = 0$? If so, then you should probably use a different notation for the former. Nov 6, 2023 at 23:25

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

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$$