Special Issue on Selected Papers from the 17th International FLAIRS Conference (FLAIRS-2004); Guest Editors: Zdravko Markov, Valerie BarrNo Access

A LOCAL SEARCH/CONSTRAINT PROPAGATION HYBRID FOR A NETWORK ROUTING PROBLEM

JONATHAN LEVER

JONATHAN LEVER

IC-Parc, Imperial College, London, SW7 2AZ, UK

Search for more papers by this author

https://doi.org/10.1142/S0218213005001989Cited by:9 (Source: Crossref)

Abstract

This paper presents a hybrid algorithm that combines local search and constraint programming techniques to solve a network routing problem. The problem considered is that of routing traffic demands from a set of requests over a network with limited capacity so as to minimise the cost of any unrouted demands. The hybridisation is twofold: pure local search is used to find a good cost bound for a subsequent branch-and-bound optimisation phase, with local search again applied at the nodes of the branch-and-bound search tree. Constraint propagation occurs in the search tree to reduce the domains of the decision variable, using a set of constraints that are independent of the action of local search at the nodes. In contrast to previous constraint programming/local search hybridisations, here local search is used to satisfy the hard problem constraints, while optimisation is handled in the framework of constraint programming. The resulting algorithm is incomplete, but is shown to compare favourably with a complete approach to this problem.

Keywords:

Remember to check out the Most Cited Articles!
Check out Notable Titles in Artificial Intelligence.

References

Y. Casseau and F. Laburthe, Journal of Heuristics 5(3), 281 (1999). Crossref, Web of Science, Google Scholar
M. Genreau and G. Pesant, Journal of Heuristics 5(3), 255 (1999). Web of Science, Google Scholar
N. Jussien and O. Lhomme, Local search with constraint propagation and conflict-based heuristics, in Proc. 7th International National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligence, (AAAI Press, 2000), pp. 169–174 . Google Scholar
O. Kamarainen and H. El-Sakkout, Local probing applied to scheduling, Proc. 8th International Conference on the Principles and Practice of Constraint Programming (Springer-Verlag, 2002) pp. 155–171. Google Scholar
A. Schaerf, Combining local search and look-ahead for scheduling and constraint satisfaction problems, Proc. 15th International Joint Conference on Artificial Intelligence (Morgan Kaufmann, 1997) pp. 1254–1259. Google Scholar
P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, Proc. 4th International Conference on the Principles and Practice of Constraint Programming (Springer-Verlag, 1998) pp. 417–431. Google Scholar
J. Zhang and H. Zhang, Combining local search and backtracking techniques for constraint satisfaction, Proc. of the American Association for Artificial Intelligence (AAAI Press, 1996) pp. 369–374. Google Scholar
W. Lee, M. Hluchyi and P. Humblet, IEEE Network 46 (1995). Google Scholar
C. Barnhart, C. A. Hane and P. H. Vance, Operations Research 48(2), 318 (2000). Crossref, Web of Science, Google Scholar
Y. Wang and Z. Wang , Explicit routing algorithms for internet traffic engineering , Proc. IEEE ICCCN ( 1999 ) . Google Scholar
V. Liatsos , S. Novello and H. El-Sakkout , A probe backtrack search algorithm for network routing , Proc. CP2003 Third Workshop on Cooperating Solvers in Constraint Programming ( Springer-Verlag , 2003 ) . Google Scholar
S. Kirkpatrick, C. Gelatt Jr. and M. Vecchi, Science 220, 671 (1983). Crossref, Web of Science, Google Scholar
W. D. Harvey and M. L. Ginsberg, Limited discrepancy search, Proc. 14th International Joint Conference on Artificial Intelligence (Morgan Kaufmann, 1995) pp. 607–615. Google Scholar