Using heuristics and mixed-integer programming in chemical graph
theory

Pierre Hansen, Gilles Caporossi and Damir Vukicevic

Mathematical programming is extensively used to solve graph
optimization problems with specific algorithms. It can also be used to
advance the theory of graphs itself,i.e. to provide conjectures,
refutations and proofs (or ideas of proof). Many problems of extremal
graph theory can be expressed as parametric combinatorial optimisation
problems on an infinite family of graphs (or, in practice, on all graphs
with a moderate number of vertices). Such problems are solved with the
AutoGraphiX system using a generic heuristic of Variable Neighborhood
Search type. Moreover, necessary and sufficient conditions for edge
realizability of graphs can be exploited in the case of chemical graphs to
express such problems as mixed-integer programs, as done in the recent
system ChemoGraphiX. Main ideas and results of this research program will
be presented.