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.