[Solved]: Is this an instance of a well-known problem?

Problem Detail: 

Context

I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I would like to get some feedback. Below you will find an abstract version of the problem.

The Problem

Input:

• A bag of colored balls. A ball may have many colors (e.g. red, blue and yellow) or only one (e.g. green). Each ball has also a score. Since we are talking about a bag, elements may be repeated.
• A set of colored boxes, one per color. Each box is labeled with a natural number.

Problem: each colored box must be filled with the exact amount of balls specified by its label.

Constraints:

• The color of the balls in a box must match the color of the box (e.g. a green ball goes in a green box).
• A ball of many colors can be assigned to a box of any of those colors (e.g. a ball that is both red and green can either go in a red box or in a green one).

The solution to the problem can be represented by the following information: for each box, a list of the balls it contains (a ball is represented as a list of colors and a score).

Output of the algorithm: the solution with the highest score. The score of a solution is the sum of the scores of all balls in the boxes (of course, there may be many solutions, but in that case we just pick one of them).

Current research

Somehow this problem makes me think of Sudoku, which is an instance of the exact cover problem. However, I haven't been able to come up with a way to model this problem in terms of exact cover and am afraid I may be missing a more straightforward approach.

As suggested in the answers, another possibility would be to model this using max-flow. However, this approach is unable to generate all possible solutions such that each box is filled to its capacity. Furthermore, the max flow value is known to be the sum of the capacities of the boxes (it is assumed the number of balls is large enough for this to happen).

Questions

Is this an instance of the exact cover problem? If yes, how would you model it in terms of exact cover? If no, is it an instance of any other well-known problem?

Asked By : aochagavia

Answered By : Hendrik Jan

Isn't this a case of max-flow?

Model your problem as a bipartite graph, from ball to boxes, with an edge from each ball to the boxes with matching colour. Each of these edges has capacity 1. Now add source and target vertices. From source to each ball with capacity 1. From each box to target, capacity is the capacity of the box.

Now you want to enumerate all solutions to this max-flow problem (i.e., output all flows whose value achieves the maximum possible). But that might be a lot of solutions!

(edit) A recent update has added scores to the balls, and the target is to maximize the scores of the balls that are put into the boxes. I would suggest maximal bipartite matching where you have as many copies of nodes for each box as the capacity of that box. As there will be balls that do not fit into the boxes I would suggest adding boxes for overflow balls (to obtain complete matching, when necessary). Wikipedia suggests the Hungarian algorithm.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59295