CS 525: Linear Programming Methods

Spring 2011-12 (Also IE, Math, Stat)

General Course Information

Overview

• Introduction
• Linear Algebra: A Constructive Approach
• The Simplex Method
• Duality
• Convexity and polyhedral sets
• Large Scale Computation
• Sensitivity Analysis
• Approximation
• Quadratic Programming and Complementarity Problems

Text

• Linear Programming via MATLAB, Michael C. Ferris, O. L. Mangasarian and Stephen J. Wright, SIAM, 2007. See also this page for a little more information, and the supplementary material, including Matlab codes.
• The following books are on reserve at the Wendt Library and can give additional background information:
  • Introduction to Linear Optimization, D. Bertsimas and J.N. Tsitsiklis, Athena Scientific Press, 1997.
  • Linear Programming, V. Chvatal, Freeman Press, 1980.
  • Linear Programming: Foundations and Extensions, (2nd Ed) R.J. Vanderbei, Kluwer Academic Press, 2001.

Prerequisites

• Math 443 or 320 or 340 or consent of instructor

Handouts from Class

• Getting Started in MATLAB: A description of everything you need to do to get set up to use Matlab in this course.
• The MATLAB PRIMER (Third Edition): An introduction to the basic commands and utilities that you need in Matlab.
• Example 3-3-3; multiple solutions
• Example 3-4-1; Phase I and II Simplex Method
• Example 3-5-1: an example of cycling in the simplex method
• Example 3-5-2: overcoming cycling in the simplex method
• Example 3-6-1: Two Phase Simplex Method This is a diary file containing all the details of the steps for the two phase simplex method as carried out in class.
• Example 3-6-5: Scheme I This is a diary file containing all the details of the steps for Scheme I as carried out in class.
• Example 3-6-5: Scheme II
• Example 6-4-4 .
• Example 7-4-1: Handout I for Lemke's Method
• Example 7-4-2: Handout II for Lemke's Method
• Example 7-5-2: Bimatrix Game (Matching Pennies) soln
• Example 7-5-6: Bimatrix Game (Matching Pennies) via LP
• Example 9-2-1 (with tableaus).
• Example 9-2-4 (with tableaus).

Programming Assignments and Homeworks

• You may discuss the assignments with your classmates. However, you may not share any code, copy solution from another person, or carry out an assignment together. Discussion should only involve verbal communication. All assignments need to be written up entirely separately.
• Handing in homeworks - most homeworks will be handed in either in person (or using the DropBox facility of Learn@UW). Further details will be provided when the assignments are passed out.
• Homework 1 (due Feb 3) , also if needed: hwk1.mat This assignment should be handed in to Ferris during class on Feb 3.
• Homework 2 (due February 10) , also if needed: hwk2.mat
• Homework 3 (due February 17)
• Homework 4 (due February 24)
• Homework 5 (due March 2)
• Homework 6 (due March 16)
• Homework 7 (due March 23)
• Homework 8 (due March 30)
• Homework 9 (due April 13)
• Homework 10 (due April 25) , also if needed: hwk10.mat
• Homework 11 (due May 4)
• Homework 12 (due May 11)
• Solution for hwk12

Grading

Grades for the class will be available at Learn@UW. You will need to log-on, move to the course page, and use the "Grades" tab at the top of the page.

• Approximately: 40% Homework, 15% Midterm, 35% Final, 10% Project
• 1 Assignment per week approximately. Most of the assignments will require the use of MATLAB, which will also be used extensively in the lectures. Homework assignments will be closed at 11am on the day they are due. No homework or project accepted in mailbox of instructor or TA. Submitting someone else's work as your own is academic misconduct. Such cheating and plagiarism will be dealt with in accordance with University procedures (see the Academic Misconduct Guide for Students) .

Examinations

Examinations are closed book, with the exception that 1 handwritten sheet (standard size paper) can be brought in to the examination.
• Midterm Examination: Wednesday, March 7, 2011, 7:15 - 9:15 pm in 1221 CS.
  • Midterm Examination: October 21, 2008.
  • Midterm Examination: October 27, 2004.
  • Solution to 2004 Midterm examination
  • Midterm Examination: October 22, 2002.
  • Solution to 2002 Midterm examination
  • Midterm Part 1 (Spring 1997)
  • Midterm Part 2 (Spring 1997)
  • MATLAB solution to 1997 Midterm examinations
• Final Examination Tuesday, May 15 at 2:45 pm in 1221 CS. Copies of previous final examinations can be downloaded:
  • Final exam from (Spring 1997)
  • Solutions for Q1, Q2, Q3, Q5 on Spring 1997 Final
  • Solutions for Q4 on Spring 1997 Final
  • Final exam from (Fall 1999)
  • Solutions for Q1, Q2, Q3 on Fall 1999 Final
  • Solutions for Q4 on Fall 1999 Final
  • Final exam from (Fall 2002)
  • Solutions for Q1, Q2, Q3 on Fall 2002 Final
  • Final exam from (Fall 2004)
  • Solutions for Q1, Q2, Q3 on Fall 2004 Final
  • Final exam from (Fall 2006)
  • Solutions for Q1, Q2, Q4 on Fall 2006 Final
  • Final exam from (Fall 2007)
  • Solutions for Fall 2007 Final
  • Final exam from (Spring 2010)
  • Solutions for Spring 2010 Final

A computing project in MATLAB.

Breast Cancer Diagnosis.
• Project in pdf format (Due (in instructors hands!) at 2:45pm on Tuesday, May 15).
• getdata.m
• wdbc.data
• wdbc.names

Miscellaneous

• Archive of Class Mailing List. You will need to enter your cs account login and password to access this archive.
• Computer Systems Laboratory FAQ
• Unix Orientation Sessions
• Instructional Facilities
• Account Activation
• Instructional Account Policies
• Forwarding Email
• Introduction to UNIX at UW
• Introduction to MATLAB
• Optimization at the University of Wisconsin
• Courses related to 525