Combinatorial optimisation problems typically involve finding the best arrangement, ordering, or selection of objects. There are numerous applications in Operational Research including scheduling of orders on machines in production industries, routing of vehicles to deliver goods to customers, and assigning of personnel such as nurses or airline crew to work periods. This course provides the main approaches and techniques required to tackle combinatorial optimisation problems. The main topics include computational complexity, types of algorithms, optimisation problems in networks, branch-and-cut, and branch-and-price.

Main contributors: Tolga Bektas (University of Southampton), Trivikram Dokka (Lancaster University), Bo Chen (University of Warwick), Adam Letchford (Lancaster University), Chris Potts (University of Southampton), Dolores Romero (Copenhagen Business School), Vladimir Deineko (University of Warwick)

PRE-REQUISITES

The basics of linear and integer programming

AIMS

The course aims at providing an appreciation of the types of combinatorial problems that arise in Operational Research, and providing knowledge of the main approaches for tackling such problems.

LEARNING OUTCOMES

On completion of the course, the student will be expected to:

•understand the basics of complexity theory and be able to provide proofs that certain problems are NP-hard;

•have knowledge of a range of algorithms for shortest path, minimum spanning tree and network flow problems;

•analyse the worst-case running time of an algorithm;

•have an appreciation of the main types of approaches that can be used for tackling combinatorial optimization problems, together with their limitations;

•understand the principles behind branch-and-cut and branch-and-price, and be able to apply these approaches to new problems;

•have an overview of how combinatorial optimization techniques can be applied in an area such as data science.

PRINCIPAL TOPICS OF LEARNING

1.Introduction. Types of problems (for example, machine scheduling, vehicle routing and the travelling salesman problem, cutting and packing, set covering and partitioning). Integer programming formulations.

2.Computational Complexity. Analysis of worst-case running time of algorithms (sorting, matrix multiplication, divide and conquer, dynamic programming). NP-completeness, reducibility.

3.Shortest path and minimum spanning tree algorithms. Label setting shortest path algorithms (Dijkstra’s algorithm and its variants). Label correcting shortest path algorithms (Bellman-Ford algorithm and its variants). Greedy algorithms for the minimum spanning tree (Kruskal, Prim).

4.Network flow algorithms: Maximum flow problem, augmenting paths, max-flow min-cut, Ford-Fulkerson algorithm and its variants. Minimum cost flow problem.

5.General Solution Approaches. Branch and bound, dynamic programming, constraint satisfaction, Lagrangean relaxation.

6.Branch and cut. Valid inequalities, polyhedra and facets, separation, computational aspects.

7.Danzig Wolfe Decomposition. Formulations using column generation, pricing algorithms, branching strategies.

8.Benders Decomposition.

9.Applications in Data Analysis and Visualisation. Models from regression and classification, clustering and visualisation.