Bin allocation problem 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)?
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, 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. (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.