Math 482 Linear Programming and Combinatorial Optimization Spring 2006 Class Log

1. Jan 18, Wed. course overview and logistics; overview of optimization problems; Sec 2.1: linear programming problems, standard forms
2. Jan 20, Fri. geometric approach to solutions of LP; Sec 2.2: basic feasible solutions
3. Jan 23, Mon. bounds on basic solutions; existence of basic feasible solutions
4. Jan 25, Wed. Sec 2.3: geometry of linear programs; polytopes
5. Jan 27, Fri. correspondence between geometric and algebraic views; existence of optimal basic feasible solutions
6. Jan 30, Mon. finished proof of existence of optimal basic feasible solutions
7. Feb 1, Wed. Sec 2.4: moving from bfs to bfs; pivoting; Sec 2.5: tableaux
8. Feb 3, Fri. Sec 2.6: change in cost when changing basis; choosing a profitable column; the simplex algorithm
9. Feb 6, Mon. example of the simplex method; Sec 2.7: various problems including cycling; Bland's Rule to avoid cycling
10. Feb 8, Wed. Sec 2.8: artificial basis; two-phase simplex algorithm
11. Feb 10, Fri. Sec 3.1: primal and dual problems; Duality Thm; example of dual; when primal and dual have finite optima, are unbounded, or are infeasible.
12. Feb 13, Mon. another perspective on the dual; Sec 3.2: complementary slackness
13. Feb 15, Wed. Sec 3.3: Farkas' Lemma; use as a certificate for infeasibility
Feb 15, Wed. 6pm-8pm Test 1 in 145 Altgeld
14. Feb 17, Fri. matrix games; computing the value of the game as an LP; duality applied to Player I and II's best strategies
15. Feb 20, Mon. Sec 3.4: basic graph theory; node-arc incidence matrix; shortest-path problem
16. Feb 22, Wed. dual of shortest path problem; Sec 3.6: dual simplex algorithm
17. Feb 24, Fri. implementation and example of dual simplex algorithm; Sec 4.1: revised simplex algorithm
18. Feb 27, Mon. implementation of the revised simplex algorithm
19. Mar 1, Wed. example of the revised simplex algorithm
20. Mar 3, Fri. Sec 6.1: maximum flows, LP formulation, dual, max flow-min cut theorem
21. Mar 6, Mon. Sec 4.3: alternate LP formulation of maximum flow problem; solution using the revised simplex method
22. Mar 8, Wed. Sec 5.1-3: primal-dual algorithm
23. Mar 10, Fri. example of primal-dual for an arbitrary LP; finiteness
24. Mar 13, Mon. Sec 5.4: primal-dual for shortest path; Sec 6.4: Dijkstra algorithm
25. Mar 15, Wed. Sec 5.6: primal-dual for maximum flow;
Mar 15, Wed. 6pm-8pm Test 2 in 145 Altgeld
26. Mar 17, Fri. Sec 6.3: Ford-Fulkerson algorithm; finiteness
Mar 20-24. Spring break, no classes.
27. Mar 27, Mon. transformations from max flow: Menger Thm; maximum bipartite matching
28. Mar 29, Wed. Sec 7.1-2: min-cost flows
29. Mar 31, Fri. Sec 8.1-7: complexity classes P and NP; complexity of simplex and ellipsoid algorithms; Sec 13.1: integer programs
30. Apr 3, Mon. Traveling Salesman Problem as an IP
31. Apr 5, Wed. Sec 13.2: total unimodularity
32. Apr 7, Fri. Sec 14.1: cutting planes, Gomory cuts, fractional dual algorithm, example
33. Apr 10, Mon. Sec 14.2: lexicographic order; anticycling rules; use in fractional dual algorithm
34. Apr 12, Wed. Sec 14.3: finiteness of the fractional dual algorithm
35. Apr 14, Fri. Sec 18.1: branch and bound
36. Apr 17, Mon. Sec 18.6: dynamic programming; application to shortest path in layered networks
37. Apr 19, Wed. Sec 17.3: application of dynamic programming to 0-1 knapsack
38. Apr 21, Fri. more applications of dynamic programming; greedy algorithm
Apr 26, Wed. 6pm-8pm Test 3 in 145 Altgeld
Apr 24-28. I will be away attending a conference, no lectures.
39. May 1, Mon. Sec 12.1-2: minimum weight spanning trees; Kruskal, Prim, and Boruvka algorithms; began matroids
40. May 3, Wed. Sec 12.3-4: matric and graphic matroids; connection to the greedy algorithm; evaluations
May 9, Tue. 7pm-10pm Final Exam in 441 Altgeld

    Back This page last modified .