1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Several similar questions have been asked before, see for example 1, 2, 3, 4 and 5 $\endgroup$ – dhasson Sep 16 at 15:21
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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 $

answers to our problem:

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – RobPratt Sep 16 at 20:57
  • $\begingroup$ @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 $ $\endgroup$ – marco tognoli Sep 18 at 15:33
  • $\begingroup$ My point is that your proposed constraints are too strong. $\endgroup$ – RobPratt Sep 18 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.