Abstract
Local search is a metaheuristic for solving computationally hard optimization problems. In the past three decades, local search has grown from a simple heuristic idea into a mature field of research in combinatorial optimization that is attracting ever-increasing attention. It is still the method of choice for NP-hard problems as it provides a robust approach for obtaining high-quality solutions to problems of a realistic size in reasonable time. Optimization problems such as the shortest path, the traveling salesman, pin packing, and the Knapsack problems. Local search techniques have been successful in solving large and tight constraint satisfaction problems. Local search algorithms turn out to be effective in solving many constraint satisfaction problems. This chapter gives an introduction to the local search algorithms, the optimization and the constraint satisfaction problems, and the local search methods used to solve them.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
http://www.cs.cmu.edu/~venkatg/RD-approx.html. Accessed 15 Aug 2012
Veřmřovský K (2003) Algorithms for constraint satisfaction problems. Master thesis, Faculty of Informatics, Masaryk University Brno, Czech Republic
Brailsford SC, Pott CN, Smith BM (1999) Constraint satisfaction problems: algorithms and applications. Eur J Oper Res 119:557–581
Newton MAH, Pham D, Sattar A, Maher M (2011) Kangaroo: an efficient constraint-based local search system using lazy propagation. In: Proceedings of 17th international conference on principles and practice of constraint programming
Letombe F, Joao Marques-Silva J (2008) Improvements to hybrid incremental SAT algorithms. In: Proceeding of the international conference on theory and applications of satisfiability testing
http://en.wikipedia.org/wiki/Local_search_(optimization). Accessed 14 Nov 2014
Aarts EHL, Lenstra EJK (2003) Local search in combinatorial optimization. Princeton University Press, Princeton
http://en.wikipedia.org/wiki/Optimization_problem. Accessed 08 Aug 2014
Mancini T, Flener P, Pearson JK (2012) Combinatorial problem solving over relational databases: view synthesis through constraint-based local search. In: Proceedings of the 27th annual ACM symposium on applied computing, pp 80–87
http://hsc.csu.edu.au/sdd/core/cycle/feasibility/feasibility.html. Accessed 08 Aug 2014
Aardal KI, van Hoesel S, Lenstra JK, Stougie L (1997) A decade of combinatorial optimization. Technical report, Utrecht University, Information and Computing Sciences, Issue 1997–12
Mackworth A (1977) Consistency in networks of relations. J Artif Intell 8(1):99–118
Fang H, Kilani Y, Lee JHM, Stuckey PJ (2007) The Island confinement method for reducing search space in local search methods. J Heuristics 13:557–585
Michel L, Van Hentenryck P (1999) A modeling language for local search. INFORMS J Comput 11:1–14
Van Hentenryck P, Michel L (2009) Constraint-based local search. MIT Press, Honolulu
http://www.hakank.org/oscar/. Accessed 2 Aug 2014
Audemard G, Simon L (2007) GUNSAT: a greedy local search algorithm for unsatisfiability. In: Proceeding of the international joint conference on artificial intelligence
Tompkins DA, Hoos HH (2004) UBCSAT: an implementation and experimentation environment for SLS algorithms for SAT and MAX-SAT. In: Proceeding of the 7th international conference on theory and applications of satisfiability testing, pp 37–46
Pham D-N, Thornton J, Gretton C, Sattar A (2007) Advances in local search for satisfiability. In: Proceedings of the 20th Australian joint conference on artificial intelligence
Schuurmans D, Southey F, Holte R (2001) The exponentiated subgradient algorithm for Heuristic Boolean Programming. In: Proceeding of the international joint conference on artificial intelligence, pp 334–341
Wei W, Li CM (2009) Switching between two adaptive noise mechanisms in local search for SAT
Li CM, Wei W (2009) Combining adaptive noise and promising decreasing variables in local search for SAT, (2009). SAT2009. http://www.cril.univ-artois.fr/SAT09/
Li XY, Stallmann MF, Brglez F (2003) QingTing: a fast SAT solver using local search and efficient unit propagation. In: Proceedings of international conference on theory and applications of satisfiability testing
Huttter F, Tompkins DAD, Hoos HH (2002) Scaling and probabilistic smoothing: efficient dynamic local search for SAT. In: Proceedings of the eighth international conference on principle and practice of constraint programming (CP-02). Lecture Notes in Computer Science (LNCS), vol 2470, pp 233–248
Thornton J (2005) Clause weighting local search for SAT. J Autom Reasoning 35(1–3):97–142. ISSN 0168-7433
Ho SY, Shu LS, Chen JH (2004) Intelligent evolutionary algorithms for large parameter optimization problems. IEEE Trans Evol Comput 8(6):522–541. http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=01369245
Yang P (2007) A hybrid evolutionary algorithm by combination of PSO and GA for unconstrained and constrained optimization problems. In: IEEE international conference on control and automation
Russell S, Norvig P (2009) Artificial intelligence: a modern approach, 3rd edn. Prentice Hall, Englewood Cliffs
https://bitbucket.org/oscarlib/oscar/wiki/CBLS. Accessed 29 July 2014
Van Hentenryck P (2009) Constraint-based local search. MIT Press, Cambridge
https://bitbucket.org/oscarlib/oscar/wiki/ExtendCBLS. Access 4 Aug 2014
http://jripples.sourceforge.net/jripples/manual/concepts/propagationrules.html. Accessed 4 Aug 2014
Micheal L, Van Hentenryck P (2000) Localizer. J Constraints 5(1–2):43–84
http://dynadec.com/technology/. Accessed 13 Dec 2013
http://dynadec.com/technology/constraint-based-local-search/. Accessed 12 Aug 2014
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Kilani, Y., Alsarhan, A., Bsoul, M., Otoom, A.F. (2016). Local Search Algorithms for Solving the Combinatorial Optimization and Constraint Satisfaction Problems. In: Balas, V., C. Jain, L., Kovačević, B. (eds) Soft Computing Applications. SOFA 2014. Advances in Intelligent Systems and Computing, vol 356. Springer, Cham. https://doi.org/10.1007/978-3-319-18296-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-18296-4_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18295-7
Online ISBN: 978-3-319-18296-4
eBook Packages: EngineeringEngineering (R0)