Pierre Hansen and Gilles Caporossi - Variable neighborhood search for extremal graphs A.  computer-aided search and applications

Finding extremal graphs for some invariant, or for a function of several invariants, possibly subject to constraints, can be viewed as a problem of combinatorical optimization on an infinite familly of graphs. Consequently, powerful metaheuristics may be used to solve this problem. The Variable Neighborhood Search (VNS) metaheuristic, is used within the system AutoGraphiX (AGX), which has many capabilities such as finding counter-examples to conjectures, or suggesting new ones.

The system has been used to study different problems in graph theory, some interesting but unexpected results were found and will be presented here.