Variabel keputusan bilangan bulat sebagai indeks

Aug 19 2020

Masalah berikut hanya memiliki dua variabel integer; namun, mereka muncul dalam indeks parameter. Hargai jika ada yang punya ide efisien untuk mengubahnya menjadi model pemrograman integer kanonik.

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

Jawaban

3 RobPratt Aug 19 2020 at 01:30

Memperkirakan$x,y\in\{0,\dots,n\}$. Saya pikir saya hanya akan mengulangi ini$(n+1)^2$pasang dan pertahankan yang terbaik yang memenuhi batasan.

Tetapi jika Anda bersikeras pada pemrograman integer, perkenalkan variabel biner$x_i$dan$y_i$untuk$i\in\{0,\dots,n\}$, dengan interpretasi bahwa$d_x=\sum_i d_i x_i$dan$d_y=\sum_i d_i y_i$. Masalahnya adalah untuk memaksimalkan$$\left(\sum_i d_i (y_i - x_i)\right)^2$$tunduk pada\begin{align} \sum_i x_i &= 1\\ \sum_i y_i &= 1\\ \sum_i d_i (y_i - x_i) &\ge \alpha \end{align}Jika mau, Anda dapat membuat tujuan linier.