Polyhedral Analysis for Concentrator Location Problems

Martine Labbé (mlabbesmg.ulb.ac.be)
Hande Yaman (hyamansmg.ulb.ac.be)

Abstract: The concentrator location problem is to choose a subset of a given terminal set to install concentrators and to assign each remaining terminal node to a concentrator to minimize the cost of installation and assignment. The concentrators may have capacity constraints. We study the polyhedral properties of concentrator location problems with different capacity structures. We develop a branch and cut algorithm and present computational results.

Keywords: concentrator location, polyhedral analysis, branch and cut

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: To appear in Computational Optimization and Applications.

Download:

Entry Submitted: 07/24/2003
Entry Accepted: 07/24/2003
Entry Last Modified: 08/16/2005

Modify/Update this entry