Séminaire du GERAD : « Consistent Neighborhood Search for Assignment Problems with Incompatibility Constraints »

Many combinatorial optimization problems require the use of a local search to find a satisfying solution in a reasonable amount of time, even if the optimality is not guaranteed. Usually, local search algorithms operate in a search space which contains complete solutions (feasible or not) to the problem. In contrast, in Consistent Neighborhood Search (CNS), after each variable assignment, the conflicting variables are deleted to keep the partial solution feasible, and the search can stop when all the variables have a value. In this talk is formally presented CNS, which has a search behavior between exhaustive tree search and local search working with complete solutions. Then is discussed, with a unified view, the success of some existing metaheuristics, which can however be considered within the CNS framework, in various fields: graph coloring, frequency assignment in telecommunication networks, vehicle fleet management with maintenance constraints, and satellite range scheduling. Some concluding remarks are given in order to have guidelines for the adaptation of CNS to other problems. This is a joint work with Michel Vasquez (Alès School of Mines, France).