Optimal two-commodity flows with non-linear cost functions

N. L. Boland, A. T. Ernst, C. J. Goh, A. I. Mees

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

We consider networks in which two different commodities have to be transported across undirected arcs, subject to a shared capacity on the arcs. For each arc and commodity there is an associated non-linear cost that depends on the amount of the commodity transported across the arc. The aim is to minimize the sum of the costs over all arcs and commodities. Efficient algorithms for solving this problem for two types of objective functions will be presented: in the first the cost depends on the absolute value of the flow and in the second the cost is a quadratic function of the flow. Previous work on multi-commodity flow has concentrated on linear cost problems or tackled non-linear cost problems with Lagrangian relaxation methods and other more general techniques. The algorithms in this paper, on the other hand, provide a very efficient way of dealing with two types of non-linear two-commodity optimal flow problems.

Original languageEnglish
Pages (from-to)1192-1207
Number of pages16
JournalJournal of the Operational Research Society
Volume46
Issue number10
DOIs
Publication statusPublished - 1995
Externally publishedYes

Keywords

  • Networks
  • Optimization
  • Quadratic programming
  • Two-commodity flow

Cite this