always_first's blog

Optimization problem in table
By always_first, history, 8 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

»
8 years ago, # |
  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
»
8 years ago, # |
  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
  • »
    »
    8 years ago, # ^ |
      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
»
8 years ago, # |
  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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you enforce a minimum flow on each edge ?

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

      It is described in this topic, also the link to the paper is given.

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

    Thank you! Nice solution.

    Does this solution work for not integer A[r][c] as well? In e-maxx site it is written that costs must be integers.

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

      There is no need for costs to be integer. Min-cost flow doesn't use the fact costs are integral at any moment.

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

        I see, thanks a lot.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Hi. I know this is not related to the topic, but can you point me some good resources for min cost flow algorithms?

        Thanks!

        → Reply