Search code examples
algorithmpacking

Packing problem

I have the following problem:

  1. I have a given number of identically formed items with different colors (I know how many there are from each color)
  2. I pack these items into boxes that can hold each a given number (n) of item in such way that I use the minimum number of boxes: round_up(total_nr_of_items/n)
  3. There are some colors I am not allowed to put in one box except if I can't otherwise have the ideal number of boxes.
  4. There is a minimal number of items from each color (different for each color) that I'm allowed to put in a box. That is I can decide to put 0 pcs. of a color into a box or a minimum of k pcs. or above. This constraint can also be broken (as few times as possible) if the packing could not be done with the minimum number of boxes.
  5. I want to find a solution where as few colors as possible are split between boxes.

I think this is a kind of packing problem but I don't know which one.

Please suggest into which packing problem can the above be converted into and/or an algorithm that I could use to solve this problem.

Solution

  • Looks like an NP-Hard constraint satisfaction problem. You'll have hard and soft constraints something like this.

    Build-in constraints:

    • I have a given number of identically formed items with different colors (I know how many there are from each color)

    Hard constraints:

    • There are some colors I am not allowed to put in one box.

    • There is a minimal number of items from each color (different for each color) that I'm allowed to put in a box. That is I can decide to put 0 pcs. of a color into a box or a minimum of k pcs. or above.

    Soft constraints:

    • I pack these items into boxes that can hold each a given number (n) of item in such way that I use the minimum number of boxes: round_up(total_nr_of_items/n)

    Softer constraints (or really low weight soft constraints):

    • I want to find a solution where as few colors as possible are split between boxes.

    For algorithms to solve this, take a look at Simulated annealing, Tabu search, Branch and bound, ...

    For software which implements such algorithms and support constraints, take a look at Drools Planner (java, open source).