Solving nonlinear multicommodity flow problems by the analytic center cutting plane method

Fecha:	1997
Resumen:	The paper deals with nonlinear multicommodity flow problems with convex costs. A decomposition method is proposed to solve them. The approach applies a potential reduction algorithm to solve the master problem approximately and a column generation technique to define a sequence of primal linear programming problems. Each subproblem consists of finding a minimum cost flow between an origin and a destination node in an uncapacited network. It is thus formulated as a shortest path problem and solved with Dijkstra's d-heap algorithm. An implementation is described that takes full advantage of the supersparsity of the network in the linear algebra operations. Computational results show the efficiency of this approach on well-known nondifferentiable problems and also large scale randomly generated problems (up to 1000 arcs and 5000 commodities).
Derechos:	Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.
Lengua:	Anglès
Documento:	Article ; recerca ; Versió publicada
Materia:	Àlgebra
Publicado en:	Mathematical Programming, vol. 76 n. 1 (1997) p. 131-154, ISSN 0025-5610

24 p, 1.2 MB

Acceso restringido a la UAB

Registro creado el 2006-03-13, última modificación el 2024-12-07