wired's blog

Bin Packing with Multiple bins and limitations on bin capacity
By wired, history, 3 years ago, In English

Can some one help me with bin packing problem with constraints on bin limit and with multiple bins.

Constraints:

  bin capacity <= 100
  no of bins <= 500
  no of items <= 5,000

Is it possible to do so (approx.) using some clustering algorithms??
  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Apparently it's an NP-hard problem.

If that's not the problem you're trying to solve, you need to elaborate more.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

It is an NP-hard problem. You can see it as a flow problem with bounds, but not in the traditional sense, you need a minimum flow over the sum of flows of edge sets . If you are interested in solving it with that idea, you can consult Carvalho (1998, 2002) and his solution to the Cutting Stock Problem or Pessoa et al. (2020). btw, one of the first to talk about efficient solutions for this problem was Martello (and Toth) in his book Knapsack problems, he maintains a page with other researchers that may interest you. bpplib

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The new question that you propose is not very clear, perhaps you could search in the 1D-BPP literature about the dominance criterion (perhaps it is understood as clustering), also if you are interested in approximate solutions beyond heuristics or lagrange relaxations you can search in Vance (1994) and the relationship between the column generation algorithm and the modified integer round-up property.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Keep in mind that in the link that I shared there are codes and executables available.

    → Reply