Optimal Dynamic Routing in Single Commodity Networks by Iterative Methods

Galen Sasaki, Bruce Hajek

Research output: Contribution to journalComment/debate

Abstract

In this paper, we present iterative methods for finding optimal state-dependent routing strategies in single commodity networks. The key to our method is to show that there exists a family of optimization problems with convex cost and linear constraints that have solutions that can be converted into an optimal routing strategy by way of a flow relaxation transformation. These problems, when solved by certain iterative algorithms, lead to different convergence rates. In particular, one of the problems has quadratic cost.To solve one of these optimization problems, we use an iterative projected descent direction algorithm due to Bertsekas. We present an alternative to the Armijo-like step size rule of the algorithm, which we believe is more robust. Also included are Newton-like descent directions that take a reasonable amount of time to compute. Finally, some results of our computer experiments are summarized.

Original languageEnglish (US)
Pages (from-to)1199-1206
Number of pages8
JournalIEEE Transactions on Communications
Volume35
Issue number11
DOIs
StatePublished - Nov 1987

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Optimal Dynamic Routing in Single Commodity Networks by Iterative Methods'. Together they form a unique fingerprint.

  • Cite this