AF: Small: Circuit Walks in Optimization

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

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.