Bin packing with conflicts: A generic branch-and-price algorithm

摘要

The bin packing problem (BPP) has items of different sizes/weights that are to be packed into a minimum number of identical bins of given capacity. If conflicts are include the it is denoted by BPPC and a graph is given where nodes represent items and edges represent conflicts between pairs of items. The problem then is a combination of the bin packing problem and the vertex coloring problem. Examples of its applications are examination scheduling, parallel computing and database storage, and product delivery. The special case arises for instance in the mutual exclusion scheduling problem in which all items or tasks are represented by time intervals associated to their schedule, and a conflict between tasks arises when the associated intervals overlap an instance of such a case being workforce planning. Many computational studies have been published in this area. This paper shows how the BPPC can be solved using a generic branch-and-price algorithm using the generic platform, BaPCod. The pricing sub-problem is a knapsack problem with conflicts (KPC) that is solved using a branch-and-bound oracle for a general graph.