离散优化——从得分矩阵的每一行和每一列中恰好选择 N 项
Discrete optimization - selecting exactly N items from each row and column of a score matrix
给定一个分数矩阵，我想 select 每列和每行中的 n 个元素，这样整个矩阵中 selected 元素的总分数将是尽可能高。
示例：给定成本矩阵
array([[0.65500799, 0.79214695, 0.39854742],
[0.53634974, 0.3682463 , 0.99663978],
[0.73423119, 0.87150676, 0.80823699]])
n=1 的最佳select离子是：
array([[1., 0., 0.],
[0., 0., 1.],
[0., 1., 0.]])
本题总分0.65500799+0.87150676+0.99663978
n=2 的最佳select离子是：
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），这种方法在计算上不可行（运行 时间爆炸）。
问题：
- 这个离散优化问题是如何分类的？
- 什么启发式方法可以快速找到解决此问题的好方法？
- 哪些 Python 库实现了这些启发式算法？
这是一个基于整数规划（IP）的解决方案。
决策变量： x[i,j] = 1 如果我们 select 行 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 或 solver-specific 程序包（例如 gurobipy 或 docplex 中实现此功能。我希望这些求解器甚至可以在几分之一秒内解决中等规模的问题实例，达到最优（不是启发式）。
给定一个分数矩阵，我想 select 每列和每行中的 n 个元素，这样整个矩阵中 selected 元素的总分数将是尽可能高。
示例：给定成本矩阵
array([[0.65500799, 0.79214695, 0.39854742],
[0.53634974, 0.3682463 , 0.99663978],
[0.73423119, 0.87150676, 0.80823699]])
n=1 的最佳select离子是：
array([[1., 0., 0.],
[0., 0., 1.],
[0., 1., 0.]])
本题总分0.65500799+0.87150676+0.99663978
n=2 的最佳select离子是：
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），这种方法在计算上不可行（运行 时间爆炸）。
问题：
- 这个离散优化问题是如何分类的？
- 什么启发式方法可以快速找到解决此问题的好方法？
- 哪些 Python 库实现了这些启发式算法？
这是一个基于整数规划（IP）的解决方案。
决策变量： x[i,j] = 1 如果我们 select 行 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 或 solver-specific 程序包（例如 gurobipy 或 docplex 中实现此功能。我希望这些求解器甚至可以在几分之一秒内解决中等规模的问题实例，达到最优（不是启发式）。