CSCI 5654: Linear Programming

Fall 2009

Instructor: Sriram Sankaranarayanan


[  Syllabus   Handouts/Announcements    Assignments  ]

News

.
12/02/09 Midterm#2 on Dec. 2nd
11/20/09 Assignment 10 is due on Dec 2nd .
11/18/09 Lecture 20 Notes
11/13/09 Homework Assignment 9 is due next friday (11/20) and late on 11/30, the monday after thanksgiving.
11/06/09 Homework Assignment 8 is due next friday (11/13) and late on the subsequent wednesday.
11/4/09 Lecture 16 Notes (handwritten notes).
11/2/09 Lecture 15 Notes.
10/29/09 Assignment 7 is due Nov 4th (wednesday).
10/26/09 Lecture 14 Notes.
10/22/09 Assignment 6 is due on the 28th of october (wednesday).
10/21/09 Lecture 13 Notes.
10/19/09 Post-midterm review (grades given out), rehash of Lecture#12.
10/14/09 First midterm
10/12/09 Preparation for Midterm: come prepared with questions.
10/07/09 Lecture #12: Handwritten notes. Copies available from ECOT 624.
10/05/09 Assignment#5 is here (due 10/12, late 10/19).
10/05/09 Lecture #11 slides .
09/29/09 Lecture #10 slides , matlab codes: browse, download tarball
09/28/09 Lecture #9 slides , matlab codes: solveLeastSquares , expt1 , expt2 .
09/21/09 Lecture #8 slides .
09/18/09 Assignment #3 here is due on the 28th Sept. (one week late: 5th oct).
09/16/09 Lecture #7 slides , Chapter 9 of Venderbei's book available online through Springer.
09/14/09 Lecture #6 slides
09/09/09 Lecture #5 slides and homework assignment #2 (due 09/16/2009, one week late: 09/25/2009).
09/09/09 Lecture #5 Handout #3 .
09/02/2009 Lecture #4 slides and homework assignment #1 (due 09/09/2009, one week late: 09/16/2009).
08/31/2009 Posted lecture#3 slides and Handout#2.
08/26/2009 Posted lecture#2 slides (passwords given out in class).
08/24/2009 Posted lecture#1 slides and Handout#1 (passwords given out in class).

Course Information

Meetings: Mondays/Wednesdays 5:30 - 6:45 p.m. @ ECCR 116.
Office Hours: Tuesdays/Fridays 2:00- 3:00 p.m. @ECOT 831, or by appointment.

Overview

This course presents the theory and applications of Linear Programming (LP), arguably one of the most important optimization problems in  applied mathematics and engineering. The Simplex algorithm to solve linear programs is widely regarded as one among the "top ten" algorithms of the 20th century. The theory of linear programming  is used in almost all fields of engineering including operations research,  machine learning, control system design, scheduling, computer vision  and so on.  It forms the basis for numerous approaches to solving hard combinatorial optimization problems through randomization and approximation.

The primary goals of CSCI 5654 will be
  1. Understand the basic theory behind LP, algorithms to solve LPs, and basics of (mixed) integer programs.
  2. Understand important and emerging applications of LP to economic problems (optimal resource allocation, scheduling problems), machine learning (SVM), control design (finite horizon optimal control, dynamic programming), formal verification (ranking functions), and so on.
At the end of the course, the successful student will be able to cast various problems that may arise in her research as optimization problems, understand the cases where the optimization problem will be linear, choose appropriate solution methods and interpret results appropriately. This is generally a powerful tool in many research areas.

Syllabus

Topics that will be covered include:
Note: The choice of topics may vary depending on available time and student feedback.

Grading

The course will feature weekly homework assignments, and two midterm quizes. The final grade will be determined as follows:

Homework assignments
            60%
Midterm Quizes
            15% (each)
Class Participation (*)
            10%

(*) Class participation includes responding to in-class questions, asking questions in class, making critical comments about the material in class and volunteering
to lead a mini-presentation on a topic of interest (towards the end of the course). It is expected that all the students will earn full credits for class participation.

All exams and quizzes will be held in class. 

The overall grade will be determined by adding up the homework assignment and midterm scores in the ratio shown in the table above.  Your grade will be determined by the total score (normalized to 100):

Total Score range
 Expected Grade Range
 75 - 100
  A- to A+
 60 - 75
  B- to B+
 >= 45
  Pass
 < 45
  Fail



