Combinatorial and global optimization with applications to data mining

点击翻译按钮获取中文摘要

The proposed research focusses on development of methods (i.e. theorems, exact algorithms and heuristics) and applications of mathematical programming, the aim of which is to solve multivariate, constrained optimization problems. I work in several subfields, with many collaborators. - The first subfield is global optimization whose purpose if to determine global optima of nonlinear, nonconvex functions subject to linear or nonlinear, convex or nonconvex constraints. We will continue our study of problems with particular structure and transformation of problems one into the other, using the concept of embedding of algorithms. This should lead to generalization, simplification and unification of algorithms for several problems as e.g. concave programming, optimization of the efficient set of multicriteria linear programs, etc. - The second subfield is decomposition methods for large-scale combinatorial optimization problems, and their combination with integer programming, interior point methods and global optimization. - A third subfield is metaheuristics. We will build upon the success of the Variable Neighborhood Search (VNS) metaheuristic to obtain near optimal solutions to various problems but also to enhance exact algorithms (e.g. by stabilizing or focusing column generation) and provide performance guaranties for heuristics. - A fourth subfield is experimental mathematics. We will pursue the development of a new type of application, i.e. finding conjectures in graph theory by computer with the VNS-based AutoGraphiX system. Developed since 1997 it has already led to finding over 1600 conjectures, more than 800 of which have been proved automatically and over 400 by hand in forty papers. These conjectures are increasingly being solved by mathematicians in several countries, particularly those on algebraic graph theory.