CS 525: Linear Programming Methods - Fall 1997
Schedule
Lecture: 8:50 - 9:40 MWF, 1257 CS&S
Mailing list: cs525-1list@cs.wisc.edu
Course URL: http://www.cs.wisc.edu/~cs525-1
Office: 6391 CS&S
Telephone: 262-4281
E-mail: ferris@cs.wisc.edu
Office Hours: 10:00 - 11:00 Mondays, 8:00 - 9:00 Tuesdays
Office Hours: 4:00 - 5:00 pm Friday 12 December
8:00 - 9:00 am Monday 15 December
Teaching Assistant: Lee Yuh-Jye
Office: 3310 CS&S
Telephone: 262-1721
E-mail: yuh-jye@cs.wisc.edu
Office Hours: 11:30 - 13:00 Friday 12 December
General Course Information
- Course Overview
- Introduction
- Linear Algebra: A Constructive Approach
- The Simplex Method
- Duality
- Geometry
- Computational Considerations
- Interior Point Methods
- Sensitivity Analysis
- Approximation Problems
- The Linear Complementarity Problem
- Class Text: Linear Programming via MATLAB, Michael C.
Ferris and O. L. Mangasarian, available as Handout 1 for CS 525
from DoIT. A postscript version of Chapter 2 can be
downloaded for immediate use.
- Prerequisites Math 443 or 320 or 340 or consent of
instructor
- Assignments and examinations
- Midterm Examination (During class time on November 3 and 5) A
copy of a previous midterm examination can be downloaded:
- Final Examination Monday, December 15 at 12:25 pm in Grainger
1175. A copy of a previous final examination can be downloaded:
- 1 Assignment per week approximately Most of the assignments
will require the use of MATLAB, which will also be used extensively
in the lectures.
- A description of everything you need to do to get set up to use
Matlab in this couse is found in Getting Started
in MATLAB
- A computing project in MATLAB. Breast cancer diagnosis via
linear programming.
- Grading Approximately: 35% Homework, 10% Midterm, 35% Final,
20% Project
- Example 3-15: an
example of cycling in the simplex method
- Example 3-16:
overcoming cycling with smallest subscript
- Example 3-18:
Scheme I This is an addition to the book and should be placed
between pages 68 and 69 of the class text. The data can be loaded
as ex3-18.
- Example 3-18:
Scheme I This is a diary file containing all the details of the
steps outlined in the postscript version above.
- Example 3-18:
Scheme I (abbreviated version)
- Example 3-18:
Scheme II
- Example 6-4:
Using Phase I and II with rsmbdd
- Solution of Hwk
13, Question 1
- Solution of Hwk
13, Question 2
- Trial
Question Solution: Page 1, Question 1
- Trial
Question Solution: Page 1, Question 2
- Trial
Question Solution: Page 1, Question 3
- Trial
Question Solution: Page 3, Question 1
- Trial
Question Solution: Page 3, Question 2
-
Example 4-1: Dual tableau
-
simpbdd.m: MATLAB code for hwk 10 (question 2) for solving
linear programs in canonical form with lower and upper bounds.
-
Example 6-1: an example of the revised simplex method
-
smooth.m A MATLAB file for solving LCP's using smoothing.
Also needs
pfun.m to evaluate the smooth function accurately.
Handouts from DoIT:
- 525 (Ferris) handout 1. Class text, Linear Programming via
MATLAB. A postscript version of Chapter 2 can be
downloaded for immediate use.
- 525 (Ferris) handout 2. The MATLAB PRIMER (Third Edition). The
second edition of the PRIMER can be downloaded in postscript
form.
Programming Assignments and Homeworks
Computing Information
- Unix Orientation Sessions
Unix Orientation sessions will be held as follows:
Tuesday September 2 4:30pm, 6:00pm
Thursday September 4 4:30pm, 6:00pm
Monday September 8 4:40pm
Tuesday September 9 4:40pm
Wednesday September 10 4:40pm
Thursday September 11 4:40pm
Room 1221 CS
The orientation session includes a 20 minute video tape and
30-45 minute hands-on session in the user rooms. New Unix users
are strongly encouraged to attend.
- Account Initialization
Registered students who had a CSL Unix account last semester
have the same account this semester. They should be able to
login using the same login name and password as last semester.
Registered students who did not have an account last semester
should initialize their account by logging in to a Unix
workstation as user "newuser". There are signs in the user
rooms explaining how to use newuser, and running newuser is
including in the Unix Orientation hands-on session.
NOTE: We add accounts for students every afternoon based on
registration information from the registrar's
database. Newly created accounts are active as of the next
morning.
There may be an additional delay between the time the
student registers via touch-tone and when the data is
avaliable to us.
- Introduction to
UNIX at UW
Mathematical Programming at UW
This page was updated September 2, 1997.