liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Convex multicommodity flow problems: a bidual approach
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2005 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The topic of this dissertation, within the subfield of mathematics known as optimization, is the development of a new dual ascent method for convex multicommodity flow problems. Convex multicommodity flow problems arize in many different routing problems such as the design of packet switched computer networks and the computation of traffic network equilibria. The dual problem of a strictly convex twice differentiable convex multicommodity flow problem is an essentially unconstrained maximization problem with a piecewise twice differentiable concave objective. The idea behind this new dual ascent algorithm is to compute Newton-like ascent directions in the current differentiable piece and performing line searches in those directions combined with an active set type treatment of the borders between the differentiable pieces. The first contribution in this dissertation is a detailed investigation of this special structure. The insights gained are then used to explain the proposed algorithm. The algorithm is also tested numerically on well known traffic equilibrium problem instances. The computational results are very promising. The second contribution is a new approach for verifying feasibility in multicommodity flow problems. These feasibility problems arizes naturally in the new dual ascent algorithm proposed. The background of the problem is that if a certain representation of a solution to the dual convex multicommodity flow problem is proved to be feasible for the convex muticommodity flow problem aswell, an optimal solution is found. Hence, it is natural to seek a method for verifying feasibility of a given candidate solution for the multicommodity flow problem. The core of the approach is a distance minimizing method for verifying feasibility and hence for demonstrating optimality. This method is described in detail and some computational results in a traffic assignment setting is also given. Finally, a short note illustrating that many published test problems for traffic assignment algorithms have peculiarities are given. First and foremost, several of them have incorrectly specified attributes, such as the number of nodes. In other testproblems, the network contains subnetworks with constant travel times; subnetworks which to a large extent can be reduced or eliminated. In further test problems, the constant travel time subnetworks imply that the solution has nonunique arc flows.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2005. , 12 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 954
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-28478Local ID: 13625ISBN: 91-8529-963-4 (print)OAI: oai:DiVA.org:liu-28478DiVA: diva2:249288
Public defence
2005-06-02, BL32, B-huset, Campus Valla, Linköpings universitet, Linköping, 10:00 (English)
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2012-11-23Bibliographically approved
List of papers
1. A dual algorithm for the convex multicommodity flow problem
Open this publication in new window or tab >>A dual algorithm for the convex multicommodity flow problem
(English)Manuscript (preprint) (Other academic)
Abstract [en]

This paper introduces a new dual ascent algorithm for solving the convex multicommodity flow problem, CMFP for short. CMFPs arize in many different routing problems such as the design of packet switched computer networks and the computation of traffic network equilibria. The algorithm utilizes the structure of the dual convex multicommodity flow problem, DCMFP for short. The dual objective is a sum of a concave differentiable function and a piecewise linear concave function. The algorithm exploits the local structure of the dual objective in an ascent scheme. In this paper a thorough explanation of the CMFPs and DCMFPs are given along with an outline of the dual ascent algorithm proposed. The method are applied to CMFPs arizing in the traffic assignment setting.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-85560 (URN)
Available from: 2012-11-23 Created: 2012-11-23 Last updated: 2012-11-23
2. Verified feasibility of structured multicommodity flow solutions
Open this publication in new window or tab >>Verified feasibility of structured multicommodity flow solutions
(English)Manuscript (preprint) (Other academic)
Abstract [en]

This paper introduces a new approach for verifying feasibility for multicommodity flow problems, MFP:s for short. This feasibility problem priginates in a new solution method for the convex MFP based on the solution of the dual convex MFP, where optimality is demonstrated by showing that a given solution to the dual convex MFP is feasible for the convex MFP and hence optimal. In this paper a brief description of the MFP and the structure of its solutions are given. Furthermore, a distance minimizing method, based on simplicial decomposition, is described and used to efficiently verify feasibility and hence demonstrate optimality. The method is applied to convex MFP:s arizing in a traffic assignment setting.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-85562 (URN)
Available from: 2012-11-23 Created: 2012-11-23 Last updated: 2012-11-23
3. A comment on some test networks for the traffic assignment problem
Open this publication in new window or tab >>A comment on some test networks for the traffic assignment problem
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We show that many published test problems for traffic assignment algorithms have peculiarities. First and foremost, several of them have incorrectly specified attributes, such as the number of nodes. In other test-problems, the network contains subnetworks with constant travel times; subnetworks which to a large extent can be reduced or eliminated. In further test problems, the constant travel time subnetworks imply that the solution has nonunique arc flows.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-85563 (URN)
Available from: 2012-11-23 Created: 2012-11-23 Last updated: 2012-11-23

Open Access in DiVA

No full text

Authority records BETA

Hägglöf, Kristoffer

Search in DiVA

By author/editor
Hägglöf, Kristoffer
By organisation
Optimization The Institute of Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 152 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf