The Cut Polytope and Related Convex Bodies

优化是指当一个人面临大量可能的选择时，找到“最佳”选择的方法。更正式地说，它涉及最大化（或最小化）一些决策变量的函数，受到各种约束。该项目涉及一个称为最大割问题的优化问题。最大割问题（Max-cut problem）是一个复杂的数学问题，它涉及将一个图分成两部分，以使从一部分到另一部分的边数最大化。除了本身是一个有趣的问题外，最大割问题也有许多应用，例如在计算机科学，电信，统计学，理论物理，计算生物学和数学分支，如组合学，最大割问题是图论和度量空间理论中的一个重要问题，无论在理论上还是在实际应用中都是一个难以解决的问题。虽然有很好的启发式方法，可以获得高质量的解决方案，以大的情况下，国家的最先进的精确方法是能够解决的情况下，只有大约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.