Column Generation Approach to the Multiple Problem with Color Contraints

In this paper, we study a new problem which we refer to as the multiple knapsack with color constraints (MKCP). Motivated by a real application from the steel industry, the MKCP can be formulated by generalizing the multiple knapsack problem along two directions: (i) adding assignment restrictions on items which can be assigned to a knapsack, (ii) adding a new attribute (called "color" in the paper) to an item and then adding the associated "color" constraints which restrict the number of distinct colors which can be assigned to a knapsack to two. These generalizations make the problem computationally difficult to solve to optimality in practice as well as in theory. A real life instance (called mkc) of this problem class is available through MIPLIB and a larger instance (mkcp) is downloadable from the IBM Deep Computing Institute
The focus of this paper is to present computational results for the two mentioned instances of this
problem. We present the original (natural) formulation for the problem then reformulate it and use column generation to solve it. The column generation problem is modeled and solved as a knapsack problem with color constraints. We solve mkc to optimality and use Dantzig-Wolfe decomposition for lower bounding the &her instance. Solving mkc to optimality took less time than it takes to solve the LP relaxation of the original formulation. The larger instance is solved to near-optimality (within .7% of optimality) in a fraction of the time required to solve the original relaxed LP.