Computational Modelling Group

Conference  12th September 2011 9 a.m.  University of Southampton

Combinatorial Optimization

Web page
http://www.natcor.ac.uk/node/6
Categories
Optimisation
Submitter
Elizabeth Roe

Combinatorial optimization 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 optimization problems. The main topics include computational complexity, types of algorithms, optimization problems in networks, branch-and-cut, and branch-and-price.

Main contributors: John Beasley (Brunel University), Bo Chen (University of Warwick), Adam Letchford (Lancaster University), Chris Potts (University of Southampton).

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

  • 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

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

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

SYLLABUS CONTENT

  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), data structures. NP-completeness, reducibility.

  3. Solution Approaches. Branch and bound, dynamic programming, constraint satisfaction, heuristics.

  4. 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).

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

  6. Matching algorithms. Bipartite matching, augmenting paths, assignment problem, Hungarian algorithm. Matching in general graphs, blossoms.

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

  8. Branch and price. Formulations using column generation, pricing algorithms, branching strategies.

Contact
Linda Newby
l.newby@lancaster.ac.uk