私の仕事では、次の問題に遭遇しました: $d_{i,j} \in \Re$ がオブジェクト $i$ と $j$ 間の類似性を表す類似性行列 D が与えられた場合、$k を選択したいと思います。 $ オブジェクト、$k \in {1, \dots, n}$ について、選択されたオブジェクト間の類似性を最小限に抑えるような方法で。この問題を正式に定式化する最初の試みは、次の整数プログラムを使用することでした。
$\minimize$ $d_{1,2}X_1X_2 + d_{1,3}X_1X_3 + \dots + d_{1,n}X_1X_n + d_{2,1}X_2X_1 + \dots + d_{n,n-1 }X_nX_{n-1} $
$X_1 + X_2 + \dots + X_n = k$ および $X_y \in {0,1}$ で、$y=1,\dots,n$ の場合
上記のプログラムでは、$X_y$ はオブジェクト $y$ が選択されたかどうかを示します。明らかに、上記のプログラムは線形ではありません。オブジェクト $X_1$ と $X_2$ の両方が選択されているかどうかを示す変数 $X_{1,2} $ を使用して、目的関数を線形にしようとしました。ただし、正確に $k$ 個のオブジェクトを選択する必要があるという制約、つまり前の制約 $X_1 + X_2 + \dots + X_n = k$ を定式化するのに苦労しています。
私は数理計画法の専門家ではないので、これについて教えていただけないでしょうか。
前もって感謝します！ではごきげんよう、
アーサー