权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Circuit Walks in Optimization

AF：小：优化中的电路行走

基本信息

批准号：
2006183
负责人：
Steffen Borgwardt
金额：
$ 23.36万
依托单位：
University of Colorado at Denver-Downtown Campus
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006183&HistoricalAwards=false
关键词：
AF Small Circuit Walks Optimization

项目摘要

The field of optimization provides powerful tools for finding optimal solutions to mathematical programs based on complex real-world problems. However, the computation of a better solution is just a first step towards the greater goal of actually implementing it in practice. In many applications, a gradual transition to a new transportation plan, a new schedule, a new database structure, or a new software solution is required. Such a transition should be a short sequence of simple and natural steps that satisfy a combination of optimality criteria and restrictions associated with the problem. The goal of this project is the design, study, and implementation of algorithms for optimal gradual transitions between solutions of a mathematical program. The ability to efficiently construct such a transition will enable a wealth of new applications. The project will raise awareness in the scientific community to go beyond just solving a problem and will advance knowledge on the transfer of computational results to practice. The research is complemented with synergistic education and outreach activities, including new courses, the training of students, and a workshop bringing together students from across the country with international experts. The impact will be tested in applications, involving students through a collaboration with the Auraria Library's Data to Policy Project.For the polyhedra arising in linear and integer programming, a transition between two solutions can be modeled as a walk along the so-called circuits, the elementary, support-minimal difference vectors retaining feasibility. The circuits contain valuable information on the underlying application. Each step of a circuit walk is a meaningful, human-interpretable step towards the new solution. This project aims to provide a broad, comprehensive approach to the efficient construction of optimal circuit walks in various settings. The main settings are circuit walks between two given solutions, motivated by the need for gradual transitions in practice. Further, circuit walks are a generalization of edge walks, and the corresponding circuit diameters provide a fresh point of view on the polynomial Hirsch Conjecture. Finally, augmentation along circuits is a generalization of the famous simplex method and gives a new way to deal with degenerate polyhedra and to study the existence of a polynomial pivot rule. The methods will combine applied graph theory, polyhedral theory, mathematical programming, and complexity theory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

优化领域为寻找基于复杂现实问题的数学程序的最优解提供了强大的工具。然而，计算出更好的解决方案只是迈向在实践中实际实现它的更大目标的第一步。在许多应用程序中，需要逐步过渡到新的运输计划、新的时间表、新的数据库结构或新的软件解决方案。这种转换应该是一系列简单而自然的步骤，满足与问题相关的最优性标准和限制的组合。这个项目的目标是设计、研究和实现一个数学程序的解之间最优渐进转换的算法。有效地构建这种转换的能力将使大量新应用程序成为可能。该项目将提高科学界的意识，使其超越仅仅解决一个问题，并将推进关于将计算结果转化为实践的知识。这项研究还辅之以协同教育和外联活动，包括开设新课程、培训学生和举办一个讲习班，让全国各地的学生与国际专家一起参加。影响将在应用程序中进行测试，通过与Auraria图书馆的数据到政策项目的合作，让学生参与其中。对于线性和整数规划中产生的多面体，两个解决方案之间的过渡可以建模为沿着所谓的电路行走，基本的，支持最小差分向量保持可行性。电路包含有关底层应用程序的有价值的信息。环形行走的每一步都是迈向新解决方案的有意义的、人类可解释的一步。本项目旨在提供一种广泛、全面的方法来有效地构建各种环境下的最佳电路行走。主要设置是在两个给定的解决方案之间的电路行走，这是由于在实践中需要逐步过渡。此外，回路游动是边游动的泛化，相应的回路直径为多项式赫希猜想提供了一个新的视角。最后，沿回路增广是对著名的单纯形法的推广，为处理退化多面体和研究多项式枢轴规则的存在性提供了一条新的途径。这些方法将结合应用图论、多面体理论、数学规划和复杂性理论。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。