How can I linearize this IF-THEN constraint?

Let

• $$P_{t,u}; t=1,2,\ldots,T, u=1,2,\ldots,U$$ be known values
• $$\alpha$$ is also a known parameter
• $$X_{t,u}$$ an optimization variable

I have the following constraint: IF $$P_{t,u}\geq\alpha$$, THEN $$X_{t,u}=1$$ and $$X_{t',u}=0, t'\neq t$$

How can I linearize this constraint?

• Several similar questions have been asked before, see for example 1, 2, 3, 4 and 5 Sep 16 '20 at 15:21

Because $$P_{t,u}$$ and $$\alpha$$ are known constants (not decision variables), no linearization is needed. In a modeling language, it would look like this:

con Mycon1 {t in 1..T, u in 1..U: P[t,u] >= alpha}:
X[t,u] = 1;
con Mycon2 {t in 1..T, u in 1..U, tp in 1..T diff {t}: P[t,u] >= alpha}:
X[tp,u] = 0;


Some languages support this equivalent form with a single constraint declaration:

con Mycon {t in 1..T, u in 1..U, tp in 1..T: P[t,u] >= alpha}:
X[tp,u] = (if tp = t then 1 else 0);


Even more compact:

con Mycon {t in 1..T, u in 1..U, tp in 1..T: P[t,u] >= alpha}:
X[tp,u] = (tp = t);


Some languages also support a FIX statement for equality constraints with one variable:

for {t in 1..T, u in 1..U, tp in 1..T: P[t,u] >= alpha}
fix X[tp,u] = (tp = t);


An alternative to declaring binary variables and then forcing them to 0 is to use a sparse index set, as demonstrated here.

If I got the question correct you don't even need a constraint. You can simply define the lower and upper bounds on your variables $$X_{t,u}$$ based on the parameters. For instance:

x[t,u] = model.addVar(lb = 1 if P[t,u] >= alpha else 0, ub = 1 if P[t,u] >= alpha else 0, vtype="B")


If there isn't a $$t$$ for all $$u$$ that fulfills $$P_{t,u} \geq \alpha$$ you can define a new set $$K:=\{(t,u)| P_{t,u} \geq \alpha \quad \forall t\in T, u \in U\}$$ and set the bounds accordingly to the set.

It is possible to translate into a linear programming formulation the following constraint:

If $$P_{t,u} \geq \alpha \rightarrow x_{t,u} =1$$ and $$x_{t’,u}=0$$ for all $$t’=1,2, …, T$$ with $$t’\neq t$$. Let introduce $$T \cdot U$$ Boolean variables: $$x_{t,u}$$

Remembering that $$P_{t,u} \cdot \alpha^{-1}=P_{t,u} \cdot \frac{1}{\alpha} \geq 1$$ if and only if $$P_{t,u} \geq \alpha$$. So, the generic constraint

$$x_{t,u} \geq P_{t,u} \alpha^{-1} \rightarrow x_{t,u}=1$$

Now we want to assign zero value to every remaining variables: it is sufficient to introduce the following constraint:

$$\sum_{t=1}^T x_{t,u} = 1$$

In general we introduce the following contraints as feasible region:

$$\left\{ \begin{array}{l} x_{1,1} \geq P_{1,1} \alpha^{-1} \\ x_{2,1} \geq P_{2,1} \alpha^{-1}\\ \vdots \\ x_{T,1} \geq P_{T,1} \alpha^{-1} \\ \sum_{t=1}^T x_{t,1} = 1 \\ \vdots \\ x_{1,U} \geq P_{1,U} \cdot \alpha^{-1} \\ x_{2,U} \geq P_{2,U} \alpha^{-1} \\ \vdots \\ x_{T,U} \geq P_{T,U} \alpha^{-1} \\ \sum_{t=1}^T x_{t,U} = 1 \\ x_{t,u} Boolean \\ \end{array} \right.$$

• If $P_{t,u}>0$ for all $t,u$ and $\alpha>0$, then your inequality constraints $x_{t,u} \ge P_{t,u} \alpha^{-1}>0$ would imply that $x_{t,u}=1$ for all $t,u$. Sep 16 '20 at 20:57
• @RobPratt, you are right! We can introduce also $x_{t,u} \cdot (P_{t,u} \alpha^{-1} -1 ) \geq 0$ in order to force $x_{t,u}=0$ whenever $P_{t,u} < \alpha$ Sep 18 '20 at 15:33
• My point is that your proposed constraints are too strong. Sep 18 '20 at 15:37