Polyhedral Analysis for the Uncapacitated Hub Location Problem with Modular Arc Capacities

Hande Yaman (hyamanbilkent.edu.tr)

Abstract: We consider the problem of installing a two-level telecommunication network. Terminal nodes communicate with each other through hubs. Hubs can be installed on terminal nodes and they are interconnected by a complete network. Each terminal is connected to a hub node by direct links. The aim is to minimize the cost of installing hubs and links. We present valid and facet defining inequalities for this problem.

Keywords: hub location, polyhedral analysis, lifting

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

Category 2: Combinatorial Optimization (Polyhedra )

Citation: SIAM Journal on Discrete Mathematics, Vol. 19, 501-522, 2005.

Download:

Entry Submitted: 11/18/2004
Entry Accepted: 11/18/2004
Entry Last Modified: 11/08/2005

Modify/Update this entry