Premium
Improved preprocessing, labeling and scaling algorithms for the Weight‐Constrained Shortest Path Problem
Author(s) -
Dumitrescu I.,
Boland N.
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10090
Subject(s) - preprocessor , shortest path problem , computer science , lagrange multiplier , algorithm , relaxation (psychology) , mathematical optimization , simple (philosophy) , scaling , path (computing) , computational complexity theory , mathematics , theoretical computer science , artificial intelligence , graph , psychology , social psychology , philosophy , geometry , epistemology , programming language
Much has been written on shortest path problems with weight, or resource, constraints. However, relatively little of it has provided systematic computational comparisons for a representative selection of algorithms. Furthermore, there has been almost no work showing numerical performance of scaling algorithms, although worst‐case complexity guarantees for these are well known, nor has the effectiveness of simple preprocessing techniques been fully demonstrated. Here, we provide a computational comparison of three scaling techniques and a standard label‐setting method. We also describe preprocessing techniques which take full advantage of cost and upper‐bound information that can be obtained from simple shortest path information. We show that integrating information obtained in preprocessing within the label‐setting method can lead to very substantial improvements in both memory required and run time, in some cases, by orders of magnitude. Finally, we show how the performance of the label‐setting method can be further improved by making use of all Lagrange multiplier information collected in a Lagrangean relaxation first step. © 2003 Wiley Periodicals, Inc.