Global and combinatorial optimization

所提出的研究集中于方法(即定理、精确算法和启发式)的发展和数学规划的应用，其目的是解决多变量的约束优化问题。我和许多合作者在几个子领域工作。第一个子领域是全局优化，其目的是确定受线性或非线性约束的非线性、非凸函数的全局最优解。我们将继续研究具有特殊结构的问题，并使用算法嵌入的概念将问题转化为另一个问题。这将导致几个问题的算法的泛化、简化和统一，例如凹规划、有效的多准则线性规划集的优化。第二个子域是大规模组合优化问题的分解方法，以及它们与整数规划、内点方法和全局优化的结合。第三个子领域是元启发式。我们将建立在最近的可变邻域搜索(VNS)元启发式算法的成功的基础上，以获得各种问题的接近最优解，并增强精确算法(例如，通过稳定或聚焦列生成)，并为启发式算法提供性能保证。此外，我们还将致力于一种新型应用的开发，即在基于VNS的AutoGraphiX系统中通过计算机发现图论中的猜想。自1997年发展以来，它已经找到了1500多个猜想，其中800多个已经被自动证明，20多篇论文中有350多个是手工证明的。

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 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 subfields is metaheuristics. We will build upon the success of the recent 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. Moreover, 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 1500 conjectures, more than 800 of which have been proved automatically and over 350 by hand in two dozen papers.