Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482559 | European Journal of Operational Research | 2006 | 11 Pages |
Abstract
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 QKP’s simultaneously in a vectorial or parallel way.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Pablo A. Lotito,