OR 641

OR 641/MATH 689/OR750 Linear Programming

Fall 2007, Wednesday 4:30-7:10, Krug Hall 209

Professor
Ariela Sofer
Professor and Chair
Science and Technology II, Room 111
phone: (703) 993-1692 or 993-1670 (secretary)
Office hours: Tuesday 2:30--4:00, Wednesday 2:30--4:00, or by appointment
electronic mail: asofer@gmu.edu
fax: (703) 993-1521 (on cover sheet put: A. Sofer, SEOR Dept.)

Text

Stephen G. Nash and Ariela Sofer, Linear and Nonlinear Programming
The first edition was published by McGraw Hill in 1996. We have just completed a second edition to be published by SIAM Books. The pdf files of materials from the second edition corresponding to this course will be available from Professor Sofer. Students will have to sign a statement confirming that they will not share the files, post the files, or transmit the files to anyone else, prior to obtaining the files.
The first edition is out of print. You may still get some copies over the internet. Although the first edition will not be required, some students may find it useful to have the entire book (first edition) available in print form as additional reference.

Course web page: www.gmu.edu/departments/ore/sofer/or641_07.html

Course description
Linear programming problems arise in a wide variety of applications from areas such as finance, transportation, and military. These problems may be very large, potentially involving thousands of constraints and millions of variables. This course focuses on the theory and methods for solving large-scale linear programs. Students will gain hands-on experience in solving large-scale linear programs via computational work with the software CPLEX.

We will take an indepth look at the geometry of linear programs, then discuss the simplex method, duality theory and the dual simplex. We then discuss computational enhancements to the simplex that make it suitable for large sparse programs. These include the revised simplex, basis factorization, and bounded-variable linear programs. We then discuss computational complexity of finite algorithms, and in particular the simplex method. Finally, we discuss nonsimplex methods for linear programming including the ellipsoid method and the primal-dual interior-point method. The course will cover Chapters 2-7, 9, and Appendix A.1-A.5 of the book.

Grading
There will be an in-class midterm examination, and a cumulative final exam . The midterm will make up 25% of the grade and the final exam will make up 35% of the grade. Homeworks will make up 20% of the grade. A computational project will make up the remaining 20% of the grade. In computing the final grade, the lowest homework grade will be dropped. The exams will be open book, open notes.

Fundamental rules

Make-up exams will only be given for extreme situations, and only if I am contacted before the exam is given and full arrangements are established. Full adherence to this policy is the responsibility of the student.
The exam dates above are tentative, and it is the students responsibility to keep abreast of changes.
Homework will be assigned each class, and usually collected. All work must be clearly written. Illegible work will not be accepted.
There will be a penalty of 10% of the total grade for every day homework is late.

Other information
Getting a computer account
IT&E Computer Labs (schedules, software, etc.)

OR 641/MATH 689/OR750 Linear Programming

Course Materials

Homework to date

Project