The p-dimensional vector bin packing problem, also called general assignment problem, is a generalization of bin packing with multiple constraints. In this problem, we are required to pack n items of m different types, represented by p-dimensional vectors, into as few bins as possible. By means of reductions to vector packing, several cutting & packing problems, including the one-dimensional bin packing and cutting stock problems, can be solved.
The MIP models are being solved using COIN-OR CBC (an open-source MIP solver) on AWS Lambda. Much better run times can be achieved using Gurobi or CPLEX.
Help
Solution method
VPSolver is a multiple-choice vector packing solver based on an arc-flow formulation with graph compression [PhD Thesis] [Poster] [Paper] [BibTeX].
By means of reductions to vector packing, VPSolver can be used to solve several problems such as:
- Bin packing;
- Cutting stock;
- Cardinality constrained bin packing;
- Cutting stock with cutting knife limitation;
- Bin packing with conflicts;
- Cutting stock with binary patterns;
- Cutting stock with binary patterns and forbidden pairs.
- [Computational results on several benchmark test data sets]
By means of reductions to multiple-choice vector packing, VPSolver can be used to solve several problems such as:
- Variants of the problems from the list above that consider multiple bin types;
- Variable-sized bin packing (as an one-dimensional multiple-choice vector bin packing problem).
VPSolver includes a python interface that allows modeling other problems easily. Using the python interface, VPSolver can be used to solve problems such as:
- Many variants that happen in the industry that include cutting and packing problems as subproblems of a larger production planning problem;
- Multi-stage variants (e.g, two- and three-stage two-dimensional cutting stock problems);
- Multi-period variants (e.g., plan the production for several days with the possibility of delaying or anticipating the production of some items).
Note: Suggestions of other cutting & packing problems (including industrial applications) are welcome! [Contact]