Grouping is encountered frequently in material design problems where an order book is used to create manufacturable units. Typically, these problems can be formulated as variations of bin packing problems. In the standard problem we have to pack a given set of items into as few bins as possible considering a weight constraint.
We study variants with additional assignment constraints for items and bins of certain types. The objective can be to minimize the number of used bins as well as minimizing the unused portions of the bins.
We apply some well known heuristics to these variants and study their performance. Moreover, we develop an approximation algorithm based on a set cover formulation of the problem. The performance of the method is discussed in a worst case study and some computational results for real world problem instances.
The algorithms are designed and implemented to fit into the framework of a workbench for rapid prototyping of optimization problems.
Selected References:
Henning Biermann, biermann@cs.nyu.edu