Binary Decision Diagrams for Bin Packing with Minimum Color Fragmentation

11/30/2018
by   David Bergman, et al.
0

Bin Packing with Minimum Color Fragmentation (BPMCF) is an extension of the Bin Packing Problem in which each item has a size and a color and the goal is to minimize the sum of the number of bins containing items of each color. In this work, we introduce BPMCF and present a decomposition strategy to solve the problem, where the assignment of items to bins is formulated as a binary decision diagram and an optimal integrated solutions is identified through a mixed-integer linear programming model. Our computational experiments show that the proposed approach greatly outperforms a direct formulation of BPMCF and that its performance is suitable for large instances of the problem.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset