Design of capacitated networks with tree configurations

Cited 33 time in webofscience Cited 0 time in scopus
  • Hit : 572
  • Download : 53
This paper considers the problem of designing a capacitated network with a tree configuration (CTP). For a given set of nodes with their capacities, k types of link facilities with various characteristics, acid installation cost for connecting each pair of nodes using each type of link facility, the problem is to find a tree network which satisfies the given traffic requirements between all pairs of nodes and minimizes total installation cost. We formulate (CTP) as an integer programming problem using path variables. To solve the linear programming relaxation which has exponentially many variables, we develop a polynomial-time column generation procedure. Moreover, to tighten the formulation, an efficient preprocessing procedure is devised and some classes of valid inequalities are found. Using the results, we develop a branch-and-cut algorithm with column generation where an efficient branching rule is adopted. Computational results show that the algorithm can solve practically-sized problems to optimality within a reasonable time.
Publisher
BALTZER SCI PUBL BV
Issue Date
1996
Language
English
Article Type
Article
Description

The authors wish to thank anonymous referees for their helpful comments.

Keywords

TOPOLOGICAL DESIGN; OPTIMIZATION; ALGORITHMS

Citation

TELECOMMUNICATION SYSTEMS, v.6, no.1, pp.1 - 19

ISSN
1018-4864
URI
http://hdl.handle.net/10203/7554
Appears in Collection
IE-Journal Papers(저널논문)
Files in This Item
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 33 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0