The Cut Polytope and Related Convex Bodies
Lead Research Organisation:
Lancaster University
Department Name: Management Science
Abstract
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.
Organisations
Publications
Letchford A
(2017)
A branch-and-cut algorithm for the capacitated open vehicle routing problem
in Journal of the Operational Research Society
Galli L
(2013)
A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs
in Optimization Letters
Letchford A
(2014)
A new separation algorithm for the Boolean quadric and cut polytopes
in Discrete Optimization
Letchford A
(2017)
A note on representations of linear inequalities in non-convex mixed-integer quadratic programs
in Operations Research Letters
Amaral A
(2012)
A polyhedral approach to the single row facility layout problem
in Mathematical Programming
Letchford A
(2014)
An aggressive reduction scheme for the simple plant location problem
in European Journal of Operational Research
Giandomenico M
(2008)
An application of the Lovász-Schrijver M(K, K) operator to the stable set problem
in Mathematical Programming
Letchford A
(2010)
Binary positive semidefinite matrices and associated integer polytopes
in Mathematical Programming
Galli L
(2012)
Complexity results for the gap inequalities for the max-cut problem
in Operations Research Letters
Fortini M
(2010)
Computing compatible tours for the symmetric traveling salesman problem
in Mathematical Programming Computation
Description | The cut polytope is a fundamental convex set that arises in several branches of mathematics, including optimisation, probability theory, the geometry of numbers and the theory of metric spaces. A better understanding of its properties will lead to improved solution methods for certain optimisation problems. The specific results were: 1. The quality of various convex approximations of the cut polytope is now much better understood (Galli & Letchford, 2010; Letchford & Sørensen, 2012). 2. Some of the theoretical and algorithmic results known for the cut polytope were extended and adapted to other optimisation problems, including: global optimisation problems (Burer & Letchford, 2009, 2012, 2014), a graph layout problem (Letchford, Reinelt, Seitz & Theis, 2010), a network design problem (Feremans, Labbé, Letchford & Salazar, 2011), and general mixed-integer nonlinear programs (Galli, Kaparis & Letchford, 2011). 3. On the negative side, it was shown that certain relaxations of the cut polytope are hard to work with computationally (Galli, Kaparis & Letchford, 2012). 4. During the fellowship, many other papers were written and published, concerned with improved solution methods for various other optimisation problems. |
Exploitation Route | Eventually, theoretical advances made in the field of optimisation tend to become incorporated into software, which means that optimisation problems arising in industry can be solved more quickly. |
Sectors | Digital/Communication/Information Technologies (including Software),Other |
Description | Other researchers have been using the results of the project to improve solution algorithms for various optimisation problems. These algorithms have already been incorporated into academic software. Eventually, some of them may find their way into commercial software too. |
First Year Of Impact | 2012 |
Sector | Digital/Communication/Information Technologies (including Software),Other |
Impact Types | Economic |