Collaboration Policy: The homework assignments are strictly non-collaborative. However, you are permitted (and even encouraged) to discuss solution strategies with the instructor or other people who are enrolled in the course. Any such help or discussion must be acknowledged clearly at the beginning of your assignment. Such an acknowledgement will not incur any penalties.

The actual assignment itself must be written entirely on your own without outside assistance. Copying directly or indirectly (consulting) from unauthorized
sources (solution manuals, on line web pages, discussion forum and so on) is prohibited. If in doubt, ask the instructor. Looking at another student's assignment
or solution is strictly prohibited.

Soliciting  help on assignments from people or sources other than the instructor and students registered for this course is considered unauthorized assistance and hence a violation of the CU honor code.  Once again, if you have any doubts in this regard, ask the instructor.

Note: The CU Boulder honor code is available online HERE! You are expected to be aware of and to follow the honor code.

Book

Main Text: Linear Programming by Vasek Chvatal, W.H. Freeman publisher, 1983.
                    Topics not covered in Chvatal will be covered by notes and handouts.
                    (todo for instructor: place this in reserve).

Other texts:
                   1. Linear Programming by R.J. Vanderbei (available online through the CU library).
                   2. Combinatorial optimization: Algorithms & Complexity, by Christos Papadimitrou and Ken Steglitz
                   3. Linear Programming: Theory and Applications by G.B. Danzig and M.K. Thapa.
                   4.  Schrijver's and Integer and Combinatoral Optimization: Nemhauser & Wosley are also good references (not recommended as texts).
                   5. Convex Optimization by Boyd & Vandenbreghe is a good reference for the more general area of convex optimization.


Announcements and Handouts

Lecture Topics Covered Slides + Handouts
20 Cutting Plane Methods: (Chvatal-) Gomory cuts. Lecture Notes
19 Integer Linear Programming: NP completeness, examples, branch-and-bound method. Vanderbei's book chapter 23.
17 & 18 Network Simplex: Transshipment problem. Initialization Phase. Analysis of Network Simplex Problems. Chvatal Chapter 18, and Vanderbei's book Chapter 14.
16 Polar cones. Network Simplex: Transshipment problem and Feasible Spanning Tree Solutions. Handwritten notes .
15 Double Description of Polyhedra, Geometric view of degeneracy Lecture Notes .
14 Farkas' Lemma (theorems of the alternative) and Minkowski-Weyl Theorem Lecture Notes.
13 Convex polytopes, polyhedra, vertices, basic feasible solutions and correspondence to Simplex Lecture Notes.
12 Geometry of Simplex-1: basic properties of linear spaces, affine spaces and cones (rehash of lecture 12, because of midterm interruption.)
12 Geometry of Simplex-1: basic properties of linear spaces, affine spaces and cones. handwritten note (to be typeset soon).
11 Classification problems: classification as LP, dual form of linear-separable classification problem, support vectors, pitfalls using a linear objective function, margins. Also discussed optimal margin classifier using SVMs (not in syllabus). slides.
10 Application of norm(penalty) minimization problems: regularization, penalty function approximation, signal smoothing (denoising), linear regression slides , matlab codes: browse, download tarball
9 Application module #1: Norm minimization problems (L1,L2, Linfty), unconstrained least squares, solving linear systems with noise slides , matlab codes: solveLeastSquares , expt1 , expt2 .
8 Duality for general form Simplex. Revision of basic concepts. slides
7 Dual simplex: connections between primal/dual dictionaries, general form simplex slides
6 Duality: revisited strong duality proof, complementary slackness, dual variables as shadow (margin) costs. slides
5 Dual Problem: Introduction, Dual Variables, Relations between dual and primal formulations. slides and handout
4 Pitfalls: Degeneracy, Cycling, Bland's Rule (w/o proof), Klee-Minty Cubes and Complexity. Slides
3 Pitfalls: Unbounded instances, Initialization Phase Simplex and properties Slides and Handout#2
2 Basic Simplex: Dictionaries, Basic Variables, Basic Feasible Solution, Pivoting. Slides
1 Overview: Linear Programming, Topics, Example Applications Slides and Handout #1 .

Assignments

Assignments will be posted here. You are allowed a grace period of upto one week for 5 assignments of your choice.

References

Will post interesting links and papers here.