矩阵最大不重叠数的最小化

Question

我正在寻找一个有效的解决方案，从矩阵中选择不重叠的值，而不考虑成本的最小化。匈牙利算法通过选择一个代价最小的组合来解决指派问题。然而，我想要一个最大值的最小化。

    J1 J2 J3
w1 | 5  4  5 |
w2 | 3  2  5 |
w3 | 1  5  2 |

匈牙利人会选择

W3 --> J1 = 1
W2 --> J2 = 2
W1 --> J3 = 5

总成本=1+2+5=8

但是，最大值为5。

我希望将组合选择为

W1 --> J2 = 4
W2 --> J1 = 3
W3 --> J3 = 2

所以我想要的输出是：4,3,2

而不是成本最小化。我想选择一个最小最大数量的组合。

Answer 1

你会选择MIP模型吗？

如果将矩阵a表示为x_ij,添加二进制变量x_ij表示元素是否被选中,并添加k作为最大选定值,则以下操作将起作用(i和j是行和列索引）：

最大化K以

<代码>%1。∑(j∈j)x_ij=1,xi∈I（每行一个元素）

<代码>2。∑(i∈i)x_ij=1,hxj∈J（每列一个元素）

<代码>3。k≤A_ij*x_ij,xii∈I,hixj∈J(k小于或等于每个选定元素）

MiniZinc中的一个实现（使用给定的数据）：

int: Items = 3;

set of int: ITEM = 1..Items;

array[ITEM, ITEM] of int: A = [| 5, 4, 5
                               | 3, 2, 5 
                               | 1, 5, 2 |];
  
array[ITEM, ITEM] of var 0..1: x;

var int: k;

constraint forall(i in ITEM)
    (sum(j in ITEM)(x[i, j]) = 1);

constraint forall(j in ITEM)
    (sum(i in ITEM)(x[i, j]) = 1);

constraint forall(i, j in ITEM)
    (k >= A[i, j] * x[i, j]);

solve minimize k;

output ["k=\(k)\n"] ++ 
["x="] ++ [show2d(x)];

给出：

k=4
x=[| 0, 1, 0 |
     1, 0, 0 |
     0, 0, 1 |]