# Packing objects into bins to minimize the number of bins

There is a list of objects. Each object cannot be in a bin with some other objects. How can I find the minimum number of bins required to hold all the objects (and the objects in them)?

My current algorithm:

For each object in the list, see if any of the currently existing bins will hold it. If yes, stick it in the first bin we come to that will hold it. If we exhaust the list of bins without finding a bin, create a new bin and stick the object into it.

Will this algorithm find the minimum number of bins? If not, what algorithm will (NP-hard algorithms OK: I have only about 12 objects)?

Feel free to add any tags you think appropriate - I'm not sure which one is

This is the clique cover problem in disguise, and finding an optimal solution NP-hard.

• Any better algorithm than just brute-forcing it?
– dpdt
Jan 23, 2018 at 22:45
• @dpdt It's all about what trade-offs you're willing to make. I think greedily removing a maximal clique (which can be found efficiently) should give pretty good results. Your algorithm should be acceptable most of the time as well. If you insist on only having the optimal solution you're probably going to have to dive into some papers to find something that finishes computing for anything but the smallest cases at all.
– orlp
Jan 23, 2018 at 22:51
• The problem is NP-hard, not the algorithm. Jan 24, 2018 at 7:06

This problem can also be viewed as a graph coloring problem. You basically have a graph of objects, and each objects linked together must have different colors (i.e going to different bins)

In practice, some simple search (such as simulated annealing) is going to give you a pretty good solution for graph coloring. If you insist on the smallest number of bins, you can try constraint programming or similar exact solution techniques.