Variabili di decisione intere come indice

Question

Il seguente problema ha solo due variabili intere; tuttavia compaiono nell'indice dei parametri. Lo apprezzo se qualcuno ha un'idea efficiente per trasformarlo in un modello di programmazione intero canonico.

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

Supponiamo$x,y\in\{0,\dots,n\}$. Penso che farei semplicemente un giro su questi$(n+1)^2$coppie e tenere la migliore che soddisfi il vincolo.

Ma se insisti sulla programmazione di numeri interi, introduci variabili binarie$x_i$e$y_i$per$i\in\{0,\dots,n\}$, con l'interpretazione che$d_x=\sum_i d_i x_i$e$d_y=\sum_i d_i y_i$. Il problema è massimizzare$$\left(\sum_i d_i (y_i - x_i)\right)^2$$soggetto 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 vuoi, puoi linearizzare l'obiettivo.