Computational Geometry:Solving Hard Optimization Problems (CG:SHOP)

计算几何：解决硬优化问题 (CG:SHOP)

• 批准号: 444569951
• 负责人: Professor Dr. Sándor Fekete
• 金额: --
• 依托单位: Institut für Betriebssysteme und Rechnerverbund
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/444569951?language=en
• 关键词: Computational; Geometry; Solving; Hard; Optimization

In the over 40 years since the beginning of Computational Geometry, a widerange of optimization problems have been proposed and investigated bycomputational geometers, mainly from a theoretical point of view. Many of thosetasks belong to the NP-hard class of problems, for which the existence ofpolynomial-time algorithms implies P=NP. While Computational Geometry hasconsidered a wide spectrum of NP-hard optimization problems, positive resultstypically imply polynomial-time, constant-factor approximation algorithms,without much regard for practical solution quality, realistic running times, oreven exact solutions. In principle, this is the approach taken by therelatively new area of Algorithm Engineering; however, the impact on hardproblems treated in the community of Computational Geometry has been ratherlimited, as the focus has been more on streamlining theoretical computationalcomplexity, rather than exact methods.This seam between separate successful areas is precisely where our projectintends to bring new contributions, making use of methods from CombinatorialOptimization, based on the recognized expertise in all three areas. At theconcrete level, we will study a selection of different, natural geometricoptimization problems that have enjoyed attention from the perspective ofComputational Geometry, but are still lacking practical approaches to computingprovably optimal or near-optimal solutions. This involves applying tools andtechniques from Combinatorial Optimization and Algorithm Engineering to solveproblems from Computational Geometry, but also algorithmic methods fromComputational Geometry itself. For these problems, we will providecomputational results, based on benchmark instances and solution methods thatcan serve as reference points, both for specific instances (for which we willprovide provably optimal or near-optimal solutions), as well as for particularalgorithmic approaches (for which we will provide practical experiments that gobeyond worst-case bounds). At the general level, we will develop generic toolsand methods for solving geometric optimization problems with practically usefulperformance, by making use of sparsification techniques to get good solutionsto very large instances, for dealing with inaccurate data and error analysis,and for generally modeling, developing and testing. Moreover, we will establishan integrated platform that provides an overall toolbox, a benchmark andresults repository, and a challenge site.In recent months, we have managed to demonstrate the promise of our approach byestablishing and successfully running an annual Computational GeometryChallenge, based on specific problems of this type, indicating the potentialfor changing the scope of a theory-oriented field towards practical usefulnessfor challenging problems.

自计算几何诞生以来的40多年里，计算几何学家们主要从理论的角度提出并研究了各种各样的优化问题。这些任务中的许多属于NP难问题，对于这些问题，多项式时间算法的存在意味着P=NP。虽然计算几何已经考虑了广泛的NP难优化问题，积极的结果通常意味着多项式时间，常数因子近似算法，而不太考虑实际的解决方案的质量，现实的运行时间，甚至精确的解决方案。原则上，这是算法工程这一相对较新的领域所采用的方法;然而，对计算几何领域中处理的硬问题的影响却相当有限，因为重点更多地放在简化理论计算复杂性上，而不是精确的方法。这种独立成功领域之间的接缝正是我们的项目打算带来新贡献的地方，利用组合优化的方法，基于这三个领域公认的专业知识。 在具体层面上，我们将研究一系列不同的自然几何优化问题，这些问题从计算几何的角度受到关注，但仍然缺乏计算可证明的最优或接近最优解的实用方法。这包括应用组合优化和算法工程的工具和技术来解决计算几何的问题，以及计算几何本身的算法方法。对于这些问题，我们将提供计算结果，基于基准实例和可以作为参考点的解决方案方法，既针对特定实例（我们将提供可证明的最佳或接近最佳的解决方案），也针对特定的算法方法（我们将提供超出最坏情况界限的实际实验）。在一般的水平上，我们将开发通用的工具和方法来解决几何优化问题，具有实际有用的性能，通过使用稀疏化技术，以获得很好的解决方案，非常大的情况下，处理不准确的数据和误差分析，以及一般建模，开发和测试。此外，我们将建立一个集成平台，提供一个整体的工具箱，一个基准和结果库，以及一个挑战网站。在最近几个月里，我们已经成功地证明了我们的方法的承诺，建立并成功地运行了一个年度计算几何挑战赛，基于这种类型的具体问题，表明了改变理论导向领域的范围对挑战性问题的实际有用性的潜力。