Department of
Mathematical Sciences
CARNEGIE MELLON UNIVERSITY
OPERATIONS RESEARCH I 21-292
1. COURSE OBJECTIVES
To develop and extend the students knowledge of mathematical
techniques underlying the application of mathematical ideas in
solving optimization problems.
2. BASIC INFORMATION
Instructor: Professor Frieze.
Time and location: Class
Monday, Wednesday, Friday, 10.00AM-10.50AM in Posner 151.
Recitation: Group A, Tuesday 9.00AM-9.50AM in WEH5302.
Group B, Tuesday
10.00AM-10.50AM in WEH4709.
Office hours:
Professor Frieze: WEH6204, Monday,
Thursday, 11.00AM - 12.00PM in WEH6204.
TA Sherry Sarkar: Tuesday, 11.00AM - 1.00PM in WEH8213.
TA Freya Zhai: Friday, 1.30PM - 3.30PM in WEH7215.
2.
RESOURCES
BOOK: A Gentle Introduction to Optimization by B. Guenin, J.
Könemann, L. Tunçel is recommended.
OR1_Notes.
Professor Offner's
course material.
Python program 1 to illustrate
the Simplex Algorithm.
Python program 2 to
illustrate the Simplex Algorithm.
3. TEST SCHEDULE
Two in class
tests: February 16, March 27 plus a final.
4 HOMEWORK
Weekly homework will be posted on Canvas, usually due on Wednesday.
LATE HOMEWORK CANNOT BE ACCEPTED.
5. GRADE SCHEME
Homework: 10%; Tests 25%
each; Final 40%.
Grade cutoffs will be no
higher than D: 60, C: 70, B: 80, A: 90.
6 TOPICS
1. Linear Programming
(a) Formulations of LP models.
(b) Simplex Algorithm and extensions.
(c) Duality.
(d) Geometry.
(e) Two-Person Zero-Sum games.
2. Integer Programming.
(a) Formulations of IP models.
(b) Cutting plane algorithm.
(c) Branch and Bound.
(d) NP-completeness.
3. Nonlinear
Programming.
(a) Convex sets and functions.
(b) Local and global optima.
(c) Steepest descent algorithm.
(d) Lagrangean duality.
(e) KKT conditions.