A Potts Neuron Approach to Communication Routing

Research output: Contribution to journalArticle

Standard

A Potts Neuron Approach to Communication Routing. / Häkkinen, Jari; Lagerholm, Martin; Peterson, Carsten; Söderberg, Bo.

In: Neural Computation, Vol. 10, 1998, p. 1587-1599.

Research output: Contribution to journalArticle

Harvard

APA

CBE

MLA

Vancouver

Author

Häkkinen, Jari ; Lagerholm, Martin ; Peterson, Carsten ; Söderberg, Bo. / A Potts Neuron Approach to Communication Routing. In: Neural Computation. 1998 ; Vol. 10. pp. 1587-1599.

RIS

TY - JOUR

T1 - A Potts Neuron Approach to Communication Routing

AU - Häkkinen, Jari

AU - Lagerholm, Martin

AU - Peterson, Carsten

AU - Söderberg, Bo

PY - 1998

Y1 - 1998

N2 - A feedback neural network approach to communication routing problems is developed, with emphasis on Multiple Shortest Path problems, with several requests for transmissions between distinct start- and endnodes. The basic ingredients are a set of Potts neurons for each request,with interactions designed to minimize path lengths and to prevent overloading of network arcs. The topological nature of the problem is conveniently handled using a propagator matrix approach. Although the constraints are global, the algorithmic steps are based entirely on local information, facilitating distributed implementations. In the polynomially solvable single-request case, the approach reduces to a fuzzy version of the Bellman-Ford algorithm. The method is evaluated for synthetic problems of varying sizes and load levels, by comparing to exact solutions from a branch-and-bound method, or to approximate solutions from a simple heuristic. With very few exceptions, the Potts approach gives legal solutions of very high quality. The computational demand scales merely as the product of the numbers of requests, nodes, and arcs.

AB - A feedback neural network approach to communication routing problems is developed, with emphasis on Multiple Shortest Path problems, with several requests for transmissions between distinct start- and endnodes. The basic ingredients are a set of Potts neurons for each request,with interactions designed to minimize path lengths and to prevent overloading of network arcs. The topological nature of the problem is conveniently handled using a propagator matrix approach. Although the constraints are global, the algorithmic steps are based entirely on local information, facilitating distributed implementations. In the polynomially solvable single-request case, the approach reduces to a fuzzy version of the Bellman-Ford algorithm. The method is evaluated for synthetic problems of varying sizes and load levels, by comparing to exact solutions from a branch-and-bound method, or to approximate solutions from a simple heuristic. With very few exceptions, the Potts approach gives legal solutions of very high quality. The computational demand scales merely as the product of the numbers of requests, nodes, and arcs.

U2 - 10.1162/089976698300017322

DO - 10.1162/089976698300017322

M3 - Article

VL - 10

SP - 1587

EP - 1599

JO - Neural Computation

JF - Neural Computation

SN - 1530-888X

ER -