combinatorics - 找到 NxM 数组的每列 x 个数和每行 y 个数的最佳选择

Question

给定一个 NxM 正整数数组，如何选择整数，以便在每行最多有 x 个选择，每列最多有 y 个选择的情况下获得最大的值总和。这是我在制作 NCAA 游泳阵容时所面临的一个问题的抽象。每个游泳者在每个项目中都有一个时间，可以使用USA Swimming Power Points Calculator将其转换为整数，越高越好。一旦你转换了这些时间，我想为每个项目分配不超过 3 名游泳者，每个游泳者不超过 3 场比赛，以使力量得分的总和最大化。我认为这类似于武器瞄准分配问题但是这个问题允许一种武器类型多次攻击同一个目标（在我的情况下，允许一个游泳者参加同一个事件两次），这对我的用例不起作用。有人知道 wta 问题的这种变化被称为什么，如果知道的话，您知道我可以寻找的任何解决方案或资源吗？

Answer 1

这是一个数学模型：

数据

Let a[i,j] be the data matrix
and   
    x: max number of selected cells in each row 
    y: max number of selected cells in each column 

（注意：这有点不寻常：我们通常为变量保留名称 x 和 y。这些约定有助于提高可读性）。

变量

 δ[i,j] ∈ {0,1} are binary variables indicating if cell (i,j) is selected.

优化模型

 max sum((i,j),  a[i,j]*δ[i,j])
 sum(j,δ[i,j]) ≤ x   ∀i
 sum(i,δ[i,j]) ≤ y   ∀j
 δ[i,j] ∈ {0,1}

这可以输入任何 MIP 求解器。