The Cut Polytope and Related Convex Bodies

优化是指当一个人面临大量可能的选择时，找到“最佳”选择的方法。更正式地说，它处理受各种约束的某些决策变量的函数的最大化（或最小化）。提议的项目涉及一个被称为最大切割问题的优化问题。它关注的是将一个图划分为两个部分，以便最大化从一个部分到另一个部分的边的数量。最大切问题本身就是一个有趣的问题，它也有许多应用，例如在计算机科学、电信、统计学、理论物理、计算生物学和数学分支，如组合学、图论和度量空间理论。最大割问题在理论和实践上都是一个难以解决的问题。虽然有很好的启发式方法可以获得大型实例的高质量解决方案，但最先进的精确方法能够解决只有大约100个顶点的实例，以证明最优性。该项目的主要目标是加深我们对最大切割问题的理解，设计出能够解决更大实例的方法，并将这些方法作为计算机软件实现。要做到这一点，必须对被称为切割多面体的特定几何对象和某些相关几何对象进行理论研究。

Optimisation is concerned with methods for finding the 'best' option when one is faced with a huge range of possible options. More formally, it deals with maximising (or minimising) a function of some decision variables, subject to various constraints. The proposed project is concerned with an optimisation problem called the max-cut problem. It is concerned with partitioning a graph into two pieces so as to maximise the number of edges crossing from one piece to the other.As well as being an interesting problem in its own right, the max-cut problem also has many applications, for example in computer science, telecommunications, statistics, theoretical physics, computational biology, and branches of mathematics such as combinatorics, graph theory and the theory of metric spaces.The max-cut problem is difficult to solve both in theory and practice. Although there are good heuristic methods available which can obtain good quality solutions to large instances, the state-of-the-art exact methods are capable of solving instances with only up to around 100 vertices to proven optimality.The main goals of the proposed project are to deepen our understanding of the max-cut problem, to devise methods which are capable of solving larger instances to optimality, and to implement these methods as computer software. To do this, a theoretical study will have to be made of a certain geometric object known as the cut polytope, and certain related geometric objects.