CSC 445/545 Class Notes: Fall 2014

For a complete set of notes, please attend class or get notes from someone who attended. Only selected notes will be placed here.

1. Lecture 1: Intro. to CSC 445/545.
2. Lecture 2: LP Problems.
3. Lecture 3: Solving LP Problems.
4. Lecture 4: Programming issues.
5. Lecture 5: Numerical issues.
6. Lecture 6: Infinite loops.
7. Lecture 7: Avoiding infinite loops.
8. Lecture 8: Dealing with initial infeasible solutions.
9. Lecture 9: Getting X0 out of the basis.
10. Lecture 10: Examples with an exponential number of pivots.
11. Lecture 11: Klee Minty with maximum increase.
12. Lecture 12: Upper bounding the objective function.
13. Lecture 13: Reading primal/dual solutions using slacks.
14. Lecture 14: Duality theory.
15. Lecture 15: Proof that dual upper bounds primal.
    Typesetting references for your report.
16. Lecture 16: Complementary slackness.
17. Lecture 17: Using complementary slackness.
18. Lecture 18: Small changes to the resources available.
19. Lecture 19: Economic interpretation of dual variables.
20. Lecture 20: Using linear programming for Clar and Fries numbers.
21. Lecture 21: Fitting lines to data sets.
22. Lecture 22: Currents in Benzenoids. Slides available from connex resources.
23. Lecture 23: Integer Programming. Slides available from connex resources.
24. Lecture 24: Gomery Cutting Planes. Slides available from connex resources.
25. Lectures 25 and 26: Network Transshipment Problems
26. Lecture 26: Microwaves: another example with units.
27. Lecture 27: LP applied to an independent set problem, Slides available from connex resources.
28. Lecture 28: The revised Simplex method.
29. Lecture 29: Eta factorizations of the basis matrix.