Variáveis ​​de decisão inteiras como índice

Question

O problema a seguir tem apenas duas variáveis ​​inteiras; no entanto, eles aparecem no índice dos parâmetros. Agradeço se alguém tiver alguma ideia eficiente para transformá-lo em um modelo de programação inteira 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

Suponha$x,y\in\{0,\dots,n\}$. Eu acho que eu apenas faria um loop sobre esses$(n+1)^2$pares e manter o melhor que satisfaça a restrição.

Mas se você insiste em programação inteira, introduza variáveis ​​binárias$x_i$e$y_i$por$i\in\{0,\dots,n\}$, com a interpretação que$d_x=\sum_i d_i x_i$e$d_y=\sum_i d_i y_i$. O problema é maximizar$$\left(\sum_i d_i (y_i - x_i)\right)^2$$sujeito 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}Se quiser, você pode linearizar o objetivo.