Professor Per Olov Lindberg
Division of Optimization
Department of Mathematics
Linköping University
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.