Richard Freling, H. Edwin Romeijn, Dolores Romero Morales, Albert P.M. Wagelmans
A Branch and Price algorithm
for the multi-period single-sourcing problem
In this paper we propose a Branch and Price algorithm for solving multi-period
single-sourcing problems. In particular, we generalize a Branch and Price
algorithm that was developed for the Generalized Assignment Problem (GAP)
to a class of convex assignment problems. We then identify an important
subclass of problems, containing many variants of the multi-period single-sourcing
problem (MPSSP), as well as variants of the GAP, for which we derive an
efficient solution procedure for the pricing problem, a critical factor
in the efficiency of the Branch and Price algorithm. We execute an extensive
numerical comparison between the performance of the Branch and Price algorithm
and the MIP solver of CPLEX for a particular variant of the MPSSP.