Combinatorial optimisation for semigroups

半群的组合优化

• 批准号: 1948246
• 金额: --
• 依托单位: University of St Andrews
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2017
• 资助国家: 英国
• 起止时间: 2017 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-1948246
• 关键词: Combinatorial; optimisation; semigroups

Semigroups are fundamental algebraic objects. They arise in many areas throughout mathematics and theoretical computer science. While semigroups have a rich theory, the less-rigid structure they have compared to groups makes them more difficult to work with. In fact, a common theme in Computational Semigroup Theory (CST) is considering semigroup problems as a problem in group theory together with a problem in combinatorics. However, the added combinatorial sub-problem can lead to problems for semigroups being much more computationally expensive than the corresponding problems for groups.Combinatorial optimisation is concerned with efficiently finding solutions to combinatorial problems which cannot realistically be found with an exhaustive search. A classic example is the "travelling salesman" problem, which asks for the shortest distance a salesman must travel to visit a number of cities exactly once. For 20 cities, there are over 2 quintillion different possible routes to check, which is unfeasible in any reasonable amount of time. However, far more efficient algorithms exist which can find optimal routes for even much larger numbers of cities. In addition, there are heuristic methods which can find approximate solutions very quickly. Heuristics, approximation, parallelization and reduction of search space through symmetries are examples of techniques from combinatorial optimisation which have applications throughout mathematics and computer science. As many areas can benefit from combinatorial optimisation techniques, general-purpose solvers for combinatorial problems have been developed. However, these solvers are not well-suited to problems in CST, as they cannot efficiently represent certain aspects of the problems. This project will bring the techniques of such solvers to bear on problems in CST. Specific problems in mind include:(Di)graph homomorphisms and endomorphismsTranslations and the translational hull of semigroupsMaximal subsemigroupsMinimal generating sets of semigroupsNormalisers and automorphism groups of semigroupsSemigroup isomorphisms and homomorphismsLattices of congruencesIntersections of subsemigroups and inverse subsemigroupsFor all of the identified problems, theoretical research will lead to practical computer implementations. Completed work will be included in the Semigroups package (J. D. Mitchell and others, 2017) for the free and open source Computational Algebra software GAP (The GAP Group, 2017). Work in development will be available through a hosting service for open source software, GitHub. Algorithms that are performance-critical will be implemented in a standalone C/C++ library, accessible through Python. A recent trend in mathematics has been the use of computational tools to analyse examples in search of theoretical results. For example, researchers may wish to verify a new conjecture on all finite groups less than a certain order. This might not be realistic for a researcher in Semigroup Theory: the number of semigroups of size 10 is a 20-digit number. By providing new and improved tools in CST, and enabling currently-unfeasible computations, this project will open new avenues of mathematical research. J. D. Mitchell and others. (2017). Semigroups - GAP package, Version 3.0.7. doi:10.5281/zenodo.592893The GAP Group. (2017). GAP - Groups, Algorithms, and Programming, Version 4.8.8 (http://www.gap-system.org).

半群是基本的代数对象。它们出现在数学和理论计算机科学的许多领域。虽然半群有丰富的理论，但与群相比，它们的结构不那么刚性，这使得它们更难处理。事实上，计算半群理论（CST）中的一个共同主题是将半群问题视为群论中的问题和组合学中的问题。然而，增加的组合子问题可能会导致问题的半群是更昂贵的计算比相应的问题的group.Combinatorial优化关注的是有效地找到解决方案的组合问题，实际上不能找到一个详尽的搜索。一个经典的例子是“旅行推销员”问题，该问题要求推销员必须旅行一次才能访问多个城市的最短距离。对于20个城市来说，有超过200亿个不同的可能路线需要检查，这在任何合理的时间内都是不可行的。然而，存在更有效的算法，可以为更多的城市找到最佳路线。此外，还有一些启发式方法可以非常快速地找到近似解。启发式，近似，并行化和减少搜索空间，通过对称性是从组合优化技术的例子，在整个数学和计算机科学的应用。由于许多领域可以从组合优化技术中受益，因此已经开发了用于组合问题的通用求解器。然而，这些求解器并不适合CST中的问题，因为它们不能有效地表示问题的某些方面。这个项目将带来的技术，这样的解决承担在CST的问题。具体问题包括：（迪）图同态和自同态翻译和平移船体的半群最大子半群最小生成集的半群正规化和自同构群的半群同构和同态格的同余交叉的子半群和逆子半群对于所有的确定的问题，理论研究将导致实际的计算机实现。完成的工作将包括在半群包（J。D。Mitchell等人，2017年）的免费和开源计算代数软件GAP（差距集团，2017年）。开发中的工作将通过开源软件GitHub的托管服务提供。性能关键的算法将在独立的C/C++库中实现，可通过Python访问。数学中最近的一个趋势是使用计算工具来分析实例以寻求理论结果。例如，研究人员可能希望验证一个关于所有小于某个阶的有限群的新猜想。这对于半群理论的研究人员来说可能不现实：大小为10的半群的个数是20位数。通过在CST中提供新的和改进的工具，并使目前不可行的计算成为可能，该项目将开辟数学研究的新途径。J. D.米切尔和其他人。（2017年）。半群- GAP包，版本3.0.7。doi：10.5281/zenodo.592893 GAP集团。（2017年）。GAP -组、算法和编程，版本4.8.8（http：www.gap-system.org）。