Project : coprin

Section: Software

Keywords : local search , meta-heuristics .

INCOP

Participants : Bertrand Neveu, Gilles Trombettoni.

We have designed and implemented a new C++ library INCOP of incomplete methods for solving combinatorial optimization problems. This library offers classical local search methods such as simulated annealing, tabu search, a population based method "Go With the Winners" (GWW). Several problems have been encoded, including Constraint Satisfaction Problems, graph coloring, frequency assignment. The user can easily add new algorithms and encode new problems. The neighborhood management has been carefully studied. First, an original parameterized move selection allows us to easily implement most of the existing meta-heuristics. Second, different levels of incrementality can be specified for the configuration cost computation, which highly improves efficiency.

INCOP has shown great performances on a sample of well-known benchmarks. It outperforms most of the existing concurrent tools. The challenging flat300_28 graph coloring instance has been colored in 30 colors for the first time by a standard Metropolis algorithm. The first version of this library, named INCOP [32] [34] [33], is now available at http://www-sop.inria.fr/coprin/neveu/incop.

We have also designed a new hybrid algorithm scheme, a hybridization of the population based "Go With the Winners" algorithm with local search. The randomization step of GWW is replaced by a local search in order to favor better solutions during the search. An instantiation of this schema, named GWW-grw, has four parameters and we proposed a simple way to tune them [32] [35]. Good results for frequency assignment problems have been obtained.