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: Melih Celik (University of Bath), Eun-Seok Kim (Queen Mary University of London), Gunes Erdogan (University of Bath), Antonio Martinez-Sykora (University of Southampton), Bo Chen (University of Warwick), Adam Letchford (Lancaster University), Carlos Lamas Fernandez (University of Southampton)
PRE-REQUISITES
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 (e.g., 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, branch-and-price, and Benders decomposition. Valid inequalities, polyhedra and facets, separation, computational aspects. Formulations using column generation, pricing algorithms, branching strategies.
7. Applications of combinatorial optimisation. Integer programming methods for data science. Case study and computer lab sessions. Combinatorial optimisation in practice.