𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Alberto Ceselli; Giovanni Righini

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
178 KB
Volume
45
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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. Β© 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 125–142 2005

πŸ“œ SIMILAR VOLUMES

A branch-and-price algorithm for a hiera
A branch-and-price algorithm for a hierarchical crew scheduling problem
✍ Diego B.C. Faneyte; Frits C.R. Spieksma; Gerhard J. Woeginger πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 122 KB πŸ‘ 1 views

## Abstract We describe a real‐life problem arising at a crane rental company. This problem is a generalization of the basic crew scheduling problem given in Mingozzi et al. [18] and Beasley and Cao [6]. We formulate the problem as an integer programming problem and establish ties with the integer

A branch-and-cut algorithm for the preem
A branch-and-cut algorithm for the preemptive swapping problem
✍ Charles Bordenave; Michel Gendreau; G. Laporte πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 247 KB πŸ‘ 1 views

## Abstract In the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determinin