
Linear programming is a fundamental tool in both optimization and algorithm design. Our goal in this course is to familiarize ourselves with various aspects of linear optimization, so that we are comfortable with its use in our research. The course intends to cover both the innards of linear programming, such as the simplex algorithm, as well as its use, often as a black box, in designing both exact and approximately optimal algorithms.
The course will proceed in two parts. In the first part, we will look at linear programming itself in some depth, including combinatorial problems for which linear programming offers exact algorithms. In the second part, we will look at approximation algorithms that are based on duality or rounding fractional LP solutions. Topics that I plan to cover include: Part I: linear programming and its geometry; the simplex method, including techniques to handle degeneracy; interiorpoint methods; the ellipsoid method; duality and it's use in designing algorithms; network problems; integrality of optimal solutions. Part II: LPbased approximation algorithms, including set cover, online set cover, unrelated machine scheduling, and survivable network design. 

A good background in linear algebra as well as basic knowledge of computational complexity will be required. 

Classes will be held Wed/Fri 23:30pm in A212.
Classes begin on January Evaluation will be on the basis of assigments (50%), a midterm (25%), and a final exam (25%). 

We will mostly follow the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis for the first part of the course, and Approximation Algorithms by Vijay Vazirani for the second part. Other good reference materials are
For background in linear algebra, a good book is Introduction to Linear Alebra by Gilbert Strang. I recommend taking notes in class, as our treatment will often differ from that in books, and I may cover topics out of order. I will post an outline of topics covered in each lecture below, including source material. 


