21-257 Models and Methods for Optimization
Department of Mathematical Sciences
CARNEGIE MELLON UNIVERSITY
21-257 Models and Methods for Optimization, Spring 1999
Instructor: B. Doytchinov
Office: WeH6213
Office hours: Mo 10:00-11:30am, Fr 9:30-11:00am
e-mail:bd24@andrew.cmu.edu
| Teaching Assistants |
Sections |
Office |
Office Hours |
| Yi Lu |
A,B |
WeH 6207 |
We 4:00pm - 6:00pm |
| Monica M.
Vandieren |
C |
WeH 7213 |
Mo 3:30pm - 4:30pm
Tu 4:30pm - 5:30pm |
| Alejandro Santos |
D |
WeH 6215 |
Tu 6:30pm - 7:30pm |
COURSE CONTENTS
The course consists of three main parts:
- Preview of Optimization Problems. This includes Chapter 1
and
parts of Chapter 2. We will look at certain basic types of linear
optimization
problems. Also, we will make a quick review/crash course of the
necessary
skills from linear algebra (spans, linear independence, solving
systems of linear equations by row operations).
- Linear Programming. This is the central topic for the
course. It
covers Chapter 3 of the text. We will spend about half of the semester
on it.
- Network Models and Integer Programming. This covers parts
of Chapters 4 and 7. We will study the transportation problem, the
critical path method, the knapsack problem and the traveling salesman
problem.
- Dynamic Programming. Dynamic Programming is probably the
most
interesting topic in Optimization. We will look at parts of Chapter 8
and we will study some examples. This will not be a part of the course per
se,
in the sense that the material covered will not be given on tests or on
the final exam.
TEXT
R.Walker.Introduction to Mathematical Programming, First
Edition.
This book should be available at the campus bookstore by the end of the
first week of classes.
LECTURES and RECITATIONS
There are 3 lectures and only one recitation per week. You are supposed
to attend all lectures and recitation. If you miss a class, it is your
responsibility to make a copy of the classnotes from another student
and make sure you learn what you have missed.
HOMEWORK
Homework is assigned each week, and is due on the Thursday
of the following week. The homework will be collected in recitation, at
the beginning of the session. No late homework will be accepted.
Homework is a required component of the course. Working the
exercises will help you learn, and your graded homework will give you
some feedback on your progress. You
are encouraged to discuss homework problems with each other; however,
the work handed in must be your own. In particular, to avoid any
perception of copying, you
should not read anybody else's work or show your work to anybody else.
CALCULATORS
Calculators will be allowed on tests and finals, as long as they
don't have a QWERTY keyboard. However, none of the problems presented
will actually require the use of a calculator.
GRADES
There will be three in-class tests and a Final exam. The lowest of the
three
test scores will be dropped. The grade will be calculated in the
following way:
50% of the grade come from the two best Tests,
40% of the grade come from the Final Exam,
10% of the grade come from the 10 best homework scores.
Midsemester Grade. The midsemester grade will be calculated
on the base of 60% of Test 1 and 40% of homework to date. No scores
will be dropped in computing the midsemester grade.
No makeup tests will be given - ever. If you miss a test,
that will be the one dropped when
computing the semester score.
Anybody caught cheating on any of the tests or exams will be
assigned a failing grade for the course.
Note that the finals session
ends on May 11, so you should plan on being in Pittsburgh until then.
FINAL EXAM
The final exam has been scheduled for Friday, May 07, 5:30-8:30pm.
There is no special review list or review session for the final.
To review for the test, please look at the homework problems and the
similar ones in the book,
also at the review sheets for the three tests.
The final exam will be comprehensive and will cover all the studied
material from Chapters 1, 2, 3, 4, and 7 (Chapter 8 will not be on the
final; Sensitivity Analysis - Section 3.8 will not be either). In
length (number of problems) the test will be like two to two and a half
tests. The length of each problem will be approximately like on the
tests. There will be some short problems to solve completely, as well
as some bulkier problems in which the solution has been already carried
to
some stage and you have to finish the problem. Three of the problems
will be formulation problems, similar to the ones in sections 1.3, 3.5,
and 7.6. It is advisable to bring a calculator (at least a
four-operations one), you
might need it for the knapsack problem.
Models and Methods for Optimization, Spring 1999
Send me mail:
bd24+@andrew.cmu.edu