Variables de décision entières comme index

Question

Le problème suivant n'a que deux variables entières ; cependant, ils apparaissent dans l'index des paramètres. Appréciez-le si quelqu'un a une idée efficace pour le transformer en un modèle de programmation canonique en nombres entiers.

$$ \begin{alignat*}{2} &&\max \quad & (d_y - d_x)^2 \\ &&\text{s.t.} \quad & d_y - d_x \geq \alpha \\ && & x,y \in \mathbb{Z}_+ \\ \end{alignat*} $$

Answer 1

Supposer$x,y\in\{0,\dots,n\}$. Je pense que je ferais juste une boucle sur ceux-ci$(n+1)^2$paires et gardez la meilleure qui satisfait la contrainte.

Mais si vous insistez sur la programmation entière, introduisez des variables binaires$x_i$et$y_i$pour$i\in\{0,\dots,n\}$, avec l'interprétation que$d_x=\sum_i d_i x_i$et$d_y=\sum_i d_i y_i$. Le problème est de maximiser$$\left(\sum_i d_i (y_i - x_i)\right)^2$$sujet à\begin{align} \sum_i x_i &= 1\\ \sum_i y_i &= 1\\ \sum_i d_i (y_i - x_i) &\ge \alpha \end{align}Si vous le souhaitez, vous pouvez linéariser l'objectif.