A dual algorithm for the convex multicommodity flow problem
(English)Manuscript (preprint) (Other academic)
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.
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-85560OAI: oai:DiVA.org:liu-85560DiVA: diva2:571680