minimization of maximized non-overlapping numbers from matrix

Question

I am looking for an efficient solution which select non overlapping value from a matrix irrespective of minimization of cost. Hungarian algorithm solved the assignment problem by choosing a combination which gives minimum cost. However I want the minimization of a maximized number.

for example:

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

Hungarian will choose

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

Total cost = 1+2+5 = 8

However the maximum number is 5.

I want the combination to be selected as

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

Total cost = 4+3+2 = 9

But the maximum number is 4.

So my desired output is: 4, 3, 2

Instead of minimization of cost. I want to select a combination with minimum of maximum number.

Answer 1

Would a MIP-model be an option for you?

If you denote your matrix A, add binary variables x_ij denoting if an element is selected or not and k as the maximum selected value, the following would work (i and j being the row and column indices):

maximize k subject to

1. Σ(j ∈ J) x_ij = 1, ∀i ∈ I (one element from each row)

2. Σ(i ∈ I) x_ij = 1, ∀j ∈ J (one element from each column)

3. k ≤ A_ij * x_ij, ∀i ∈ I, ∀j ∈ J (k is less than or equal to each selected element)

An implementation in MiniZinc (using the given data):

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)];

Gives:

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