A Theoretical Framework for Local Search Techniques

Eric Monfroy (1, 2) , Frédéric Saubion (3) , Broderick Crawford (4) , Carlos Castro (5)

1 LINA - Laboratoire d'Informatique de Nantes Atlantique
2 TASC - Theory, Algorithms and Systems for Constraints
3 LERIA - Laboratoire d'Etudes et de Recherche en Informatique d'Angers
4 Escuela de Ingenieria Informatica [Valparaíso]
5 Departamento de Matematica [Valparaiso]

In the paper we describe a theoretical framework to model local search as the computation of a fixed point of functions. There are only few studies of theoretical frameworks for local search, this work allows one to simulate standard strategies used for local search and to easily design new strategies in a uniform framework. The use of this framework is illustrated through the description of Tabu search and random walk methods for solving different instances of Sudoku problem.

Mots clés: Algorithm design and analysis; Artificial Intelligence; Computational modeling; Computer science; Constraint Satisfaction Problem (CSP); constraint solving; constraint theory; Databases; Genetic algorithms; Local search; local search techniques; Mathematics; operations research; Processor scheduling; random walk methods; search problems; Sudoku problem; tabu search; uniform framework

Domaines: Informatique [cs]

Eric Monfroy, Frédéric Saubion, Broderick Crawford, Carlos Castro. A Theoretical Framework for Local Search Techniques. 11th IEEE International Conference on Computational Science and Engineering, 2008, Sao Paulo, Brazil. pp.335 - 342, ⟨10.1109/CSE.2008.40⟩. ⟨hal-03255562⟩