ATM VP-based network design

We consider the problem of designing an ATM VP-based leased line backbone network. Given point-to-point communication demands having predefined sizes in a network, the problem is to find configurations of demand routes and link facilities installed on each edge satisfying all demands at minimum cost...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2004-11, Vol.158 (3), p.555-569
Main Authors: Kang, Jangha, Park, Kyungchul, Park, Sungsoo
Format: Article
Language:English
Subjects:
Algorithms
Asynchronous transfer mode
Bin packing
Column generation
Communications networks
Cutting plane
Integer programming
Linear programming
Operations research
Routing
Studies
Systems design
Telecommunications
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of designing an ATM VP-based leased line backbone network. Given point-to-point communication demands having predefined sizes in a network, the problem is to find configurations of demand routes and link facilities installed on each edge satisfying all demands at minimum cost under some constraints. One of the most important constraints is that a single demand cannot be split over multiple link facilities. This is a sort of bin packing constraint. We propose an integer programming formulation of the problem and an algorithm to solve it. An efficient column generation technique to solve the linear programming relaxation is proposed, and a valid inequality is used to strengthen the integer programming formulation. The algorithm incorporates the column generation technique and the cutting plane approach into a branch-and-bound scheme. We test the proposed algorithm on some real problems. The results show that the algorithm can be used to solve the problems within reasonably small computing times.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(03)00372-2