<p>As far as I can see, the value of each item depends on which bin it is added to. Its full quality if it is added to its primary preference, and a reduced quality (reduced by -0.5 and -1, respectively) for its secondary and tertiary preferences. Do I understand you correctly?</p>

<p>In this case, this problem can be formulated as a <a href="http://en.wikipedia.org/wiki/Minimum-cost_flow_problem" rel="nofollow">min-cost flow problem</a>, which resembles min-cost bipartite matching (but with the added twist of bin capacity). I.e., it is not an NP-hard bin packing problem at all (unless P=NP).</p>

<p>Construct a flow network with a source, a sink, and two "layers" of nodes, corresponding to the items (first layer) and bins (second layer). Add edges from the source to the items (zero cost, capacity 1) and from the bins to the sink (zero cost, capacity equal to the bin capacity, i.e., from 1 to 3). From each item, you add an edge to each of its primary, secondary and tertiary bins, with capacity 1 and a cost of its adjusted quality multiplied by -1 (to go from a positive value to a negative cost).</p>

<p>Now just run a standard min-cost-flow (or min-cost max-flow) algorithm to get your answer.</p>

<p>Of course, not all items will be matched if the total capacity is less than the number of items, but the match will produce the matching that gives the greatest total (adjusted) quality.</p>

<p>If you don't want to muck about with min-cost flow, you could split each bin node into multiple nodes (the number of nodes corresponding to the bin capacity), and duplicate the edges from the items. So if an item has an edge with a given cost to a bin node with a capacity of 3, you'd now have 3 bin nodes, and that item would have an edge to each of them with the given cost. You could then just use an algorithm for min-cost bipartite matching, such as the <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm" rel="nofollow">Hungarian algorithm</a>. (You will now no longer have a source or a sink, of course.)</p>

<p>This latter version is probably more practical to implement, and libraries for the Kuhn-Munkres algorithm are available in multiple languages.</p>

CC BY-SA 3.0
2012-02-07T10:15:47.673Z
2012-02-08T09:51:56.507Z
2012-02-08T09:51:56.507Z
Magnus Lie Hetland
<p>This appears to be a variant of a problem usually called "Bin packing". It is not clear from your description the goal of your algorithm. Are you interested in maximizing the sum of the ratings of the items in the bins, in maximizing the rating of the bins themselves, in minimizing the number of bins used or something else?</p>

CC BY-SA 3.0
2011-04-13T13:37:50.153Z
See this chat for some more info: http://chat.stackexchange.com/transcript/message/824645#824645
Chris S
CC BY-SA 3.0
2011-04-13T14:02:15.097Z
I have seen the transcript, but your goal is still unclear. Also, how exactly do you compute the rating of each bin?
Massimo Cafaro
CC BY-SA 3.0
2011-04-13T14:05:44.213Z
Total Rating(Bin) = Sum(ItemsInBin.Rating)
Tom O'Connor
CC BY-SA 3.0
2011-04-13T13:34:15.573Z
2011-04-13T13:34:15.573Z
Massimo Cafaro
<p>Despite the warning from the StackExchange Question engine that this question appears subjective, I'm going to ask it anyway.</p>

<p>We have a script as part of an application at work which is responsible for sorting items into bins.  (Sounds simple, right?)</p>

<p>There are X items and Y bins.  Each Item has a Primary, Secondary and Tertiary preferential bin.  It also has an overall rating which corresponds to the item's overall quality, as well as the bin preference (rating is adjusted by -0.5, -1 for decreasing bin preference).</p>

<p>All item's ratings are probably different, and this affects the rating of each bin, and also an overall rating of all bins.</p>

<p>The ordering of items and their preferences into according bins is also important, i.e. Bin A containing Item1 and Item2, may have a different rating overall to Bin B containing Item1 and Item2.</p>

<p>Rules:</p>

<ul>
<li>Each bin can contain between 1 and 3 items.</li>
<li>Any one item can only appear once in each bin, and can only appear in one bin.</li>
</ul>

<p>Initially, we thought it was a knapsack problem, or possibly a multiple knapsack problem, but after researching each, we're not sure that any of the common algorithms for that problem fits our task.</p>

<p>We currently brute force it, but given that the Item pool contains 50 items, and the number of Bins is about 10, the runtime for a single bruteforce run is in the order of tens of seconds.  We'd like to get this down to 0.5s</p>

<p>So basically, has anyone come across this problem before, and does it have a name (that we can search academic papers with)?</p>

