We present a new free library, INCOP, which provides incomplete algorithms for optimizing combinatorial problems. This library offers classical local search methods such as hill climbing, GSAT, simulated annealing, tabu search as well as a population based method, Go With the Winners. Several problems have been encoded, including Constraint Satisfaction Problems, graph coloring, frequency assignment. INCOP is an open C++ library. The user can easily add new methods and encode new problems. The neighborhood management has been studied carefully. First, a parameterized move selection allows us to easily implement most of the existing meta-heuristics. Second, different levels of incrementality can be specified for the evaluation of the moves, which highly improves efficiency. We obtain the best known bounds on all instances in our sample of well-known benchmarks. The challenging flat300_28 graph coloring instance has been colored in 30 colors by a standard Metropolis algorithm.

We present Metalab, a C++ framework aimed at programming local search. The framework allows to decouple the conception of algorithm components and problem data structures. This way, end-users take advantage of Metalab by reusing available algorithms to tackle new problems, and also, by reusing available problems in order to study new metaheuristics. Among other features, Metalab supports parallel search, shared memory and neighborhood shifting mechanisms. We first describe the main design features of Metalab. We then show some comprehensive examples on how to tackle new problems and how to create advanced metaheuristics.