| Math 409 Section A |
Spring 2012 |
| DISCRETE OPTIMIZATION
|
| Instructor: |
James Burke |
|
E-Mail: |
burke(at)math(dot)washington(dot)edu |
| Phone: |
543-6183 |
|
Office Hours: |
MW 11:40-12:40pm |
| Office: |
C-443 Padelford |
|
|
& by appointment |
| Pre-Requisites: |
Math 407 |
|
Classroom: |
166 Savery Hall |
| TA: |
Jiashan Wang |
|
Office: |
C-552 Padelford |
| E-Mail: |
jsw1119(at)math(dot)washington(dot)edu |
|
Hours: |
Wed. & Thur. 3-4pm |
URL for the course website:
- http://www.math.washington.edu/~burke/crs/409/
Supplementary Text:
Integer Programming, by Laurence Wolsey, Wiley-Interscience,
New York, 1998.
Discrete Optimization:
Discrete optimization is a branch of optimization that deals with problems
where some or all of the decision variables are required to take integer
values. Integer programming (IP), mixed integer programming (MIP),
network optimization, and combinatorial optimization (COP)
are the primary sub-branches of this field of study.
Application arise in a number of areas where `yes-no' decisions are required
and can be easily modeled by variables taking the values 0 and 1. If a problem
only consists of decision variables taking the values 0 and 1, it is called
binary programming (BIP). Applications range from facility location, capital
investement, electrical networks, telecommunications, transportation,
proteomics, bioinformatics, and supply-chain management to name a few. These
problems are of enormous practical importance, and can be of extremely large
scale.
Course Content:
In this course we focus primarily on integer linear programs, and in particular
network optimization problems. We begin with a description of
the branch and bound technique and show how it can be applied to
general discrete optimization problems. We then quickly review the
simplex algorithm for linear programming discuss total unimodularity.
We then focus on network optimization problems covering Part III of the
course text.
Grading:
Quizzes:
There are 7 fifteen/twenty minute quizzes each worth 70 points. The
quizzes are given on Friday March 30, April 6,13,20,27, and May 11, 18, 25.
The first quiz is a review of 407, and the remaining
quizzes cover the homework of the previous week.
The potential content of
the quiz will be announced the Wednesday before the quiz.
The top 5 scores on the 7 quizzes count toward your grade.
Midterms:
There is one midterm: Friday, May 4. The
content of the midterm will be discussed in advance and a sample midterm
will be distributed before the exam. The midterm is worth 300 points.
Final Exam:
The final exam is to be given on Monday, June 4
from 8:30 to 10:20am in the same room as that for instruction (SAV 166).
The final exam is comprehensive. A sample final exam
will be distributed. The final exam is worth 350 points.
Final Grade:
The total number of possible points is 1000:
| 350 quiz points 300 midterm points 350 final
exam points 1000 points. |
Your final grade will be based on these points.
One class curve is computed
after the final exam has been scored.
Time Conflicts with an Exam:
There will be no make-up exam except
in the case of a documented medical or family emergency.
In the event of an unavoidable conflict with a midterm (an athletic meet,
wedding, funeral, etc...), you must notify me at least 2 weeks before the
date of the exam so that we can arrange for you to take the exam BEFORE the
actual exam date. In the event of an unavoidable conflict with the final
exam, you will need to submit a written petition for this purpose to me
by Wednesday, May 23.
As with exams, make-up quizzes are given only in the case of a documented
medical or family emergency.
Incomplete:
A grade of Incomplete will be given only
if a student is doing satisfactory
work up until the end of the quarter,
and then misses the final exam due to
a documented medical or family emergency.
Important Dates:
Holidays:
Memorial Day, Monday, May 28.
Midterm Date: Friday, May 4.
Final Exam: Monday, June 4, 8:30-10:20 am.