Variables de decisión enteras como índice

Question

El siguiente problema tiene solo dos variables enteras; sin embargo, aparecen en el índice de los parámetros. Agradezco si alguien tiene alguna idea eficiente para transformarlo en un modelo de programación entera canónica.

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

Suponer$x,y\in\{0,\dots,n\}$. Creo que simplemente pasaría por encima de estos$(n+1)^2$pares y quedarse con el mejor que satisfaga la restricción.

Pero si insiste en la programación entera, introduzca variables binarias$x_i$y$y_i$por$i\in\{0,\dots,n\}$, con la interpretación de que$d_x=\sum_i d_i x_i$y$d_y=\sum_i d_i y_i$. El problema es maximizar$$\left(\sum_i d_i (y_i - x_i)\right)^2$$sujeto a\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 lo desea, puede linealizar el objetivo.