インデックスとしての整数決定変数

Question

次の問題には、2つの整数変数しかありません。ただし、パラメータのインデックスに表示されます。誰かがそれを標準的な整数計画モデルに変換するための効率的なアイデアを持っているなら、それを感謝してください。

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

仮定します $x,y\in\{0,\dots,n\}$。私はこれらをループするだけだと思います$(n+1)^2$ ペアにして、制約を満たす最適なものを保持します。

しかし、整数計画法を主張する場合は、バイナリ変数を導入してください $x_i$ そして $y_i$ にとって $i\in\{0,\dots,n\}$、その解釈で $d_x=\sum_i d_i x_i$ そして $d_y=\sum_i d_i y_i$。問題は最大化することです$$\left(\sum_i d_i (y_i - x_i)\right)^2$$ 対象 \begin{align} \sum_i x_i &= 1\\ \sum_i y_i &= 1\\ \sum_i d_i (y_i - x_i) &\ge \alpha \end{align} 必要に応じて、目的を線形化できます。