C&O 350 - Linear Programming (WINTER SEMESTER 1996)

Information related to the teaching activities of Professor Henry Wolkowicz is available. The material is related to the course taught in the WINTER SEMESTER 1996 (with Prof. Cunningham).

Please note that all files are accessible by anonymous ftp to orion.uwaterloo.ca:pub/henry/teaching/w96/350.w96.

Available:

• course handout
  office hours, marking schemes, ...
• outline
  chapters & sections covered/not covered , WWW resources
  (This outline will get more detailed as the course progresses.)
• Assignments, Midterm, and Solutions
• Course Notes
• Matlab Programs
• Books, other References, and Interesting Related Sites
• Final Comment; and Marks

For previous years assignments, midterms, etc... please go to the home pages for the previous years. Please start at the teaching section

Assignments, Midterm, and Solutions

the latest list of marks (sections 1 and 2).

The file lpmovie.tar.Z contains all the files you need to run the solution matlab files. This file is available in the same directory as the solution files.

• assignment 1 and solutions for assignment 1 and comments on solutions for assignment 1.
• assignment 2 and solutions for assignment 2. and comments on solutions for assignment 2.
• assignment 3 and solutions for assignment 3. and comments on solutions for assignment 3.
• assignment 4 and solutions for assignment 4.
• assignment 5 and solutions for assignment 5 and comments on solutions for assignment 5.
• solutions for assignment 6
• midterm, winter/96 and comments on midterm winter/96. (solutions are in the library)
• midterm, winter/95 and solution file.

Course Notes

• Linear Programming at NEOS; misc. information.
• history and FAQ (frequently asked questions) for linear programming;
• Notes from Joseph Cheriyan on:
  dictionaries, pivots, 2-phase simplex, sensitivity analysis, Gomory's cutting plane method
• LPs in Equality Form
• matrix formulae (and exercises) for the revised simplex method;
• Sensible Rules for Remembering Duals - the S-O-B Method;
• example of the revised simplex method;
• practice problems, outline for the final exam, and assignment 6 of fall/95.
• a short description of the affine scaling (interior point) algorithm for solving LPs. Much more information on interior point methods can be obtained here.
• notes on primal-dual interior-point algorithms for solving LPs.
• An Operations Research home page with LOTS of useful information, e.g. jobs, FAQs, addresses, ...;
• WWW Undergraduate Page at SIAM provides a forum for undergraduate mathematics.

Matlab Programs

To use these files, make sure that the files simplex.m and reg.m are in your directory. If the files use lpmovie, then you need the appropriate files in your directory. Copy and uncompress the file you are interested in. Then enter matlab to start matlab. Then run the file you are interested in. Matlab is automatically started for you if you click on a .m file.

Some of the available files:

• Matlab Primer
• Matlab FAQs
• Algorithms
• Linear Programming Examples
• miscellaneous information on matlab, including a tutorial.

Algorithms (MATLAB)

• The simplex method solves a minimization LP with general equality and inequality constraints;
• The affine scaling (interior point) solves a minimization LP with equality constraints;

Linear Programming Examples (MATLAB)

• An example that cycles is included;

Final Comment; and Marks

• Good luck on April 11, 1996, 9AM - 12PM.
• YES FINAL marks - when available (sections 1 and 2)
• The marks for the tests and assignments for section 1 - including the mark on the final exam - are now available. Also posted are the final grade for Henry's section on Henry's door MC6065. The final grade for Bill Cunningham's section is also available.

Book, other References, and Interesting Related Sites

---

Books

• G.B. Dantzig (1963) "Linear Programming and Extensions" This is the classical text on LP. When our text by Chvatal appeared, several reviewers stated that it is the first book with a solid contribution since Dantzig's book.
• S.I. Gass (1975) "Linear Programming"
• R.I. Rothenberg (1979) "Linear Programming"
• D.G. Luenberger (1984) "Linear and Nonlinear Programming" Good insights and explanations for duality theory. In particular, see the interpretation of duality theory for the diet problem.
• K.G. Murty (1983) "LINEAR PROGRAMMING" This is the encyclopedia of books on linear programming - that is the reason for the caps in the title. However, there are also lots of numerical examples.
• M. Sakarovitch (1983) "Linear Programming"

---

Other References

• The Diet Problem: An Application of Linear Programming, a description, software, etc... (from Jon Lee).
• "Interior point methods for constrained optimization," appeared in Acta Numerica pages 341-407, 1992, by Margaret H. Wright, who is from AT&T Bell Laboratories Computing Science Research Center.
• myths and paradoxes for mathematical programming, by H. Greenberg.

Home Page