Optimization and Systems Theory Seminar
Friday, June 4, 2004, 11.00-12.00, Room 3721, Lindstedtsv. 25

Professor Per Olov Lindberg
Division of Optimization
Department of Mathematics
Linköping University

New fast and accurate methods for convex multicommodity flow problems

Convex Multicommodity Flow Problems (CMFP:s) appear in many transportation and communication problems, in particular in traffic assignment and telecom message routing. CMFP:s tend to be huge, whence specialized methods often are needed. The dominating method in practice is the Frank-Wolfe method, which has fast initial but slow asymptotic convergence. Faster (origin based) methods have been suggested recently, though. For this problem class, we suggest a new bidual approach, that promises to be both fast and accurate. The dual problem to a differentiable, strictly convex CMFP is an (essentially) unconstrained problem with piecewise differentiable strictly concave objective We have devised a dual ascent scheme for this problem. It is based on
- determination of Newton like ascent directions in the currently active differentiable piece, through the solution of a restricted-relaxed bidual problem.
- line searches, where we recursively update shortest path trees.
- treating of the ridges encountered in the line searches in an active set fashion.
- optimality checks, where feasibility of tentative multicommodity flow solutions are verified.

The talks is based on joint work with Kristoffer Hägglöf.

The studied problem class may seem specialized, but the approach used has bearing also on other structured problems.


Calendar of seminars
by Anders Forsgren.