作爲一個整數線性規劃制定雙線性優化程序

Question

在我的工作中，我遇到了以下問題：給定相似性矩陣D，其中$ d_ {i，j} \ in \ Re $表示對象之間的相似性$ i $和$ j $，我想在{1，\ dots，n} $中爲$ k \選擇$ k $對象，這樣可以最小化所選對象之間的相似性。我第一次嘗試正式制定這個問題是使用以下整數程序：

$ \ 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,2} $來表示目標函數是線性的，這表示是否選擇了對象$ X_1 $和$ X_2 $。然而，我努力想要確定必須選擇恰好$ k $對象的約束，即先前的約束$ X_1 + X_2 + \ dots + X_n = k $。

由於我不是數學編程方面的專家，我不知道你是否可以幫我解決這個問題。

預先感謝您！ 一切順利，

亞瑟

Answer 1

你是在正確的道路上，只是缺少了一兩件事：

讓x_i是1，如果對象選擇，否則爲0我。

設y_ij是1，如果對象i & j都選擇，否則爲0

的IP去如下：

最大化

sum d_ij y_ij 

S.T.

sum x_i = k 

x_i + x_j - 1 <= y_ij for all i<j 

x & y binary variables 

奇怪尋找鏈接約束說，y_ij = 1 iff x_i + x_j =2

只定義一個變量y爲每一對！

希望這有助於