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

Office Hours: Tuesdays/Fridays 2:00- 3:00 p.m. @ECOT 831, or by appointment.

The primary goals of CSCI 5654 will be

- Understand the basic theory behind LP, algorithms to solve LPs, and basics of (mixed) integer programs.
- 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.

- Linear Programs: Simplex algorithm and its analysis, duality, complementary slackness; Geometry of linear programs; Network flow algorithms.
- Integer Linear Programs: Branch & Bound, Gomory cuts, approximation/randomization through LP.
- Applications: Optimal allocation of resources, control design, verification, regression, relaxations of hard combinatorial problems to LP.
- Beyond LP: Convexity,
Quadratic Programming, Semi-Definite Programming.

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.

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.

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

- Homework Assignment 10 is due on Dec 2nd
- Homework Assignment 9 is due 11/20 and late on 11/30.
- Homework Assignment 8 is due next friday (11/13) and late on the subsequent wednesday.
- Assignment 7 is due Nov 4th (wednesday)..
- Assignment 6 is due on the 28th of october.
- Homework Assignment #5 here is due on monday 12th October (one week late: 19th Oct).
- Homework Assignment #4 here is due on monday 5th October (one week late: 12th Oct).
- Homework Assignment #3 here is due on monday 28th Sept. (one week late: 5th oct).
- Homework Assignment #2 ( here ) will be due on 09/16/09.
- Homework Assignment #1 ( here ) will be due on 09/09/09.

- Daniel A. Spielman and Shang-hua Teng, Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually takes Polynomial Time, ACM Symp. on Theory of Computation, 2001.
- Glenn Fung, The Disputed Federalist Papers: SVM feature selection via concave minimization., 2003.