A Branch and Price Algorithm for Solving an Integrated Production Planning and Facility Location Problem
We consider an integrated Facility Location and Production Planning Problem (FLPPP) where we must meet the demands of a number of markets in a sequence of future time periods through production and inventory decisions at a set of open facilities. Production costs at an open facility in each period consist of a fixed setup cost if any production takes place and a variable cost per unit produced, while the inventory holding costs are assumed to be linear. In addition, each open facility faces a bound on the number of markets that it may serve. This problem is NP-hard since it generalizes the well-known uncapacitated facility location problem. We propose a set-partitioning formulation of this problem and develop a branch and price algorithm to solve it. The corresponding pricing problem, which we will refer to as the Cardinality Constrained Market Selection Problem (CCMSP), is interesting in its own right. In particular, in this problem we must select a set of markets for which we must meet the corresponding demands in future time periods through production and inventory decisions, while maximizing profit, i.e., the revenue received from the selected markets minus the production and inventory costs. We show that this problem is NP-hard in general. However, we show that the problem is solvable in polynomial time when the demand patterns in the markets follow a common seasonality pattern. In addition, we present a strong LP formulation of the problem that, although not tight in general, often yields integral optimal solutions.