#### Linear Optimization Math 432/832 Fall 2008 Class Log

 1. Aug 25, Mon. course overview and logistics; Sec 1.1: forms of linear programs; Sec 1.2,4: example of diet problem; graphical solution 2. Aug 27, Wed. different outcomes of optimization problem; Sec 1.3: convex functions; piecewise linear convex functions; solving with LP; absolute value; data fitting 3. Aug 29, Fri. Sec 2.1: convex set; convex combination; convex hull; polyhedra and polytopes Sept 1, Mon. Labor Day, no class. 4. Sept 3, Wed. Sec 2.2: definition of vertex, extreme point, basic feasible solution; properties of lin independent constraints; equivalence of definitions 5. Sept 5, Fri. continued equivalence of definitions; bound on the number of extreme points 6. Sept 8, Mon. Sec 2.5: existence of extreme points; equivalence with not containing an infinite line 7. Sept 10, Wed. feasible sets of LPs in standard form always have an extreme point; Sec 2.6: existence of optimal extreme points; Sec 2.3: basic solutions of polyhedra in standard form; basic columns 8. Sept 12, Fri. how to choose a basic solution for a polyhedron in standard form; terminology; example; assumption that A has m linearly independent rows; Sec 2.4: degeneracy; example that a degenerate solution can correspond to more than one basis, or just one basis 9. Sept 15, Mon. Sec 3.1: feasible directions; moving in the jth basic direction; maintaining feasibility; rate of change of cost; reduced cost; example 10. Sept 17, Wed. the vector of reduced costs; conditions for optimality; Sec 3.2: computing ϑ* 11. Sept 19, Fri. example of computing ϑ*; Thm 3.2: new feasible solution is a BFS; an iteration of the simplex method 12. Sept 22, Mon. example solved completely by simplex method; when all BFSs are nondegenerate, the simplex method terminates in a finite number of steps; Sec 3.3: implementation issues: how to avoid too much recomputation 13. Sept 24, Wed. the revised simplex method; how to update the inverse of the basis matrix; the tableau; how to update the tableau 14. Sept 26, Fri. reduced costs and the full tableau; how to update; example; Example 3.6 showing the simplex algorithm cycling 15. Sept 29, Mon. Sec 3.4: anticycling pivoting rules: lexicographic; example proof of correctness 16. Oct 1, Wed. Bland's rule for anticycling; example; Sec 3.5: finding an initial BFS; two-phase simplex algorithm; driving artificial variables out of the basis; example 17. Oct 3, Fri. Sec 3.7: number of pivots of the simplex algorithm; Klee-Minty example with an exponential number of pivots; polynomial time algorithms of Khachiyan and Karmarkar; Sec 4.1: motivation of the dual LP; example; derivation via Lagrange multipliers 18. Oct 6, Mon. Sec 4.2: forming dual; dual of the dual is equivalent to the primal; duals of equivalent LPs are equivalent 19. Oct 8, Wed. Sec 4.3: weak duality; consequences; strong duality; consequences 20. Oct 10, Fri. Test #1 21. Oct 13, Mon. two-player games; formulation as an LP; consequence of duality 22. Oct 15, Wed. further discussion of two-player games; complementary slackness; examples 23. Oct 17, Fri. returned Test 1; Sec 4.5: dual simplex algorithm; finding pivot row and col; pivot maintains dual feasibility and improves cost; started example Oct 20, Mon. Fall break, no class. 24. Oct 22, Wed. example of dual simplex algorithm; termination conditions; lexicographic anticycling rule; recovering the dual optimal solution from the optimal primal tableau; informal feedback survey 25. Oct 24, Fri. discussion of informal feedback survey; Sec 4.4: economic interpretation of the dual; shadow prices; example of diet problem; Sec 4.6: short certificates proving the answer; Farkas' lemma for proving infeasibility; example 26. Oct 27, Mon. review of Farkas' lemma example; geometric interpretation of the Farkas' lemma; Sec 5.1: sensitivity analysis; adding a new variable 27. Oct 29, Wed. example; adding a new inequality constraint; example 28. Oct 31, Fri. adding a new equality constraint; big M method; example 29. Nov 3, Mon. corrected example of big M method; changing b; example; changing the cost vector c; if j is nonbasic 30. Nov 5, Wed. changing the cost vector c_j when j is basic; changing the constraint matrix; when A_j is nonbasic and basic 31. Nov 7, Fri. Sec 5.2: global dependence on b; Sec 5.4: global dependence on c; Chp 6: short overview 32. Nov 10, Mon. Sec 7.2: networks; network flow LP; matrix formulation; Sec 7.3: starting network simplex algorithm; a basis has no cycles 33. Nov 12, Wed. properties of trees; tree solutions are basic solutions and conversely; how to determine the value of the basic solution from the tree 34. Nov 14, Fri. changing the basis; change in cost; computing reduced costs using the dual 35. Nov 17, Mon. network simplex algorithm for capacitated networks; integrality of optimal solution and cost 36. Nov 19, Wed. Sec 7.5: maximum flow problem; analysis of network simplex algorithm; Ford-Fulkerson algorithm; max flow-min cut thm; Sec 7.9: statement of shortest path problem; formulation as network flow problem 37. Nov 21, Fri. Test #2 38. Nov 24, Mon. Sec 7.9: solution of shortest path problem; interpretation of the dual; started primal-dual algorithm Nov 26-28, Wed-Fri. Thanksgiving break, no class. 39. Dec 1, Mon. developed primal-dual algorithm; example 40. Dec 3, Wed. finished example; implementing the primal-dual algorithm; finiteness; started primal-dual for max flow 41. Dec 5, Fri. applied primal-dual to the max flow problem; Sec 7.5: the Ford-Fulkerson algorithm; Chp 10: integer programming 42. Dec 8, Mon. integer programming is NP-complete; modeling satisfiability; linear programming relaxation; Sec 11.2: branch-and-bound method for solving IPs; example 43. Dec 10, Wed. Sec 11.2: Gomory cuts; evaluations 44. Dec 12, Fri. applications of integer programming: maximum independent set; problem-specific cuts; traveling salesman problem; quadratic number of subtour elimination constraints Dec 15, Mon, 7:30am-9:30am Final Exam