EASYLOCAL++: an object-oriented framework for the flexible design of local-search algorithms

摘要

Local search is a paradigm for search and optimization problems, which has recently evidenced to be very effective for a large number of combinatorial problems. Despite the increasing interest of the research community in this subject, there is still a lack of a widely-accepted software tools for local search. We propose EASYLOCAL++, an object-oriented framework for the design and the analysis of local-search algorithms. The abstract classes that compose the framework specify and implement the invariant part of the algorithm and are meant to be specialized by concrete classes that supply the problem-dependent part. The framework provides the full control structures of the algorithms, and the user has only to write the problem-specific code. Furthermore, the framework comes with some tools that simplify the analysis of the algorithms. The architecture of EASYLOCAL++ provides a principled modularization for the solution of combinatorial problems by local search and helps the user by deriving a neat conceptual scheme of the application. It also supports the design of combinations of basic techniques and/or neighborhood structures. The framework has been tested in some applicative domains and has proved to be flexible enough in the implementation of algorithms for the solution of various scheduling problems.