1
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ Your rules don't say anything about preferences or ratings. Do you want to take them into account in some way? If so, how? $\endgroup$ – Yoshio Okamoto Apr 13 '11 at 13:38
  • $\begingroup$ 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 $\endgroup$ – Tom O'Connor Apr 13 '11 at 13:58
  • $\begingroup$ Ratings are defined externally, but modified as part of the bin preference thing, so secondary bin choices cause a reduction in rating. $\endgroup$ – Tom O'Connor Apr 13 '11 at 13:58
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Apr 13 '11 at 15:54
  • 1
    $\begingroup$ How on earth has this question generated so much new interest? $\endgroup$ – Tom O'Connor Feb 7 '12 at 14:12
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ See this chat for some more info: chat.stackexchange.com/transcript/message/824645#824645 $\endgroup$ – Chris S Apr 13 '11 at 13:37
  • $\begingroup$ I have seen the transcript, but your goal is still unclear. Also, how exactly do you compute the rating of each bin? $\endgroup$ – Massimo Cafaro Apr 13 '11 at 14:02
  • $\begingroup$ Total Rating(Bin) = Sum(ItemsInBin.Rating) $\endgroup$ – Tom O'Connor Apr 13 '11 at 14:05

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.