Network Optimization – Page 32 – Optimization Online

The Robust Shortest Path Problem with Interval Data

Published: 2001/08/06, Updated: 2003/02/03

Network Optimization, Robust Optimization, Telecommunications interval data, robust optimization, shortest path problem, uncertainty

Motivated by telecommunication applications, we investigate the shortest path problem on directed acyclic graphs under arc length uncertainties represented as interval numbers. Using a minimax-regret criterion we define and identify robust paths via mixed-integer programming and exploiting interesting structural properties of the problem. CitationBilkent University, Department of Industrial Engineering, Technical Report August 2001ArticleDownload View PDF

A GRASP with path-relinking for private virtual circuit routing

Published: 2001/06/15

Mauricio G.C. Resende

Celso C. Ribeiro

Meta Heuristics, Network Optimization, Telecommunications bandwidth packing, frame relay, grasp, metaheuristics, multicommodity network flows, offline rerouting, path relinking, private virtualcircuit, routing

A frame relay service offers virtual private networks to customers by provisioning a set of long-term private virtual circuits (PVCs) between customer endpoints on a large backbone network. During the provisioning of a PVC, routing decisions are made without any knowledge of future requests. Over time, these decisions can cause inefficiencies in the network and … Read more

A study of preconditioners for network interior point methods

Published: 2001/04/24, Updated: 2002/07/22

Joaquim J. Júdice

João Patrício

Luis F. Portugal

Mauricio G.C. Resende

Geraldo Veiga

Network Optimization conjugate gradient method, interior point methods, linear programming, network flows, pr

We study and compare preconditioners available for network interior point methods. We derive upper bounds for the condition number of the preconditioned matrices used in the solution of systems of linear equations defining the algorithm search directions. The preconditioners are tested using PDNET, a state-of-the-art interior point code for the minimum cost network flow problem. … Read more

Dimensioning multicast-enabled communications networks

Published: 2001/02/12, Updated: 2022/08/01

Anders Forsgren

Mikael Prytz

0-1 Programming, Network Optimization, Telecommunications branch-and-cut, lagrangean decomposition, multicast traffic, network optimization, telecommunications

Networks 39 (2002), 216-231. CitationNetworks 39 (2002), 216-231.

On the min-cut max-flow ratio for multicommodity flows

Published: 2001/02/05

Oktay Gunluk

Network Optimization

In this paper we present a new bound on the min-cut max-flow ratio for multicommodity flow problems. We use a so-called aggregated commodity formulation and an optimal solution to its dual to show our main result. Currently, the best known bound for this ratio is proportional to log(k) where k is the number of origin-destination … Read more

Newton Algorithms for Large-Scale Strictly Convex Separable Network Optimization

Published: 2001/01/19

Aleksandar Donev

Phillip Duxbury

Convex Optimization, Network Optimization convex optimization, network optimization

In this work we summarize the basic elements of primal and dual Newton algorithms for network optimization with continuously differentiable (strictly) convex arc cost functions. Both the basic mathematics and implementation are discussed, and hints to important tuning details are made. The exposition assumes that the reader posseses a significant level of prior knowledge in … Read more