INVESTIGADORES
LOTITO Pablo Andres
artículos
Título:
Issues in the implementation of the DSD
Autor/es:
LOTITO P.A
Revista:
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Editorial:
Elsevier V.B.
Referencias:
Año: 2006 vol. 175 p. 1577 - 1587
ISSN:
0377-2217
Resumen:
In this paper we consider the practical implementation of the disaggregated simplicial decomposition (DSD) algorithm for the traffic assignment problem. It is a column generation method that at each step has to solve a huge number of quadratic knapsack problems (QKP). We propose a Newton-like method to solve the QKP when the quadratic functional is convex but not necessarily strictly. Our O(n) algorithm does not improve the complexity of the current methods but extends them to a more general case and is better suited for reoptimization and so a good option for the DSD algorithm. It also allows the solution of many QKPs simultaneously in a vectorial or parallel way.n) algorithm does not improve the complexity of the current methods but extends them to a more general case and is better suited for reoptimization and so a good option for the DSD algorithm. It also allows the solution of many QKPs simultaneously in a vectorial or parallel way.
2005 Elsevier B.V. All rights reserved.2005 Elsevier B.V. All rights reserved.
