python - 离散优化 - 从分数矩阵的每一行和每一列中精确选择 N 个项目

Question

给定一个分数矩阵，我想从每列和每行中精确选择 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

这些解决方案是由一个天真的人获得的 Breadth-First Search (BFS) 。但是，对于较大的问题(例如 10x10，n=2)，这种方法在计算上不可行(运行时间爆炸)。

问题:

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

Answer 1

这是一个基于整数规划(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)中实现此功能。我希望这些求解器甚至可以在不到一秒的时间内解决问题的中等大实例，达到最优(不是启发式)。