Abstract
Limited Discrepancy Search (LDS) is one of the most widely used search strategies in Constraint Programming; given a solution suggested by a search heuristics, LDS explores the search space at increasing discrepancy with respect to such solution. In optimization problems, LDS is used as a way to explore the k-distance neighborhood of an incumbent solution using constraint propagation and tree search. However, for large problems, the size of the resulting neighborhoods limits the k-distance (i.e. the number of discrepancies) that can be efficiently explored. If the first solution is far from the optimal one, exploring limited neighborhood leads to small improvements.
Therefore, we propose a variant of LDS that samples the LDS space by exploring slices of (possibly very large) discrepancy based neighborhoods. Instead of deciding only the number of variables that can change (the k-distance) we decide which n − k variables should be fixed to the value they have in the incumbent solution. We present results on hard Asymmetric Traveling Salesman Problem with Time Windows (ATSPTW) instances to show the effectiveness of the approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ascheuer, N.: Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. PhD thesis, Technische Universität Berlin (1995)
Desrosiers, J., Dumas, Y., Solomon, M.M., Soumis, F.: Time constrained routing and scheduling. In: Network Routing, pp. 35–139 (1995)
Focacci, F., Lodi, A., Milano, M.: A hybrid exact algorithm for the tsptw. Informs Journal on Computing 14(4), 403–417 (2002)
Focacci, F., Lodi, A., Milano, M.: Optimization-oriented global constraints. Constraints 7, 351–365 (2002)
Harvey, W., Ginsberg, M.L.: Limited discrepancy search. In: Proc. of IJCAI 1995, pp. 607–615. Morgan Kaufmann, San Francisco (1995)
Kiziltan, Z., Lodi, A., Milano, M., Parisini, F.: Cp-based local branching. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 847–855. Springer, Heidelberg (2007)
Korf, R.E.: Improved limited discrepancy search. In: Proceedings of AAAI 1996, pp. 286–291. MIT Press, Cambridge (1996)
Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 417–431. Springer, Heidelberg (1998)
Walsh, T.: Depth-bounded discrepancy search. In: Proceedings of IJCAI 1997, pp. 1388–1393 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Parisini, F., Lombardi, M., Milano, M. (2010). Discrepancy-Based Sliced Neighborhood Search. In: Dicheva, D., Dochev, D. (eds) Artificial Intelligence: Methodology, Systems, and Applications. AIMSA 2010. Lecture Notes in Computer Science(), vol 6304. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15431-7_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-15431-7_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15430-0
Online ISBN: 978-3-642-15431-7
eBook Packages: Computer ScienceComputer Science (R0)