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

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.


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