Combinatorial Optimisation, University of Southampton - 4th - 8th September 2017
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), Julia Bennell (University of Southampton), Bo Chen (University of Warwick), Adam Letchford (Lancaster University), Chris Potts (University of Southampton), Dolores Romero (University of Oxford).
The basics of linear and integer programming
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.
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, network flow and matching 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 supply chains.
PRINCIPAL TOPICS OF LEARNING
- 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.
- Computational Complexity. Analysis of worst-case running time of algorithms (sorting, matrix multiplication, divide and conquer, dynamic programming), data structures. NP-completeness, reducibility.
- 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).
- Network flow algorithms: Maximum flow problem, augmenting paths, max-flow min-cut, Ford-Fulkerson algorithm and its variants. Minimum cost flow problem.
- Matching algorithms. Bipartite matching, augmenting paths, assignment problem, Hungarian algorithm.
- General Solution Approaches. Branch and bound, dynamic programming, constraint satisfaction, Lagrangean relaxation.
- Branch and cut. Valid inequalities, polyhedra and facets, separation, computational aspects.
- Danzig Wolfe Decomposition. Formulations using column generation, pricing algorithms, branching strategies.
- Benders Decomposition.
- Applications in supply chains. Classic models: facility location, economic lot sizing, vehicle routing. Solving a production/distribution problem using branch and price.
- Start Date: 04/09/2017
- End Date: 08/09/2017
- Location: University of Southampton
- Address: Mathematical Sciences Department Highfield Southampton SO17 1BJ