Cutting Plane Methods for Combinatorial Optimisation

Many important problems arising in Operational Research (and indeed in other fields) can be modelled as combinatorial optimisation problems (COPs).  At the heart of most exact solution algorithms for such problems is the dynamic generation of additional constraints, called cutting planes.  Algorithms based on cutting planes have had spectacular success.  For example, they have been used to solve real-life instances of the TSP with thousands of cities to proven optimality.

 

Cutting planes work as follows.  First, the COP is formulated as an integer linear programme (ILP).  The continuous relaxation of this ILP is a linear programme (LP), which can usually be easily solved (e.g., by the simplex method).  If the LP solution is integral, the COP is solved.  If it is fractional, one "cuts off" the fractional solution by appending new linear constraints that are violated by that solution, but known to be satisfied by all solutions to the ILP.  The LP is then re-optimised, and the process is repeated.  As the constraints are added, the bound on the optimal profit or cost improves.  This procedure can be embedded within a branch-and-bound tree, leading to so-called branch-and-cut  algorithms. (There are also other variations that work better in some cases, such as branch-and-pricebranch-cut-and-price  and relax-and-cut  algorithms.)

Although cutting planes have been around since the 1960s, researchers are still discovering new families of them, either for ILPs in general, or for specific COPs that have a special structure.  They are also still discovering, e.g., algorithms for generating them, effective rules for deciding which ones to add or drop at any given time, rules for deciding when to cut and when to branch, and various techniques for measuring cut quality.

The goal of this research project would be to derive new and hopefully strong cutting planes for either general ILPs or specific COPs, devise efficient algorithms for generating them, implement those algorithms in computer software, and perform computational experiments on a range of test instances.

Applicants for this research project need to have good qualifications in mathematics or a related discipline, and have experience with computer programming. Experience with LaTeX and/or MatLab would also be desirable, but are not essential as training can be given.

For further information contact Trivikram Dokka or Adam Letchford.

Return to the Optimisation Research Group page.