Tommy Thomadsen
Technical University of Denmark
Thomas Stidsen
Technical University of Denmark
Download article
Published in: Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Linköping Electronic Conference Proceedings 14:27, p.
Published: 2004-12-28
ISBN:
ISSN: 1650-3686 (print), 1650-3740 (online)
Designing hierarchical telecommunication networks pose some very difficult optimization problems. Most solutions today involve sequential solution of a series of easier optimization problems. In this presentation we will present the Hub Location Network Design (HLND) problem. The HLND problem combines the routing problem; the network design problem and the hub selection problem into one problem. The objective is to minimize the link establishment costs and the link capacity costs. We present an ILP model for the HNLD problem. To solve larger instances of the problem we develop a cut-and-price algorithm for the LP problem; which includes additional cuts to tighten the gap. Based on the LP solution IP solutions are generated. In most cases the gap is zero.
The hub location network design problem is related to several wellknown optimization problems: Network design; Generalized Travelling Salesman and Location-Routing. The connection between the HLND problem and these will briefly be discussed.
