Perfect Copositive Matrices

在这个项目中，我们发展了一个完全共合矩阵的理论。这些矩阵可以被用来，例如，以系统的方式离散共合矩阵的凸锥。这导致了在组合优化中的可能应用，例如对完全正矩阵的有理证明的算法计算。我们项目的一个核心组成部分——对新理论的算法应用很重要——是对完美合成矩阵的邻域图的研究。这个图表现为多面体表面的边图，多面体表面的面是由互补矩阵的最小向量决定的。因此，对于邻域图的算法处理，必须计算合成矩阵的最小向量。为了完成这一重要任务，人们开发并测试了新的方法。这些用于确定最小向量的新算法本身具有有趣的未来应用潜力。作为项目的一部分，我们将开发各种算法的实现，并将它们与已知方法进行广泛的比较。最终，我们的目标是发布易于使用的软件，以及用于未来研究的测试实例的相关数据集。

In this project we develop a theory of perfect copositive matrices. These matrices can be used, for example, to discretize the convex cone of copositive matrices in a systematic way. This results in possible applications in copositive optimization, such as the algorithmic calculation of rational certificates for completely positive matrices. A central component of our project — and important for algorithmic applications of the new theory — is the investigation of the neighborhood graph of perfect copositive matrices. This graph appears as an edge graph of a polyhedral surface, whose facets are determined by minimal vectors of copositive matrices. For the algorithmic treatment of the neighborhood graph it is therefore essential to compute minimal vectors of copositive matrices. For this important task new approaches are developed and tested. These new algorithms for determining minimal vectors themselves have the potential for interesting future applications.As part of the project, we will develop various implementations of algorithms and compare them extensively with known approaches. Towards the end we aim to publish software that is easy to use, together with an associated data set of test instances for future research.