Grant: Discovery Grants Program - Individual

The research project aims at using mathematical programming to develop new algorithms for data mining and scientific discovery. This fundamental tool of operations research may be applied in two ways (i) to obtain algorithms giving a solution to a problem with a proof of optimality and (ii) to obtain heuristics providing optimal or near optimal solution but without any proof of optimality. Mathematical programming will be used to continue the development of the system AutoGraphiX, a system that aims at helping the researcher in graph theory. AutoGraphiX has been developed since 1997, during my PhD thesis and was involved in more than 30 papers. The system first provides extremal (or near extremal) graphs eventually satisfying constraints, for a given problem. The so obtained graphs may be analysed and conjectures could automatically or interactively be made. This research will also continue on the relations finding part, which could not only be applied in graph theory, but also more generally in data mining. When studying some problems with AutoGraphiX, a new technique of proof was found based upon linear programming and involving the number of edges with given end degrees as variables. We propose to use integer variables mij representing the number of edges between a vertex of degree i and a vertex of degree j. The new system ChemoGraphiX is actually being developed based upon this principle. We are also working on clustering. Clustering is one of the major techniques used in data mining. It is mainly used in marketing (segmentation) and localisation, but also in a variety of other applications where grouping observations is needed. We are actually working on the application of column generation to the clustering problem. This algorithm provides the optimal solution with proof of optimality.