EasyLocal Project Home Page

Scope and Aims

Differently from other search paradigms, e.g. branch & bound, no widely-accepted software tool is available up to now for local search; but only a few research-level prototypes have gained limited popularity. In our opinion, the reason for this lack is twofold: on the one hand, the apparent simplicity of local search induces the users to build their applications from scratch. On the other hand, the rapid evolution of local search techniques (tabu search, variable neighborhood search, iterative local search, ...) seems to make the development of general tools quite impractical.

We believe that the use of object-oriented (O-O) frameworks can help in overcoming this problem. A framework is a special kind of software library, which consists of a hierarchy of abstract classes and represents a partial implementation of the program. Therefore, a framework provides the full control structures of the invariant part of the algorithms, and the user is required only to supply the problem specific details.

The EasyLocal project regards the design and the development of an O-O framework as a general tool for the development of local search algorithms. The framework should provide a principled modularization for the solution of combinatorial problems by local search, and help the user deriving a neat conceptual scheme of the application. The aim is a system that is flexible enough for solving combinatorial problems using a variety of algorithms based on local search. In addition, the system must support also the design and the fast implementation of new techniques obtained by combinations of other basic techniques and different neighborhood structures and the study and development of innovative meta-heuristics based, for example, on learning mechanisms.

Detailed description A more detailed description of the EasyLocal framework is available from this page.

People involved

Developments

The first, very limited, version -called Local++- has been abandoned, in favor to a completely different and more powerful one -called EasyLocal.

EasyLocal has been developed both in the C++ and Java languages and its core is composed by a set of cooperating classes that take care of different aspects of local search. The prototype system has already been tested in the solution of some combinatorial problems of theoretical interest -such as Propositional Satisfiability, n-Queens, Graph Coloring, Magic Square- as well as on problems of practical application -such as Examination Timetabling, EmployeeTimetabling, University Timetabling, Vehicle Routing, ...

Downloads

It is possible to download an abridged version of the framework to be used for research purposes from here. The same page also provides documentation about the current version of EasyLocal.

Research grants

The project has been partly funded by the Italian Ministry of Education, University and Research (MIUR) under the project PRIN 2003 "Design and implementation of a solver based on local search for the execution of declarative specifications for combinatorial problems".
Luca Di Gaspero has been partly funded by a grant from the University of Udine, "Progetto Giovani Ricercatori" 2000.

Main References

[1]	Luca Di Gaspero and Andrea Schaerf. EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Software - Practice & Experience, 33(8):733-765, July 2003. [ bib \| .pdf ]
[2]	Luca Di Gaspero. Local Search Techniques for Scheduling Problems: Algorithms and Software Tools. PhD thesis, Dipartimento di Matematica e Informatica - Universit`a degli Studi di Udine, Udine, Italy, 2003. [ bib \| .pdf ]
[3]	Luca Di Gaspero and Andrea Schaerf. Writing local search algorithms using EasyLocal++. In Stefan Voß and David L. Woodruff, editors, Optimization Software Class Libraries, OR/CS. Kluwer Academic Publisher, Boston (MA), USA, 2002. [ bib \| .pdf ]
[4]	Luca Di Gaspero and Andrea Schaerf. A case-study for EasyLocal++: the course timetabling problem. Technical Report UDMI/13/2001/RR, Dipartimento di Matematica e Informatica - Universit`a di Udine, 2001. [ bib \| .pdf ]
[5]	Luca Di Gaspero and Andrea Schaerf. EasyLocal++: An object-oriented framework for flexible design of local search algorithms. Technical Report UDMI/13/2000/RR, Dipartimento di Matematica e Informatica - Universit`a di Udine, 2000. [ bib \| .pdf ]

Other References

[1]	Andrea Schaerf, Marco Cadoli, and Maurizio Lenzerini. Local++: A C++ framework for local search algorithms. Software - Practice & Experience, 30(3):233-257, 2000. [ bib \| .pdf ]
[2]	Andrea Schaerf, Maurizio Lenzerini, and Marco Cadoli. Local++: A C++ framework for combinatorial search problems. In Proc. of the 29th International Conference on Technology of Object-Oriented Languages and Systems (TOOLS-99), pages 152-161, Nancy, France, 1999. An extended version appeared in Software - Practice & Experience. [ bib ]
[3]	Andrea Schaerf, Maurizio Lenzerini, and Marco Cadoli. Local++: A C++ framework for local search algorithms. Technical Report 11-99, Dipartimento di Informatica e Sistemistica, Universit`a di Roma "La Sapienza", Rome, Italy, 1999. Appeared in Software - Practice & Experience. [ bib ]