MA446 - Combinatorial Optimization

Spring 2013 - 4th Period

Ever wonder...
(1)  How one can evaluate the safety of proposed building designs, in terms of building evacuation in the event of an emergency?

(2)  How to schedule a set of 100 jobs on 10 parallel machines, where each job is made available at different times, is expected to be completed at different times, have different processing times?

(3)  How to assign different modules of a program to multiple processors in a way that minimizes the collective costs of interprocessor communication and computation?

(4) How medical school graduates are assigned to hospitals for their residencies?
This course deals with formulating these and other problems as mathematical optimization models.  Optimization models similar to these are often part of a branch of mathematics known as Operations Research.  We will derive algorithms for solving such problems.  In the process, we will describe how algorithms for optimization problems are typically created, from deciding what optimization criteria need to be met, how to represent potential optimal solutions, and how to improve upon current solutions until we are at the optimal one.

The mathematical models we will be studying are known as combinatorial optimization models.  These typically include network models such as spanning trees, shortest path models, maximum flow models, minimum cost network flow models, matchings, and others.  Typically (but not always), the models are graph-based.  In addition, we will look at how these and other models are currently being used to solve many real-world problems.

Course Structure

Our goal is to learn how to develop algorithms "from the bottom up", using nothing but a problem description.  This involves generating the necessary theory and understanding of the problem.  From there, we will do computational analyses of the algorithms to see how fast they run and how we can improve upon their running times.

There will be a combination of homeworks, projects (with some computing element possible but not required), and (take-home) tests.

This is an applied math course for computer scientists, engineers, and, of course, mathematicians.  It assumes elementary background in graph theory, and a course or two in discrete mathematics.

Job Outlook - from Occupational Outlook Handbook

"Employment of operations research analysts is expected to grow by 15 percent between 2010 and 2020, about as fast as the average for all occupations. As technology advances and companies further emphasize efficiency, demand for operations research analysis should continue to grow.

"Applicants need a master’s degree for most operations research positions, but a bachelor’s degree is enough for many entry-level positions. Many schools offer bachelor’s and advanced degree programs in operations research, but it is common for analysts to have degrees in other quantitative fields, such as computer science and mathematics."