Home
Research
Teaching
Other
Spring 2009: Operations Research 21-292
Class information
- Class meetings: MWF 1:30 - 2:20PM, WEH 7500
- Office hours: Th 1:00 - 3:00PM
- Syllabus:
Resources (including text books that are free and legal to download)
- Convex
Optimization by Stephen Boyd and Lieven Vandenberghe
- Introduction
to Linear Programming by Michel X. Goemans
- Optimization Toolbox in Matlab
- Linear programming in Matlab
- Linear programming in Mathematica
- NEOS Solvers
- Integer programming in Matlab
| Course outline (to be updated during the term) | ||
| Date | Topic | Remarks |
| 1/12 |
Two variable LP-model & and its graphical solution | |
| 1/14 |
Solving LP with Matlab | |
| 1/16 |
Solving LP with Matlab (contd.) - Diet Prob. & Loan Policy Model | DP LPM |
| 1/19 |
Martin Luther King Day - no classes | |
| 1/21 |
Introduction to simplex method | hw1 |
| 1/23 |
Simplex method (using Gaussian elimination) | |
| 1/26 |
Simplex method (using the tabular form) | |
| 1/28 |
Big-M method | hw2 |
| 1/30 |
Two-phase method | |
| 2/2 |
Special cases in the simplex method | hw3 |
| 2/4 |
Review session | |
| 2/6 |
Test 1 | sols |
| 2/9 |
Sensitivity analysis | |
| 2/11 |
Sensitivity analysis (contd.) | hw4 |
| 2/13 |
Fundamentals of linear programming (geometry) | notes |
| 2/16 |
Fundamentals of linear programming (bases) | |
| 2/18 |
Revised simplex method | hw5 sols |
| 2/20 |
Revised simplex method (contd.) | |
| 2/23 |
Parametric linear programming | |
| 2/25 |
Introduction to duality | hw6 sols |
| 2/27 |
Strong duality theorem | |
| 3/2 |
Review session | |
| 3/4 |
Test 2 | sols |
| 3/8-13 |
Spring Break | |
| 3/16 |
Minimal-spanning-tree problem (Prim's algorithm) | |
| 3/18 |
Shortest-route problem (Dijkstra's algorithm) | hw7 sols |
| 3/20 |
Shortest-route problem (Floyd's algorithm) | |
| 3/23 |
LP formulation of the shortest-route problem | SRP |
| 3/25 |
LP formulation of the max-flow problem | hw8 sols MFP |
| 3/27 |
The max-flow min-cut theorem | |
| 3/30 |
The Ford-Fulkerson algorithm | |
| 4/1 |
Introduction to integer programming | hw9 PS IST sols |
| 4/3 |
Half-integrality of vertex cover | |
| 4/6 |
Total unimodularity | |
| 4/8 |
Review session | |
| 4/10 |
Test 3 | sols |
| 4/13 |
Branch-and-bound algorithm | |
| 4/15 |
Branch-and-bound algorithm (contd.) | |
| 4/17 |
Spring Carnival - no calsses | |
| 4/20 |
TSP problem and its branch-and-bound solution algorithm | TSP |
| 4/22 |
Unconstrained problems | hw10 sols |
| 4/24 |
The Newton-Raphson method | Newton |
| 4/27 |
Lagrangian multipliers | |
| 4/29 |
Karush-Kuhn-Tucker conditions | |
| 5/1 |
Review session | |
| 5/4 |
Special Office Hours - Monday, May 4, 1:00-4:00p.m. | |
| 5/11 |
Final - Monday, May 11, 5:30-8:30p.m., BH A51 | |