Lj. Leblanc et al., TOPOLOGY DESIGN AND BRIDGE-CAPACITY ASSIGNMENT FOR INTERCONNECTING TOKEN RING LANS - A SIMULATED ANNEALING APPROACH, Telecommunication systems, 6(1), 1996, pp. 21-43
We address the problem of determining the topology and bridge-capacity
assignments for a network connecting a number of token rings via sour
ce-routing bridges. The objective is to minimize the cost of bridge in
stallations while meeting the network users' performance requirements.
The problem is modeled as a mixed 0-1 integer program. A comparison i
s given between two solution algorithms: a simulated annealing algorit
hm using the flow-deviation algorithm for each routing subproblem, and
a drop algorithm using the simplex method for the same subproblems to
provide benchmark solutions. In the former algorithm, the routing sub
problem is formulated as a nonlinear program with penalty functions to
model node and link capacity constraints, and in the latter as a mult
icommodity flow model with the same capacity constraints. Computationa
l results show that the simulated-annealing/flow-deviation algorithm p
roduced substantially better solutions than the LP-based drop algorith
m.