CPSC 5307  
Topics: Discrete Optimization

(Winter Session, Jan-Apr, 2010)

 
 
     
Instructor:

Dave Goforth 

Office:
FA359 (Fraser)
Extension: 
2316 
dgoforth@cs.laurentian.ca
  office hours
 
 
 
Lectures:  Monday, Wednesday

4:00PM

FA 357
Text: Z. Michalewicz & D. Fogel. 20094. How to Solve it: Modern Heuristics, Second edition: Springer.
Evaluation 5 assignments
1 report
5 @ 10% = 50%
50%
 
Website: http://www.cs.laurentian.ca/dgoforth/cpsc5307/outline.htm

There are many problems in the real world that would be impossible to solve without computing power. Even with computers to assist, they are difficult to solve. This course is about attacking these problems.

There may be no obvious way to represent the information in the problem. Sometimes the problem solution must be based on what data is available, not the data you would really like to have.

There may be no obvious algorithm to solve the problem. Or, there may be an algorithm but it performs so poorly that it can't be applied to anything but toy versions of the problem.

The goal of the course is to develop skills for analyzing features of difficult problems and deciding which of a toolbox of solution methods best applies, then adjusting the method to fit the particular features. Part puzzling, part coding, part testing.

In fact, the situation is better than it appears. There are some general methods that can be applied to these difficult problems to produce good if not perfect results. Often problems that on the surface appear quite different turn out to be very similar in terms of the methods that can be applied.

 

Back to Dave Goforth's page