1

给定一个分数矩阵，我想从每一列和每一行中准确地选择 n 个元素，以便整个矩阵中所选元素的总分尽可能高。

示例：给定成本矩阵

array([[0.65500799, 0.79214695, 0.39854742],
       [0.53634974, 0.3682463 , 0.99663978],
       [0.73423119, 0.87150676, 0.80823699]])

n=1 的最佳选择是：

array([[1., 0., 0.],
       [0., 0., 1.],
       [0., 1., 0.]])

该方案的总分是 0.65500799+0.87150676+0.99663978

n=2 的最佳选择是：

array([[1., 1., 0.],
       [1., 0., 1.],
       [0., 1., 1.]])

该方案的总得分为 0.65500799+0.53634974+0.79214695+0.87150676+0.99663978+0.80823699

这些解决方案是通过简单的广度优先搜索 (BFS)获得的。但是，对于较大的问题（例如，10x10，n=2），这种方法在计算上是不可行的（运行时间爆炸式增长）。

问题：

  1. 这个离散优化问题是如何分类的？
  2. 什么启发式方法可以快速找到解决这个问题的好方法？
  3. 哪些 Python 库实现了这些启发式方法？
4

1 回答 1

2

这是一个基于整数规划（IP）的解决方案。

决策变量： x[i,j] = 1如果我们选择行i、列中的项目j。

参数（输入）： s[i,j] =条目得分（i, j）

公式：

maximize sum {i, j} s[i,j] * x[i,j]
subject to sum {i} x[i,j] = n     for all j
           sum {j} x[i,j] = n     for all i
           x[i,j] in {0,1}        for all i, j

您可以在 Python/PuLP或特定于求解器的包（例如gurobipy或）中实现此功能docplex。我希望这些求解器可以在几分之一秒内解决甚至中等规模的问题，达到最优（不是启发式的）。

于 2019-05-24T13:10:15.687 回答