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

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

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.