Computational discrete optimization

Combinatorics and Optimization (CO) 759 Topics in Discrete Optimization

Topic for winter 2015:

Computational discrete optimization

Instructor:

Bill Cook

Class times:

10:00-11:20 am, Tuesday and Thursday

We will study solution techniques for problems in discrete optimization, emphazing computational aspects of the theory and algorithms.

The topics will include:

  • Graph/Network algorithms for large-scale problems
  • Linear programming and the cutting-plane method
  • Branch-and-bound
  • Lagrangean duality
  • Dynamic programming (branch-width and tree-width)
  • Local search and simulated annealing
  • Parallel computation (distributed networks, shared-memory)

Throughout the course we will discuss how to best choose implementations to meet the demands of the given problem, including the choice of algorithms, data structures, and computing platforms.

The assignments will consist of implementation projects (students can work in groups of up to three members; it is not necessary for all students to have strong backgrounds in computer programming).