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
Amaral A
(2012)
A polyhedral approach to the single row facility layout problem
in Mathematical Programming
Burer S
(2012)
Non-convex mixed-integer nonlinear programming: A survey
in Surveys in Operations Research and Management Science
Burer S
(2009)
On Nonconvex Quadratic Programming with Box Constraints
in SIAM Journal on Optimization
Burer S
(2012)
Unbounded convex sets for non-convex mixed-integer quadratic programming
in Mathematical Programming
Caprara A
(2010)
New techniques for cost sharing in combinatorial optimization games
in Mathematical Programming
Caprara A
(2011)
Decorous Lower Bounds for Minimum Linear Arrangement
in INFORMS Journal on Computing
Feremans C
(2011)
Generalized network design polyhedra
in Networks
Fortini M
(2010)
Computing compatible tours for the symmetric traveling salesman problem
in Mathematical Programming Computation
Galli L
(2011)
Gap inequalities for non-convex mixed-integer quadratic programs
in Operations Research Letters
Galli L
(2010)
Small bipartite subgraph polytopes
in Operations Research Letters
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 |