Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1163.90381
Agarwal, Yogesh K.
Design of capacitated multicommodity networks with multiple facilities. (English)
[J] Oper. Res. 50, No. 2, 333-344 (2002). ISSN 0030-364X; ISSN 1526-5463/e

Summary: This paper addresses the problem of designing a multicommodity network using several facilities with different costs and capacities. The problem is addressed in a special context of designing private telecommunications networks using Fractional-T1 services. The algorithm starts from any given solution of the problem and gradually improves it by solving a series of subproblems, arriving at a local minimum. The subproblem is defined over a subset of links, called the subnetwork, by using one of the links as the base link. It is shown that the subproblem can be formulated as a multiple choice knapsack problem that is solved by dynamic programming. Computational results and lower bounds are reported on problems of up to 20 nodes and up to 3 facilities. On most problems, the algorithm produces solutions within about 5\% of lower bound on the average. Although it was not possible to compute lower bounds for larger problems, heuristic solutions and running times are reported for problems of up to 99 nodes and four facilities.

MSC 2000:: *90B10 Flows in networks
90C35 Network programming
90B18 Communication networks
90C39 Dynamic programming

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]