5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The output size is exponential if you ask for all solutions. Consider [1000 red balls, 1000 red-green balls, red box for 1000 balls] $\endgroup$ – John Dvorak Jun 6 '16 at 6:10
  • $\begingroup$ @JanDvorak thanks for your comment. I edited the question to change this. Now the goal of the algorithm is to produce an optimal solution based on the score of the balls in the boxes. $\endgroup$ – aochagavia Jun 6 '16 at 7:34
  • 2
    $\begingroup$ You should read up on the topic of chameleon questions... $\endgroup$ – John Dvorak Jun 6 '16 at 7:35
  • $\begingroup$ Would you suggest opening a new question? I have been reading meta.stackexchange.com/questions/43478/… but am unsure how I can use that information to improve my question. $\endgroup$ – aochagavia Jun 6 '16 at 7:38
  • $\begingroup$ What makes you think max-flow is unable to generate all possible solutions? Also, please don't edit your question in a way that invalidates prior/existing answers -- instead, make sure you ask the right question when you originally post, and if you have a new or different question, post it separately. In this case it looks like you have rejected a valid answer for no apparent reason. $\endgroup$ – D.W. Jun 6 '16 at 21:22
6
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ The max-flow gives one possible solution. But it seems like the problem is asking for all possible solutions such that each box is filled to its capacity. So 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. $\endgroup$ – Ashwin Ganesan Jun 6 '16 at 1:53
  • $\begingroup$ @AshwinGanesan your comment is spot on. I will update the question to reflect this. $\endgroup$ – aochagavia Jun 6 '16 at 6:03
  • $\begingroup$ @AshwinGanesan so, we're looking at all-solution max-flow. The problem with this is that the output size can be exponential. $\endgroup$ – John Dvorak Jun 6 '16 at 6:05
3
$\begingroup$

This is an instance of the assignment problem, i.e., finding the maximum-weight matching in a weighted bipartite graph.

On the left side of the bipartite graph, each vertex represents a ball. On the right side, a box labelled with the number $k$ corresponds to $k$ different vertices. You have an edge between a ball and a box if the box's color is one of the colors on the ball. The weight of that edge is equal to the score of the ball.

Now the optimal solution to your problem will be the maximum-weight matching for this bipartite graph, i.e., the solution to the corresponding assignment problem. There are polynomial-time algorithms for the assignment problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.