Resource-Constrained Assignment Problems with Shared Resource Consumption and Flexible Demand

This paper considers a very general class of customer-to-resource assignment problems relevant to a variety of manufacturing contexts. This problem class addresses settings in which subsets of customer types share resource capacities as well as a fixed amount of capacity consumption, independent of production volume. More broadly, our model addresses cross-facility production limits and shared capacity consumption within each customer type. To solve these large-scale optimization problems, we apply a branch-and-price solution approach. This approach relies on an effective solution method for a novel class of nonlinear knapsack pricing problems. As our computational results demonstrate, despite the fact that the resulting master problem is not a simple set-partitioning problem, the problem's relaxation is sufficiently tight to produce an algorithm that significantly outperforms CPLEX for a wide range of problem parameter settings.