Course calendar

Important dates

• First Class: 06/01/2014
• Midterm: 13/02/2014
• Last Class: 08/04/2014
• Final: 22/04/2014

Topics by Week

Week of Jan 07

Topics:	Introduction to Linear Programming
Reading:	VC, Chapter 1
Learning Goals:	1. Write a linear optimization problem in terms of a linear program in standard form. 2. Interpret geometrically a linear program in two decision variables.
Resources:	An interesting video on the geometry of linear programming.
Notes:	Tuesday Thursday

Week of Jan 14

Topics:	The simplex algorithm
Reading:	VC, 13-24, 39-42
Learning Goals:	1. Find an optimal solution for a linear program in standard form by using the simplex algorithm. 2. Implement the two-stage simplex algorithm on an initially infeasible linear program.
Resources:	A couple of examples of the simplex algorithm, one with an infinite number of solutions, from Dr. Richard Anstee's website.
Notes:	Tuesday Thursday

Week of Jan 21

Topics:	Three things to watch out for: Infeasibility (continued), cycling, and unboundedness.
Reading:	VC, 27-43.
Learning Goals:	1. Solve a linear program with an initially infeasible dictionary by using the two-stage simplex algorith. 2. Identify when the simplex algorithm is caught in a cycle and use Bland's rule to escape from the cycle. 3. Illustrate that a linear program is unbounded if there is no candidate for the leaving variable in one step of the simplex algorithm. 4. State the Fundamental Theorem of Linear Programming.
Resources:
Notes:	Tuesday Thursday

Week of Jan 28

Topics:	Duality Theory
Reading:	VC, 54-62.
Learning Goals:	1. Write, and solve, the dual of a linear program. 2. State the weak and strong duality theorems. 3. State the relationship between unbounded/infeasible primal/dual dictionaries. 4. Use the "magic coefficients" from the primal problem to find the optimal solution of the dual problem.
Resources:	A write-up on "magic coefficients" from Dr. Richard Anstee's website.
Notes:	Tuesday Thursday, see also a solution to the problem from class.

Week of Feb 04

Topics:	Duality Theory, part 2: Complementary Slackness
Reading:	VC, 62-65.
Learning Goals:	1. State the complementary slackness theorem. 2. Use the complementary slackness theorem to check that a given solution to a linear program is optimal.
Resources:
Notes:	Tuesday Thursday

Week of Feb 11

Topics:	Review and Midterm
Reading:
Learning Goals:
Resources:
Notes:

Week of Feb 18

Topics:	Reading Week, no classes
Reading:
Learning Goals:
Resources:
Notes:

Week of Feb 25

Topics:	Revised Simplex Algorithm
Reading:	VC, 97-113 (skip "An Economic...")
Learning Goals:	1. Decompose a linear program into matrices $B, N, x_B, x_N, c_B, c_N,$ and $b$. 2. Implement the revised simplex algorithm on a linear program in standard form. 3. Solve the system $c_B^TB^{-1}$ using eta matrices.
Resources:	A complete revised simplex algorithm example from Dr. Ozgur Yilmaz's website. Side-by-side standard and revised simplex algorithm from Dr. Richard Anstee's website. A derivation of the revised simplex algorithm formulas from Dr. Richard Anstee's website. An example of eta matrices from Dr. Anstee's website. Note that he uses slightly different notation. Why should we care about performance? Because nanoseconds add up!
Notes:	Tuesday Thursday

Week of Mar 04

Topics:	Algorithmic Complexity and the Performance of the Simplex Algorithm
Reading:	An introduction to complexity for the comp sci minded. VC, Chapter 4 and pages 113-114.
Learning Goals:	1. Be able to calculate the number of basic steps required in a simple mathematical algorithm. 2. Write the complexity of an algorithm in Big O notation.
Resources:	The complexity of some common algorithms. Pay attention to the chart at the end! The Complexity of Linear Programming.
Notes:	Tuesday Thursday

Week of Mar 11

Topics:	General Linear Programs and Sensitivity Analysis (Part 1)
Reading:	VC, Chapters 8 and 9
Learning Goals:	1. Write a general linear programming problem in standard form and solve using the (revised) simplex algorithm. 2. State the correspondence between the primal and dual variables in a general linear program. 3. Identify how an optional dictionary may change in response to changes in $b$ and $c$
Resources:
Notes:	Tuesday Thursday

Week of Mar 18

Topics:	Dual Simplex Algorithm and Sensitivity Analysis (Part 2)
Reading:
Learning Goals:	1. Find an optimal solution to a given linear program by using the dual simplex algorithm. 2. Given an initially optimal dictionary, find, if needed, an updated optimal dictionary after changes are made to $b$ and $c$
Resources:	An outline of the dual simplex algorithm. The example is in "tableau" form, but the connection to dictionary form should be clear. An example of truck purchasing and sensitivity analysis from Dr. Anstee's website. A second example of sensitivity analysis from Dr. Anstee's website.
Notes:	Tuesday Thursday

Week of Mar 25

Topics:	Game Theory
Reading:	VC, Chapter 15 (skip "further remarks..."
Learning Goals:	1. Describe the main features of a game. 2. Find the mixed strategy Nash equilibrium of a simple game. 3. Prove the minimax theorem using results from duality theory in linear programming. 4. Use the minimax theorem to find a mixed strategy Nash equilibrium.
Resources:	Big Monkey Little Monkey Nash & co. at the bar. We played an insightful fishing game on Thursday, which was intended to simulate the Tragedy of the Commons. The most interesting part of this game is that it does not have an optimal solution, at least not with irrational agents (namely, you)!
Notes:	Tuesday Tuesday

Week of Apr 01

Topics:	Other Optimization: integer linear programming and non-linear optimization
Reading:
Learning Goals:	1. Solve an integer linear program using the branch and bound method.
Resources:
Notes:	Tuesday Thursday

Week of Apr 08

Topics:	Final Exam Review
Reading:
Learning Goals:
Resources:
Notes: