30-10-2012, 05:13 PM
Primal and Dual Neural Networks for Shortest-Path Routing
Primal and Dual Neural Networks.pdf (Size: 183 KB / Downloads: 23)
Abstract
This paper presents two recurrent neural networks for
solving the shortest path problem. Simplifying the architecture of a
recurrent neural network based on the primal problem formulation,
the first recurrent neural network called the primal routing network
has less complex connectivity than its predecessor. Based on the dual
problem formulation, the second recurrent neural network called the dual
routing network has even much simpler architecture. While being simple
in architecture, the primal and dual routing networks are capable of
shortest-path routing like their predecessor.
INTRODUCTION
The shortest path problem is concerned with finding the shortest
path from a specified origin to a specified destination in a given
network while minimizing the total cost associated with the path.
The shortest path problem is an archetypal combinatorial optimization
problem having widespread applications in a variety of settings. The
applications of the shortest path problem include vehicle routing in
transportation systems [1], traffic routing in communication networks
[2], [3], and path planning in robotic systems [4]–[6]. Furthermore,
the shortest path problem also has numerous variations such as
the minimum weight problem, the quickest path problem, the most
reliable path problem, and so on.
PROBLEM FORMULATION
Formulation Based on Vertex Path Representation
The shortest path problem is to find the shortest (least costly)
possible directed path from a specified origin vertex to a specified
destination vertex. The cost of the path is the sum of the costs on the
edges in the path. Based on the vertex path representation, the shortest
path problem can be mathematically formulated as a quadratic integer
program as follows
PRIMAL ROUTING NETWORK
Because the shortest path problem based on the edge path representation
is formulated as a linear program, it can be solved
by the neural networks proposed for linear programming. In [15],
[16], a recurrent neural network called the deterministic annealing
network is presented and demonstrated to be capable of solving linear
programming problems. The primal and dual routing networks are
tailored from the deterministic annealing network [15], [16]. Let the
decision variables of the primal and dual shortest path problem be
represented, respectively, by the activation states of the primal and
dual routing networks. For simplicity of notations, the same symbols
[xij ] and [zi] are used to denote both the decision variables and
corresponding activation states.
CONCLUDING REMARKS
In this paper, the primal routing network with O(n2) neurons and
connections and the dual routing network with O(n) neurons and
O(n2) connections for solving the shortest path problem have been
presented. The dynamics and architectures of the primal and dual
routing networks have been described. The design methodology and
guidelines have been delineated. It has been shown that the primal and
dual routing networks are capable of shortest-path routing for directed networks with arbitrary cost coefficients. The convergence rate of the
primal and dual routing networks is nondecreasing with respect to the
size of the shortest path problem and can be expedited by properly
scaling design parameters. These features make the primal and dual
routing networks suitable for solving large-scale shortest path problems
in real-time applications. One salient advantage of the primal
and dual routing networks is the independence of the connection
weight matrix upon specific problems.