# 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.