(1) DTI - Dipartimento di Tecnologie dellInformazione, Universitá di Milano, Via Bramante 65, 26013 Crema (CR), Italy
Abstract:
The p-median problem has been widely studied in combinatorial optimisation, but its generalisation to the capacitated case has not. We propose a branch and price algorithm, comparing it with a standard MIP solver and a branch and bound algorithm based on Lagrangean relaxation. We present computational experience, using test instances drawn from the literature and new instances with higher ratio between the number of medians p and the number of nodes N. The branch and price algorithm shows very good performances and computational time robustness in solving problems for any
ratio.Received: December 2002, Revised: August 2003AMS classification:
90C10, 90C27