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.

A branch-and-price algorithm for the capacitated p-median problem / A. Ceselli, G. Righini. - In: NETWORKS. - ISSN 0028-3045. - 45:3(2005), pp. 125-142.

A branch-and-price algorithm for the capacitated p-median problem

A. Ceselli
Primo
;
G. Righini
Ultimo
2005

Abstract

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.
Branch-and-price; Column generation; Integer programming; p-median
Settore MAT/09 - Ricerca Operativa
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/4697
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 58
  • ???jsp.display-item.citation.isi??? 48
social impact