I have a problem formulation but it does not resemble the usual packing problem I find in the literature but it is a usual problem in the packing industry. I just do not know the name for it.

The problem formulation is as follows: I have a certain amount of objects with different weights (around 10000 objects with a weight between 1-4) and I want to pack them in boxes (around 100 to 200 boxes with a maxium weight of around 200). The objective is that all boxes should have the same weight (at least within a prefefined boundary). It is not mandatory that all objects are distributed.

How can I formulate this optimization problem (objective function, constraints etc.) and what algorithms may suitable to solve this problem?

  • 3
    This sounds like a Multiple knapsack problem. – Bart van Ingen Schenau Feb 22 at 13:27
  • Since you don't mention the objects' dimensions, are they the same for all objects? – Flater Feb 22 at 13:54
  • 3
    The problem description looks pretty unclear to me. Please clarify: (1) is the number of boxes fixed or subject to change? (2) What is the objective function you want to minimize? How do you measure precisely the deviation from "all boxes have the same weight"? (3) If there are non-distributed objects left, how are those taken into account in the former objective function? – Doc Brown Feb 22 at 20:57
  • 1
    This sounds like a Linear Programming (LP) problem, so a linear problem solver/optimiser may be helpful here. However, as Doc Brown mentions, you need to start by describing which parameters you're working with and particularly describe your bounds/constraints (e.g. breakdown and range of object weights, max permitted weight per box, etc), otherwise the solution will tend toward infinity (or a very high number). e.g. if the max weight for a box is unlimited then your optimal solution might just put all 10000 objects into the same box. – Ben Cottrell Feb 23 at 0:36
  • 3
    ... or the other extreme, take an arbitrary number of boxes and don't put any objects into them - all boxes have the same content weight - zero. – Doc Brown Feb 23 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.