离散优化 - 从分数矩阵的每一行和列中精确选择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.996663978 0.80823699

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

问题：

1. 该离散优化问题如何分类？
2. 启发式方法可以允许快速找到这个问题的好解决方案？
3. python libararies实施了这些启发式方法？

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。我希望这些求解器甚至可以在一秒钟的一秒钟内解决问题的中等大量实例，即最佳(不是启发性(。