CC BY-SA 3.0
2011-04-13T13:38:04.680Z
Your rules don't say anything about preferences or ratings. Do you want to take them into account in some way? If so, how?
Yoshio Okamoto
CC BY-SA 3.0
2011-04-13T13:58:08.087Z
An item can only appear in a bin which is one of its preferences, so if primary = A, secondary =B, tertiary = C, then it can only ever be in bins A,B or C, and never in bin D
Tom O'Connor
CC BY-SA 3.0
2011-04-13T13:58:52.580Z
Ratings are defined externally, but modified as part of the bin preference thing, so secondary bin choices cause a reduction in rating.
Tom O'Connor
CC BY-SA 3.0
2011-04-13T14:06:49.113Z
Thanks. Your problem looks more like a bipartite matching problem, but still let me ask a question to make the problem specification clear. In your example at hand with 50 items and 10 bins, it's impossible to fit all items into the bins. Then, what have you searched?
Yoshio Okamoto
CC BY-SA 3.0
2011-04-13T14:27:34.483Z
It's ok if all of the bins contain at least one item. We can assume that from a Set of Items, there will be enough Items to place at least 1 Item into each Bin, but we expect that by the end, each Bin will contain 2-3 Items.
Tom O'Connor
CC BY-SA 3.0
2011-04-13T14:30:42.907Z
Thank you. Then, how does the rating of bins come into play?
Yoshio Okamoto
CC BY-SA 3.0
2011-04-13T15:11:40.440Z
The rating of the Bin determines whether adding an Item is going to benefit the rating of that Bin.  I.e. BinRating=4, ItemRating =-1, If we add that Item, BinRating drops by 1, If we added Item2, where Item2Rating was +1, then we'd be in a better state than before..
Tom O'Connor
CC BY-SA 3.0
2011-04-13T15:54:42.900Z
The problem is still confusing. You appear to have the following. For each item, an ordered list of upto 3 bins in decreasing preference, and a global rating. Your goal appears to be to assign items to bins to maximize the total rating of each bin, subject to the preference constraints. The problem with this formulation thus far is that since each item has to be assigned, the total cost is merely the sum of costs of each item, which is fixed. For your problem to make sense, the "value" when assigning an item to a bin must depend on BOTH item AND bin, which I'm not seeing.
Suresh Venkat
CC BY-SA 3.0
2011-04-13T23:26:12.847Z
It seems more like an allocation optimization problem than sorting.
Kaveh
CC BY-SA 3.0
2011-04-14T00:26:37.560Z
@Suresh: As far as I understand, there can be an unassigned item. But still I don't see what to be optimized.
Yoshio Okamoto
CC BY-SA 3.0
2011-04-14T00:35:58.343Z
@Tom: Do you need an exact solution, or will an approximation do? If so, it seems that you could directly use simulated annealing, though there may be a more efficient algorithm.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-14T11:59:54.550Z
Firstly, thanks to everyone for your comments and suggestions.  At the moment, we're investigating the Hungarian Algorithm for this, as it seems to actually be a bipartite matching problem.
Tom O'Connor
CC BY-SA 3.0
2012-02-07T12:44:23.840Z
I'm not sure I fully understand the problem, but perhaps you may use Gale and Shapley's algorithm for the stable marriage problem: http://en.wikipedia.org/wiki/Stable_marriage_problem
Shir
CC BY-SA 3.0
2012-02-07T14:12:19.877Z
How on *earth* has this question generated so much new interest?
Tom O'Connor
<ds.algorithms><optimization><terminology><application-of-theory>
Bin allocation problem
Tom O'Connor
# Bin allocation problem

(Asked by: username_0 on 2011-04-13)

Despite the warning from the StackExchange Question engine that this question appears subjective, I'm going to ask it anyway.

We have a script as part of an application at work which is responsible for sorting items into bins. (Sounds simple, right?)

There are X items and Y bins. Each Item has a Primary, Secondary and Tertiary preferential bin. It also has an overall rating which corresponds to the item's overall quality, as well as the bin preference (rating is adjusted by -0.5, -1 for decreasing bin preference).

All item's ratings are probably different, and this affects the rating of each bin, and also an overall rating of all bins.

The ordering of items and their preferences into according bins is also important, i.e. Bin A containing Item1 and Item2, may have a different rating overall to Bin B containing Item1 and Item2.

Rules:

* Each bin can contain between 1 and 3 items.
* Any one item can only appear once in each bin, and can only appear in one bin.

Initially, we thought it was a knapsack problem, or possibly a multiple knapsack problem, but after researching each, we're not sure that any of the common algorithms for that problem fits our task.

We currently brute force it, but given that the Item pool contains 50 items, and the number of Bins is about 10, the runtime for a single bruteforce run is in the order of tens of seconds. We'd like to get this down to 0.5s

So basically, has anyone come across this problem before, and does it have a name (that we can search academic papers with)?

**Tags:** ds.algorithms, optimization, terminology, application-of-theory

