Cost-based Filtering for Shorter Path Constraints |
| |
Authors: | Meinolf Sellmann Thorsten Gellermann Robert Wright |
| |
Affiliation: | (1) Department of Computer Science, Brown University, 115 Waterman St, Providence, RI 02912, USA;(2) Department of Computer Science, University of Paderborn, Fuerstenallee 11, 33102 Paderborn, Germany;(3) Information Directorate, Air Force Research Lab, 525 Brooks Road, Rome, NY 13441, USA |
| |
Abstract: | Many real world problems, e.g. personnel scheduling and transportation planning, can be modeled naturally as Constrained Shortest
Path Problems (CSPPs), i.e., as Shortest Path Problems with additional constraints. A well studied problem in this class is
the Resource Constrained Shortest Path Problem. Reduction techniques are vital ingredients of solvers for the CSPP, that is
frequently NP-hard, depending on the nature of the additional constraints. Viewed as heuristics, these techniques have not
been studied theoretically with respect to their efficiency, i.e., with respect to the relation of filtering power and running
time. Using the concepts of Constraint Programming, we provide a theoretical study of cost-based filtering for shorter path
constraints on acyclic, on undirected, and on directed graphs that do not contain negative cycles. We then show empirically
how reasoning about path-substructures in combination with CP-based Lagrangian relaxation can help to improve significantly
over previously developed problem-tailored filtering algorithms for the resource constrained shortest path problem and investigate
the impact of required-edge detection, undirected versus directed filtering, and the choice of the algorithm optimizing the
Lagrangian dual. |
| |
Keywords: | Constrained shortest paths Problem reduction Global constraints Optimization constraints Relaxed consistency |
本文献已被 SpringerLink 等数据库收录! |
|