Combinatorial and global optimization with applications to data mining

组合和全局优化及其在数据挖掘中的应用

• 批准号: 105574-2012
• 负责人: Hansen, Pierre
• 金额: $ 3.93万
• 依托单位: HEC Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=636779
• 关键词: Combinatorial; global; optimization; applications; data

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, constrainedoptimization problems. I work in several subfields, with many collaborators.- The first subfield is global optimization whose purpose if to determine global optima of nonlinear, nonconvexfunctions 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.

拟议的研究重点是方法的开发（即定理，确切的算法和启发式方法）以及数学编程的应用，其目的是解决多变量，约束的临时问题。我与许多合作者一起工作。-第一个子字段是全局优化，其目的是确定非线性，非范围的全局优化，但要受线性或非线性，凸或非convex约束的约束。我们将使用算法嵌入的概念来继续研究问题的特定结构和一个问题转化为另一个问题的问题。这应该导致一些问题的概括，简化和统一算法，例如凹面编程，高效多标准线性程序的优化等。第二个子字段是用于大规模组合优化问题的分解方法，以及它们与整数编程，内部点方法和全局优化的组合。 - 第三个子场是元启发式学。我们将基于可变邻域搜索（VNS）元启发式的成功，以获取各种问题的最佳解决方案，同时也可以增强精确的算法（例如，通过稳定或专注于列的生成）并为启发式提供了性能保证。 - 第四个子领域是实验数学。我们将通过基于VNS的Aptrographix系统来追求一种新型应用程序的开发，即通过计算机中的图理论找到猜想。自1997年以来开发的是，它已经导致发现了1600多个猜想，其中800多个已自动证明，并用40篇论文手工证明了400多个。在几个国家，尤其是代数图理论的数学家，数学家越来越多地解决了这些猜想。