Linear Programming
G22.2730, G63.2741
Spring 1998, Mondays 5-7 p.m.
Theoretical, Computational and Practical aspects of Linear Programming
and its generalizations.
Instructor: Michael L. Overton
Office: WWH 529
Telephone: 998-3121
Office Hours: Drop by any time, or send email or call for appointment
Email: overton@cs.nyu.edu
What is Linear Programming?
Short Answer
Long Answer
Prerequisites: undergraduate linear algebra and experience with
writing computer programs. No knowledge of linear programming is
assumed.
Requirements: regular homework assignments, including programming assignments
using Matlab and/or C.
Books
Required Text:
Linear Programming: Foundation and Extensions , R.J. Vanderbei (Kluwer, 1996)
Group Price: $79.95
Recommended alternative general book on linear programming
(not required for course, but less expensive and available in paperback):
Linear Programming,
V. Chvatal (Freeman, 1983)
(The copy at Courant is on reserve, but there are two more copies at Bobst
available as of Feb 3.)
Recommended Book for more in-depth study of modeling and a modeling Language
(not required for course):
AMPL: A Modeling Language for Mathematical Programming ,
R. Fourer, D.M. Gay and B.W. Kernighan (Scientific Press, 1993)
Recommended Book for more in-depth study of interior-point methods
(not required for course, but a bargain price from SIAM in paperback and
destined to be a classic):
Primal Dual Interior-Point Methods , Stephen J. Wright (SIAM, 1997)
Matlab Information
Matlab is a product of
The Mathworks
Try out
A Free Matlab Online Tutorial or look for others by a web
search.
You can take a sealed CD to the ACF Innovation Center (CIWW 2nd floor), to
exchange for a copy of Matlab for your use at home this semester, running
under Windows.
Math Computer Consultant
Homework
Homework 1 (due Feb 2)
Homework 2 (due Feb 9)
Homework 3 (due Feb 23)
Homework 4 (due Mar 2)
Homework 5 (due Mar 9)
Homework 6 (due Apr 6)
Homework 7 (due Apr 20)
Homework 8 (due May 4)
Simplx.m (Matlab code)
Stepsize.m (Matlab code)
Final Homework Policy:
All homework is due May 4. For those who still have bugs in the programming
assingments for HW 6 and 8, I will consider accepting corrected versions
of the programs and summaries of your conclusions up to the final exam,
but you must update me on your progress and get my approval.
There will be a make-up class on Monday May 11. Oral exams will be
scheduled later the same week.