|
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 Mon, May 1, 2006 at 9:21pm. |