Computational, Combinatorial, and Geometric Aspects of Linear Optimization

线性优化的计算、组合和几何方面

• 批准号: RGPIN-2015-06163
• 负责人: Deza, Antoine
• 金额: $ 2.04万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=682175
• 关键词: Computational; Combinatorial; Geometric; Aspects; Linear

Rational decision-making through quantitative modelling and analysis is the guiding principle behind operations research, a field with several far-reaching applications across engineering, sciences, and industry. Finding optimal allocations of resources, scheduling tasks, and designing prototypes are a few of the areas operations research is concerned with. These problems can often be formulated, or approximated, as linear optimization problems, which involve maximizing or minimizing a linear function over a domain defined by a set of linear inequalities. The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization. The algorithmic issues are related to the combinatorial and geometric structure of the feasible region.***In the last few years, there has been substantial progress in both the geometric analysis of linear programming algorithms and novel models for integer programming. The research proposal aims at consolidating and preserving the momentum in several research areas related to the computational, combinatorial, and geometric aspects of linear optimization with a focus on the analysis of worst-case constructions leading to computationally highly challenging instances. Developing new models to handle application driven questions forms another key focus of this research proposal. The anticipated outcome and significance include fostering cutting edge research and triggering novel approaches. Tightening of the bounds, deeper understanding of the interactions between the algorithmic performance and the structural properties of the input have the potential to stimulate novel approaches for solving linear optimization problems. The proposed methodology is based on a combination of novel constructions and worst-case examples and a tighter analysis of the current bounds and results such as a strengthening of the upper bound for the diameter of polytopes, a counterexample to the Hirsch conjecture, an exponential counterexample to the continuous analogue of the polynomial Hirsch conjecture, and continuous generalizations of the Klee-Minty construction.***Supervision and training of highly qualified personnel is an essential part of my research proposal. As the head of the Advanced Optimization Laboratory (AdvOL), I will continue to seek top graduate students and further strengthen the reputation of AdvOL as one of the leading optimization research groups in Canada. I will nurture multifaceted, multidisciplinary training that produces highly marketable, qualified personnel for both industrial and academic positions. This will develop optimization models, algorithms, software and produce Highly Qualified Personnel to assist Canadian enterprises in strategic sectors of the economy, such as information technology, design, manufacturing, and transportation.**

通过定量建模和分析进行理性决策是运筹学背后的指导原则，运筹学是一个在工程、科学和工业领域有着广泛应用的领域。寻找资源的最佳分配，调度任务，设计原型是运筹学关注的几个领域。这些问题通常可以公式化或近似为线性优化问题，其涉及在由一组线性不等式定义的域上最大化或最小化线性函数。单纯形法和原对偶内点法是目前求解线性优化问题的最成功的算法。算法问题与可行域的组合和几何结构有关。在过去的几年里，有两个线性规划算法的几何分析和整数规划的新模型取得了实质性的进展。该研究计划的目的是巩固和保持势头，在几个研究领域相关的计算，组合，和几何方面的线性优化，重点是分析的最坏情况下的结构，导致计算上具有高度挑战性的情况。开发新的模型来处理应用程序驱动的问题是本研究提案的另一个重点。预期的成果和意义包括促进前沿研究和引发新的方法。收紧的边界，更深入地了解之间的相互作用的算法性能和结构属性的输入有可能刺激新的方法来解决线性优化problem. The建议的方法是基于一个新的结构和最坏情况下的例子和一个更严格的分析目前的界限和结果，如加强上限的直径多面体，赫希猜想的一个反例，多项式赫希猜想的连续类似物的指数反例，以及Klee-Minty构造的连续推广。监督和培训高素质的人才是我的研究建议的重要组成部分。作为高级优化实验室（AdvOL）的负责人，我将继续寻求顶尖的研究生，并进一步加强AdvOL作为加拿大领先的优化研究小组之一的声誉。我将培养多方面、多学科的培训，为工业和学术职位培养出高度适销对路的合格人才。这将开发优化模型，算法，软件和培养高素质的人才，以帮助加拿大企业在经济的战略部门，如信息技术，设计，制造和运输。