> **Comments:**
> **username_1**: Your rules don't say anything about preferences or ratings. Do you want to take them into account in some way? If so, how?  
> **username_0**: An item can only appear in a bin which is one of its preferences, so if primary = A, secondary =B, tertiary = C, then it can only ever be in bins A,B or C, and never in bin D  
> **username_0**: Ratings are defined externally, but modified as part of the bin preference thing, so secondary bin choices cause a reduction in rating.  
> **username_1**: Thanks. Your problem looks more like a bipartite matching problem, but still let me ask a question to make the problem specification clear. In your example at hand with 50 items and 10 bins, it's impossible to fit all items into the bins. Then, what have you searched?  
> **username_0**: It's ok if all of the bins contain at least one item. We can assume that from a Set of Items, there will be enough Items to place at least 1 Item into each Bin, but we expect that by the end, each Bin will contain 2-3 Items.  
> **username_1**: Thank you. Then, how does the rating of bins come into play?  
> **username_0**: The rating of the Bin determines whether adding an Item is going to benefit the rating of that Bin.  I.e. BinRating=4, ItemRating =-1, If we add that Item, BinRating drops by 1, If we added Item2, where Item2Rating was +1, then we'd be in a better state than before..  
> **username_2**: The problem is still confusing. You appear to have the following. For each item, an ordered list of upto 3 bins in decreasing preference, and a global rating. Your goal appears to be to assign items to bins to maximize the total rating of each bin, subject to the preference constraints. The problem with this formulation thus far is that since each item has to be assigned, the total cost is merely the sum of costs of each item, which is fixed. For your problem to make sense, the "value" when assigning an item to a bin must depend on BOTH item AND bin, which I'm not seeing.  
> **username_3**: It seems more like an allocation optimization problem than sorting.  
> **username_1**: @Suresh: As far as I understand, there can be an unassigned item. But still I don't see what to be optimized.  
> **username_4**: @Tom: Do you need an exact solution, or will an approximation do? If so, it seems that you could directly use simulated annealing, though there may be a more efficient algorithm.  
> **username_0**: Firstly, thanks to everyone for your comments and suggestions.  At the moment, we're investigating the Hungarian Algorithm for this, as it seems to actually be a bipartite matching problem.  
> **username_5**: I'm not sure I fully understand the problem, but perhaps you may use Gale and Shapley's algorithm for the stable marriage problem: http://en.wikipedia.org/wiki/Stable_marriage_problem  
> **username_0**: How on *earth* has this question generated so much new interest?  

---

## 2 answers

### Answer by username_6 on 2012-02-07. Score: 3 | Accepted answer

As far as I can see, the value of each item depends on which bin it is added to. Its full quality if it is added to its primary preference, and a reduced quality (reduced by -0.5 and -1, respectively) for its secondary and tertiary preferences. Do I understand you correctly?

In this case, this problem can be formulated as a [min-cost flow problem](http://en.wikipedia.org/wiki/Minimum-cost_flow_problem), which resembles min-cost bipartite matching (but with the added twist of bin capacity). I.e., it is not an NP-hard bin packing problem at all (unless P=NP).

Construct a flow network with a source, a sink, and two "layers" of nodes, corresponding to the items (first layer) and bins (second layer). Add edges from the source to the items (zero cost, capacity 1) and from the bins to the sink (zero cost, capacity equal to the bin capacity, i.e., from 1 to 3). From each item, you add an edge to each of its primary, secondary and tertiary bins, with capacity 1 and a cost of its adjusted quality multiplied by -1 (to go from a positive value to a negative cost).

Now just run a standard min-cost-flow (or min-cost max-flow) algorithm to get your answer.

Of course, not all items will be matched if the total capacity is less than the number of items, but the match will produce the matching that gives the greatest total (adjusted) quality.

If you don't want to muck about with min-cost flow, you could split each bin node into multiple nodes (the number of nodes corresponding to the bin capacity), and duplicate the edges from the items. So if an item has an edge with a given cost to a bin node with a capacity of 3, you'd now have 3 bin nodes, and that item would have an edge to each of them with the given cost. You could then just use an algorithm for min-cost bipartite matching, such as the [Hungarian algorithm](http://en.wikipedia.org/wiki/Hungarian_algorithm). (You will now no longer have a source or a sink, of course.)

This latter version is probably more practical to implement, and libraries for the Kuhn-Munkres algorithm are available in multiple languages.


---

### Answer by username_7 on 2011-04-13. Score: 1

This appears to be a variant of a problem usually called "Bin packing". It is not clear from your description the goal of your algorithm. Are you interested in maximizing the sum of the ratings of the items in the bins, in maximizing the rating of the bins themselves, in minimizing the number of bins used or something else?

> **Comments:**
> **username_8**: See this chat for some more info: http://chat.stackexchange.com/transcript/message/824645#824645  
> **username_7**: I have seen the transcript, but your goal is still unclear. Also, how exactly do you compute the rating of each bin?  
> **username_0**: Total Rating(Bin) = Sum(ItemsInBin.Rating)  

---

