always_first's blog

Optimization problem in table
By always_first, history, 10 years ago, translation, In English

Hi everybody!

Recently I've learned hungarian algorithm for solving the assignment problem, Now I'm curious about how to solve more general problem: for given n × m table select several numbers, maximizing their sum with following constraints: in each row the number of selected numbers is not less than Rmin and not more than Rmax, and for each column the number of selected numbers is not less than Cmin and not more than Cmax.

If Rmin = Rmax = 1 and Cmin = Cmax = 1 this is the standard assignment problem. But what can we say about more general case? Any ideas about this (maybe, at least in case Rmin = Rmax = R, Cmin = Cmax = C)? Any thoughts would be greatly appreciated.

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by always_first (original revision, translated revision, compare)

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

In the case Rmin = Rmax = Cmin = 1, and general Cmax the problem reduces to Generalized assignment problem, which is NP-hard (and hard to approximate). I don't expect it to get any easier for general values of the bounds.

However, this kind of problems are usally simple to transform to Integer Program, so if you're instance is not big you can hope to get an exact solution using a good MIP solver

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Reduction is not correct since the problem you mentioned has a more strong weight constraint: "sum of costs of tasks cannot exceed the budget of an agent". In our case all weights in this constraint are equal to 1.

    → Reply
»
10 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Isn't it a simple minimum cost LR-flow problem? Consider the classical bipartite graph where rows correspond to the left part and columns correspond to the right part, and there exist edges 

(r -> c, cost = A[r][c], 0 <= flow <= 1)    for each row r, column c
(s -> r, cost = 0, R_min <= flow <= R_max)  for each row r
(c -> t, cost = 0, C_min <= flow <= C_max)  for each column c
→ Reply