A rule-based arc-flow formulation for the generalized bin packing problem

Optimal solutions to packing problems are of the major importance for industry, companies, and business development nowadays. In the Generalized Bin Packing Problem (GBPP) different size containers can store objects and there is a cost per use. Each object is characterized by its volume and a benefit for being packed. The objects are subdivided into two groups, mandatory and non-mandatory. Mandatory items must be packed regardless their perk, while non-mandatory objects are optional to pack. In GBPP the smallest number of containers must be used, while non-mandatory items must be packed to increase the overall utility.

The arc-flow is an effective pseudo-polynomial formulation for Cutting and Packing problems. Here an edge represents each object, and the size of the object depends on the distance between the departure node and the arrival node. The resulting graph represents all possible combinations of objects and the way they can be located within a container.

In this work, we generate a rule-based digraph that introduces the loss arcs representing the empty space in the containers.