Groupe d’études et de recherche en analyse des décisions

G-2013-12

Variable Neighborhood Search for Extremal Graphs. 28: AutoGraphiX After Fifteen Years

, , et

Introduced during the late nineties of the last century, Variable Neighborhood Search (VNS) was first designed for solving specific problems in combinatorial and global optimization. Nowadays, VNS is widely used as a general framework for solving many different scientific problems and even in scientific discovery. Actually, it is used for discovery in graph theory. The AutoGraphiX (AGX) system exploits different techniques from Variable Neighborhood Search to find extremal graphs, with respect to the maximization or minimization of a graph invariant, and then uses them for generating conjectures. AGX uses three approaches for conjecture-making: analytic, algebraic and geometric . In this paper, we describe the AutoGraphiX system and the VNS used in its optimization component. We present a survey of the conjectures and results obtained with AGX. Different forms of results that can be studied by AGX, and future development in the system are also discussed. Moreover, more than 150 open conjectures are mentioned.

, 60 pages