0

在我的工作中，我遇到了以下问题：给定一个相似度矩阵 D，其中 $d_{i,j} \in \Re$ 表示对象 $i$ 和 $j$ 之间的相似度，我想选择 $k $ 个对象，对于 $k \in {1, \dots, n}$，以最小化所选对象之间的相似性的方式。我第一次尝试正式制定这个问题是使用以下整数程序：

$\最小化$ $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$。

由于我不是数学编程方面的专家，我想知道您是否可以帮助我解决这个问题。

先感谢您！一切顺利，

亚瑟

4

1 回答 1

0

您走在正确的道路上，只是缺少一件事：

x_i如果选择对象 i，则为 1，否则为 0 。

y_ij如果对象i & j都被选中，则为 1，否则为0

IP如下：

最大化

sum d_ij y_ij

英石

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 变量！

希望这可以帮助

于 2013-11-07T21:18:28.187 回答