Comment puis-je linéariser cette contrainte IF-THEN?

Question

Laisser

• $P_{t,u}; t=1,2,\ldots,T, u=1,2,\ldots,U$ être des valeurs connues
• $\alpha$ est également un paramètre connu
• $X_{t,u}$ une variable d'optimisation

J'ai la contrainte suivante: IF $P_{t,u}\geq\alpha$, PUIS $X_{t,u}=1$ et $X_{t',u}=0, t'\neq t$

Comment puis-je linéariser cette contrainte?

Answer 1

Car $P_{t,u}$ et $\alpha$sont des constantes connues (et non des variables de décision), aucune linéarisation n'est nécessaire. Dans un langage de modélisation, cela ressemblerait à ceci:

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;

Certains langages prennent en charge cette forme équivalente avec une seule déclaration de contrainte:

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);

Encore plus compact:

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

Certains langages prennent également en charge une instruction FIX pour les contraintes d'égalité avec une variable:

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

Une alternative à la déclaration de variables binaires et à leur forçage à 0 consiste à utiliser un ensemble d'index clairsemé, comme illustré ici .

Answer 2

Si j'ai la bonne question, vous n'avez même pas besoin d'une contrainte. Vous pouvez simplement définir les bornes inférieure et supérieure de vos variables$X_{t,u}$basé sur les paramètres. Par exemple:

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")

S'il n'y a pas de $t$ pour tous $u$ qui remplit $P_{t,u} \geq \alpha$ vous pouvez définir un nouvel ensemble $K:=\{(t,u)| P_{t,u} \geq \alpha \quad \forall t\in T, u \in U\}$ et définissez les limites en fonction de l'ensemble.

Answer 3

Il est possible de traduire dans une formulation de programmation linéaire la contrainte suivante:

Si $ P_{t,u} \geq \alpha \rightarrow x_{t,u} =1$ et $x_{t’,u}=0 $ pour tous $t’=1,2, …, T$ avec $t’\neq t$. Laissez présenter$ T \cdot U $ Variables booléennes: $ x_{t,u} $

Se souvenir de ça $ P_{t,u} \cdot \alpha^{-1}=P_{t,u} \cdot \frac{1}{\alpha} \geq 1 $ si et seulement si $ P_{t,u} \geq \alpha$. Donc, la contrainte générique

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

réponses à notre problème:

Nous voulons maintenant attribuer une valeur nulle à toutes les variables restantes: il suffit d'introduire la contrainte suivante:

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

En général, nous introduisons les contraintes suivantes comme région réalisable:

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