矩阵中最大化非重叠数的最小化

Question

我正在寻找一种有效的解决方案，该解决方案 select 不考虑成本最小化的矩阵中的非重叠值。匈牙利算法通过选择给出最小成本的组合来解决分配问题。但是我想要最大化数字的最小化。

例如：

    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。

我希望组合select编辑为

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

总成本 = 4+3+2 = 9

但是最大数量是4。

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

而不是成本最小化。我想 select 一个最大数和最小数的组合。

Answer 1

MIP 模型是否适合您？

如果你表示你的矩阵 A，添加二进制变量 x_ij 表示是否选择了一个元素和 k 作为最大选择值，以下将起作用（i 和 j 是行和列索引):

最大化 k 服从

1. Σ(j ∈ J) x_ij = 1, ∀i ∈ I（每行一个元素）

2. Σ(i ∈ I) x_ij = 1, ∀j ∈ J（每列一个元素）

3. k ≤ A_ij * x_ij, ∀i ∈ I, ∀j ∈ 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 |]

矩阵中最大化非重叠数的最小化

minimization of maximized non-overlapping numbers from matrix

algorithm

matrix

mathematical-optimization