Premium
A branch‐and‐price algorithm for the capacitated p ‐median problem
Author(s) -
Ceselli Alberto,
Righini Giovanni
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20059
Subject(s) - heuristics , column generation , branch and bound , median , branch and price , computer science , variation (astronomy) , mathematical optimization , branch and cut , mathematics , algorithm , integer programming , geometry , physics , astrophysics
The capacitated p ‐median problem is the variation of the well‐known p ‐median problem in which a demand is associated to each user, a capacity is associated to each candidate median, and the total demand of the users associated to the same median must not exceed its capacity. We present a branch‐and‐price algorithm, that exploits column generation, heuristics and branch‐and‐bound to compute optimal solutions. We compare our branch‐and‐price algorithm with other methods proposed so far, and we present computational results both on test instances taken from the literature and on random instances with different values of the ratio between the number of medians and the number of users. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 125–142 2005