Two examples of LPs, with two variables and three variables, with graphical solutions. An LP in general form with notation. An LP in standard form, and converting from an LP in general form to an LP in standard form. An example of such a conversion. Matrix notation.
References: Chapter 1 from Bertsimas and Tsitsiklis, particularly Sections 1.1 and 1.4.  
Linear algebra primer: linear independence of vectors, matrix inverses, uniqueness of solutions. Subspaces, basis, dimension, and null space of subspaces. Polyhedra and convexity. Defined vertices, extreme points, and basic feasible solutions, and proved equivalence of these three.
References: Sections 1.5, 2.1, and 2.2 from BT book.  
Generating basic feasible solutions: redefining basic solutions for polyhedra in standard form. Assuming matrix A has rank m can be done without loss of generality. A basic algorithm for generating all basic solutions: for each choice of m columns of the matrix A, check if the columns are linearly independent, and if so, set other variables to zero and solve the resulting linear equalities in m variables. Definition of basis, basic variables, basic columns. Adjacency of basic solutions and indices, and equivalence of the two.
References: Section 2.3 from BT book.  
Extreme points in polyhedra: P does not contain a line iff P has an extreme point. If P is nonempty and has extreme point, then either the optimal value (for minimization) is negative infinity, or is obtained at an extreme point. A basic outline of the Simplex algorithm: find a starting bfs; find an adjacent bfs of lower cost and move there; repeat until all adjacent bfs have equal or higher cost. Degeneracy of basic feasible solutions. Definition of a feasible direction, and change in basic variables to maintain feasibility of equality constraints when a single nonbasic variable is increased.
References: Sections 2.4, 2.5 2.6, and the first few parts of Section 3.1 from BT book.  
An example of degeneracy, shown by considering a polyhedron with n variables and m equality constraints where nm = 2, hence the inequality constraints could be shown in 2dimensional space. Moving to an adjacent basis (as discussed towards the end of the previous class). Definition of reduced costs, and their importance: if all reduced costs are nonnegative, the bfs is optimal (and vice versa, except for degeneracy). Effect of degeneracy in determining whether a direction is feasible or not. A more detailed outline of the Simplex algorithm. Proof that moving in the direction described will either give us another bfs of lower cost, or give us a ray along which all points are feasible and cost reduces indefinitely. Finally, proof that the simplex as described (assuming an initial bfs, and nondegeneracy) terminates in finite time, with either an optimal bfs, or a ray that demonstrates optimal cost is unbounded.
References: Sections 3.1 and 3.2 from BT book.  
No lecture today.  
Bland's pivoting rule, and proof that it avoids cycling at a degenerate basic feasible solution. The twophase method for finding an initial basic feasible solution using artificial variables.
This completes a description of the basic simplex method. References: The analysis of Bland's pivoting rule was taken from lecture notes by David Williamson (but also see Section 3.4 from BT book). The twophase method is described in Section 3.5 from BT book.  
The full tableaux method for simplex, and proof of correctness. Lexicographic pivoting rule and proof of correctness.
References: Sections 3.3 and 3.4 from BT book. We didn't explicitly cover the revised simplex method, but you can see that the proof of correctness for the full tableaux method requires the revised simplex method.  
No lecture today.  
The complexity of simplex (without proofs): examples with exponential number of pivots known for all deterministic pivoting rules. Subexponential bounds for randomized pivoting rules. Bounds on the diameter of polyhedra (linear lower bound, and subexponential upper bound). Smoothed complexity.
Duality: Dual variables as multipliers for constraints, to obtain lower bounds on the optimal cost (assuming primal in standard form). Alternative perspective: price of relaxing constraints. Guidelines for obtaining dual from primal. Taking the dual of the dual gives us the primal. Weak duality. Strong duality. Complementary slackess, and visualizing optimal primal and dual solutions using complementary slackness. References: Section 3.7 for the complexity of simplex method. Sections 4.1, 4.2 and 4.3 for duality.  
Farkas Lemma. Proof of strong duality using FL. Proof of FL (note that here the proof we covered in class is incomplete. We need to show that set P is closed and bounded for there to be a minima). Review of polyhedral geometry to show equivalence of representations of polyhedra.
References: Sections 4.6, 4.7, and the beginning of Section 4.8.  
Statement of Projection Theorem, that projecting a polyhedron onto a lower dimension yields a polyhedron. Completion of proof to show that the set P is closed and bounded, from last lecture. Definition of recession cones, extreme rays for polyhedra. For a polyhedral cone, cost is unbounded iff there is an extreme ray with negative projection on the cost vector. Using this, a proof of one direction of the the resolution theorem, unifying multiple representations of polyhedra.
You should read the proof of the projection theorem, or derive it yourself. We did not cover the proof of the converse of the resolution theorem, or the proof of the statement about polyhedral cones above. References: Section 2.8 for the projection theorem. Sections 4.8 and 4.9 for the remaining topics.  
Ellipsoid method: affine transformations, ellipsoids, and how to do a single iteration.
References: Section 8.2 from BT.  
Ellipsoid method: How to find a starting ellipsoid. Using perturbation to remove fulldimensionality assumption. Lower bound on volume for a fulldimensional polyhedron. The complete ellipsoid method for feasibility (assuming infinite precision arithmetic, integer values for input parameters, and matrix A has rank n).
References: Section 8.3 from BT.  
No class.  
Finding a feasible point, and optimization using the ellipsoid method. We discussed two methods. The first takes time polynomial in the number of constraints. It operates by finding a maximal set of constraints that are feasible when tight, and then using Gaussian elimination to solve these tight constraints. Then optimization can be done by combining the primal and dual into a single linear program. The second method relied on using the approximatelyfeasible point to obtain a rational point that was feasible, and then using binary search to find an optimal solution.
Not only does the ellipsoid method give us a polynomial time algorithm for linear programming, the running time is also independent of the number of constraints. Further, it reduces optimization to separation: given a separation oracle for a (fulldimensional) polyhedron, we can optimize over it. Started talking about interiorpoint methods, focusing on primal pathfollowing methods. Discussed KKT conditions. References: The first method for finding a feasible point and optimization is from Theorem 10.4 in the book by Schrijver, and Section 8.4 from the BT book. The second method is from Lemma 6.2.9 and Theorem 5.3.19 from the GLS book. The discussion of interior point is from Section 9.4 of the BT book.  
Completed discussing the primal pathfollowing interiorpoint algorithm. In an iteration, given a primal and dual point in the interior for some \mu, we use the secondorder Taylorseries expansion for the objective of the convex program P(\mu) around the given starting point to obtain feasible primal and dual variables for a smaller value of \mu. Thus, we follow the centralpath approximately, and stop when \mu is small enough. We also saw how to obtain feasible primal and dual values in the interior.
For obtaining an initial solution, for the scaling step to ensure that each coordinate of each bfs is at most 1, I mistakenly said that we should scale the variables. Actually, the constant vector b needs to be scaled, to ensure this property. References: Section 9.4 in the BT book. We skipped the proof of Theorem 9.7.  
Inegrality of polytopes, and Total Unimodularity. We confined our discussion to polytopes, since these are of mos interest to us. Defined integral polytopes, and use in polytime algorithms for determining solutions to Integral Linear Programs (ILPs). Defined unimodular and totally unimodular matrices, and proved that if A is TUM, b integral, then polytope Ax >= b is integral. Discussed properties of TUM matrices: transposing, negating, and concatenating identity matrices preserves TUM. Characterized TUM matrices in terms of dividing subset of columns into two sets, and used this to give a polytime algorithm for maxweight matching in bipartite graphs.
References: The main reference is Chapter 19 from the Schrijver book, but the material selection is quite selective.  
Characterizations of TU matrices. We proved a few different characterizations of TU matrices, including that used in the previous lecture.
References: The lecture basically covered the proof of Theorem 19.3 from the Schrijver book, but we skipped characterization (vi): if each entry of matrix A is +1, 1, or 0, A is TU iff the sum of entries in any square submatrix with even row and column sums is divisible by four.  
No class.  
TUM can be determined in polynomial time (without proof). TDI and use, example of matching in general graphs (CunninghamMarsh theorem) without proof. Started approximation algorithms, did a 4 log n  approximate algorithm for set cover by randomized rounding.
References: The proof of polynomial determination for TU matrices can be found in Schrijver, Chapter 20. The discussion of TDI was from the lecture notes of Michel Goemans, available here. A good proof of CunninghamMarsh is in Chandra Chekuri's notes here. The part on set cover was from Chapter 14 of Vazirani's book.  
A 2approximation algorithm for scheduling on unrelated parallel machines. We also discussed the integrality gap and it's use as a lower bound.
References: Chapter 17 of Vazirani's book. Integrality gap is discussed in Section 12.3.  
A polylogcompetitive algorithm for online set cover, by multiplicativeweight updates and primaldual analysis.
References: Chapter 4 of the book "The Design of Competitive Online Algorithms via a PrimalDual Approach" by Buchbinder and Naor (this is available online). Note that of the three algorithms in the chapter, we only covered the first, as well as Section 4.4.1 for randomized rounding.  
A 3approximate algorithm for metric facility location, by a dual algorithm.
References: Chapter 24 of Vazirani's book. We did not cover Sections 24.4.1 and 24.4.2, but these are worth reading too.  
A 3approximate algorithm for generalized Steiner network, by iterative rounding.
References: Chapter 23 of Vazirani's book. We did a 3approximate algorithm (for which there is a simpler counting argument), while the book gives a 2approximation. The book also gives an example for which the algorithm is tight. 





