Instructor: M. C. Pinar

Room: 321B

Office Hours: Tuesday 3-5 pm.

Reference Books:

- Linear Programming by V. Chvatal
- An introduction to complexity, polyhedral theory and combinatorial optimization by G. Dahl
- Lecture notes by R. Weber (ps)

**Topics
to be covered:**

- Generalities on Linear Algebra
- Statement and Geometry of the Linear Programming Problem, Some Properties
- Applications from Structural Design, Electrical Engineering, Control Theory ..
- Duality Theory, Theorems of the Alternative
- Applications from Finance
- Sensitivity Analysis
- Solution of Linear Programs by the Primal Simplex Method
- Large Scale Issues, Column Generation, Dantzig-Wolfe and Benders' Decomposition
- The Dual Simplex Method
- The Ellipsoid Method
- Network Flow Problems; Network Simplex, Max-Flow Min-Cut Theorem ...

In addition to those, the students
are expected to acquire basic skills in using the AMPL modeling language.
For general information see AMPL's site.
You can find a library of ampl solution models here.

Grading

Homeworks: 40 % Homework #1 is here. Due date: October 8, 2001.

Homework #2 is here. Due date: October 17, 2001.

Homework #3 is here. Due date: October 30, 2001.Last year I assigned 3 hws from the pool of problems. Their solution files are posted here: hw1, hw2, hw3, and a fourth extra hw4(questions and solutions). The final examination and solution can be downloaded here as well.

Midterm Test: 30 % Date: November 5, 2001 (postponed to 14.11.2001). Final: 30 % Date: January 9, 2002 .

Announcement: 28.9.2001: First homework will be assigned Monday, 1.10.2001

1.11.2001: First homework graded! Can be picked from my office
along with solution sheet.

2.11.2001: Second homework graded and ready to be picked up along
with solution sheet.

: Third hw expected to be graded and ready by friday,
the 9.11.2001

: Fourth hw graded, can be picked from TA's office,