Math 407 A&B, Linear Optimization (3 credits), Winter 2017

• Office : Padelford C-438
• E-mail : rrthomas (at) uw (dot) edu (Please use email only for emergencies such as if you are sick and cannot take a test or quiz because of it. Please ask all other questions in class or in office hours.)
• Office hours : Wednesdays 3-4:00 pm (Padelford C-438)

• Office : Padelford C-430
• Email : aengle2 (at) uw (dot) edu
• Office hours : Thursdays 3-4:20 pm (Padelford C-430)

Course Information

• Lecture : Condon Hall 139, MWF 11:30-12:20
  
  
• Course materials :
  • (Highly) Recommended textbook : Linear Programming, by Vasek Chvatal.
  • Professor Jim Burke's Math 407 materials
    
    
• Prerequisites : A solid knowledge of matrices, vectors, inner products, systems of linear equations, row reduction, linear dependence at the level of Math 308 is required. You will be expected to write and understand proofs in this class.
  
  
• Structure of the course and expectations: : The material in this course will be taught through the lectures , reading assignments and homeworks . The lectures introduce the concepts and hence tend to be the most straightforward. You will be expected to read the appropriate reading assignments to solidify your understanding of the concepts and fill in details. The homeworks will be based primarily on the material taught in class but are intended to stretch your thinking and also sometimes to teach new concepts. Hence you should not expect that the homeworks will be entirely like either the lectures or the worked out examples in the book. Since the book is only recommended, attending lectures is critical for doing well in this class. Each week (and sometimes after each lecture) I will post an overview/summary of the material covered in class. You can use these overviews to keep up with the class and to prepare for quizzes and tests. There will be no guarantees that questions on quizzes and tests are entirely from homeworks. You can be tested on any material covered in class. There will be both numerical and theoretical questions on quizzes and tests. You should be able to provide theoretical arguments or proofs similar to those discussed in class.
  
  

• Quizzes, Homeworks and Exams

  • Homeworks:
    
    There will be homework assignments after each lecture to help you prepare for the weekly quizzes. These assignments will not be graded but are crucial for doing well on the quizzes and tests. Students will work in groups and take turns to provide solutions to the class. The homework problems are meant to improve your understanding of the material taught in class. About fifty percent of both exams will consist of problems related to the homework problems. It would be worthwhile to spend time really understanding how to do the homework.
    
    
  • Quizzes (30% of overall grade):
    
    Tentative dates for in-class quizzes: Jan 13, 27, Feb 22 (Wednesday), Mar 8(Wednesday). The weekly quiz will be based on the material and homework from the previous week. Your top 5 quiz scores count toward your grade.
    
    
  • Exams (70% of overall grade):
    
    There will be two exams : a midterm exam and a final exam.
    
    • Midterm Exam (30% of overall grade) : Friday, February 3, in class.
    • Final Exam (40% of overall grade) : 2:30-4:20 p.m. Wed, March 15, 2017, in class.
      
      
• General Comments
  • Guidelines on how to write up solutions to problems on tests and quizzes:
    You must show all your work to get full credit. Explain your steps or methods clearly. Use words to give such explanations if needed. After you have written a solution ask yourself if someone else in the class could follow and understand your solution easily. Always put yourself in the shoes of the grader when you write solutions to problems. It is important that it be apparent to the grader that you did this work on your own and that he/she understands your logic. Make it easy to grade your work. This also requires you to be organized and clear in your writing. Writing that is hard to understand or disorganized will be assumed to be wrong.
    
    
  • Make-ups: : Quizzes and exams can only be made up because of illnesses or other serious reasons. In these situations, I will need written documentation explaining the situation. Please let me know as soon as possible if you cannot take a quiz or exam on the scheduled date.
    
    
  • Partial Credit: There might be questions on an exam or quiz that carry no partial credit. This is usually because of the nature of the question where a partially correct answer may make no sense at all. For instance, a misstated theorem or definition is just a false statement and couldn't be graded with partial credit. It is important to learn to do computations and make arguments correctly from beginning to end.
    
    
  • Keep records : Please hold on to all your graded quizzes and exams until you receive your final grade. You will be asked to produce these if there are any questions or complications regarding records during the quarter.
    
    
  • Tips on getting a good grade:
    • Read the assigned reading materials and attend lectures. It is very important to really understand the concepts (as opposed to memorizing facts). It is not enough to know recipes to solve numerical problems. You will be asked questions that test your understanding of the material. A good way to find out whether you really understand something is to try to explain it to someone. You might be surprised to see how hard it is to accurately explain/reproduce a concept that you think you understand.
      
    • Write clearly and correctly. Be logical in your arguments. Learn definitions and statements of theorems accurately. Remember that I can only evaluate your written work and so it is important to convey your knowledge precisely in your writing.
      
    • Do the homework problems. Even if you understand the material, it is hard to reproduce this on a quiz or test without practice. It's important to learn to work relatively quickly. This can only come with practice.
      
    • Come to office hours if you are having trouble. Let me know early in the quarter if you are having problems with the course for whatever reason.

Weekly Assignments

Overview: Week 1 (Jan 3-6)

• Chapter 1 of Chvatal's book
• Introduction to Linear Programming (Prof. Burke's lecture 2) read until but not including "Sensitivity Analysis"
  
  Terms and definitions to know:
  • linear program, constraints, non-negativity constraints, objective function, cost vector, right hand side vector, coefficient matrix
  • feasible solution, feasible region, optimal solution of an LP
  • feasible LP, bounded LP, unbounded LP, infeasible LP
  • optimal value, unique optimum, infinitely many optima
  Concepts to know
  
  • Modeling problems as linear programs
  • Solving 2D linear programs graphically
  Homework
  • From pages 9-12 of Chvatal's book: Problem 1.1
  • Problem 1.6 (Group 1, Group 3)
  • Problem 1.7 (Group 2, Group 4)
  • Model 1 from Professor Burke's LP models (Group 5, Group 6)
  • Model 2 from Professor Burke's LP models (Group 5, Group 6)
  • Graphical solutions to 2D LPs (do all problems) (Group 7, Group 8)
  • From pages 9-12 of Chvatal's book: Problem 1.4 (Group 7, Group 8)

Overview: Week 2 (Jan 9-13)

• LP Modeling (Prof. Burke's lecture 3)
• LP Standard Form (Prof. Burke's lecture 4)
• The Geometry of Linear Programming (Prof. Burke's lecture 12) read until "vertices".
  
  Terms and definitions to know:
  • linear program, constraints, non-negativity constraints, objective function, cost vector, right hand side vector, coefficient matrix
  • feasible solution, feasible region, optimal solution of an LP
  • feasible LP, bounded LP, unbounded LP, infeasible LP
  • optimal value, unique optimum, infinitely many optima
  Concepts to know
  
  • Modeling problems as linear programs
  • Converting a linear program into standard form
  Homework
  • Try Problem 1.8 from Chapter 1 of Chvatal's book (I will do this in class, but please have a head start and bring the problem to class)
  • Model 3 from Professor Burke's LP models (Group 9, Group 10)
  • Model 5 from Professor Burke's LP models (Group 11, Group 12)
  • Transformation of LPs to standard form (do all problems) (Group 13, Group 14)
  • Model 6 from Professor Burke's LP models (Group 13, Group 14)
  • Model 7 from Professor Burke's LP models (Group 15, Group 16)
  • Model 8 from Professor Burke's LP models (Group 17, Group 18)
  • Model 10 from Professor Burke's LP models (Group 19, Group 20)

Overview: Week 3 (Jan 18-Jan 20)

• No quiz this week
• Comments from Abe Engle on Quiz 1:
  • Problem 1: -1 for drawing the wrong gradient or forgetting to draw it -1 for checking all the vertices and not actually graphically solving it -1 per piece of the wrong region i.e., wrong line or wrong side
  • Problem 2: They're confusing the polyhedron being unbounded from the program being unbounded.
  • Problem 3: This confusion carried over to this problem, if they said something like the objective function never influences the bounded/unboundedness of an LP. I took off a point for a statement like that, but I think it was mostly fine. They basically got lucky that the region in question is a polytope.
  • Problem 4: Also carried over to this problem where they said dropping 3x+2y<=12 makes an unbounded polyhedron and did not discuss the gradient of the objective. -1
  • Problem 5: They did it fine.
  • Problem 6: Lots of people forgot to introduce nonnegative variables. -1 for that.
  • Comment: Quite a few people are saying things like closed and finite when they mean bounded.

• Reading assignments
  • Chapter 2 in Chvatal's book. Understand both examples thoroughly. Do everything with dictionaries, not tableaux.
  
  
• Homework
  • Problem 2.1 a from Chapter 2 of Chvatal (Group 1, Group 2)
  • Problem 2.1 b from Chapter 2 of Chvatal (Group 3, Group 4)
  • Model 11 from Professor Burke's LP models (Group 5, Group 6)
  • Problem 2.1 c from Chapter 2 of Chvatal (Group 7, Group 8)
  • Problem 2.2 from Chapter 2 of Chvatal (Group 9, Group 10)

Overview: Week 4 (Jan 23-27)

• I am posting the geometry lecture from Monday here
• Chapter 3 of Chvatal (pp 39-42 on "Initialization")

• dictionaries, basic feasible solution, basis, non-basis, entering variable, leaving variable, pivot, optimal dictionary, multiple optima,

• The simplex method.
• How to detect infinitely many optima and to write them down.
• The geometry of the simplex method.
• Two phase simplex method - also called "initialization" in the book

• LP geometry homework posted here (Group 11, Group 12)
• Model 12 from Professor Burke's LP models (Group 13, Group 14)
• Problem 3.9 a (Group 15, Group 16)
• Problem 3.9 b (Group 17, Group 18)
• Problem 3.9 c (Group 19, Group 20)

Overview: Week 5 (Jan 30-Feb 3)

• Can the optimal value of the Auxiliary Problem be zero and x_0 be in the basis of the optimal dictionary at the end of Phase I?
• Can the optimal value of the Auxiliary Problem be non-zero and x_0 be a non-basic variable in the optimal dictionary at the end of Phase I?
• If the simplex method stalls at a vertex, does the objective function value stay constant?
• A degenerate dictionary always corresponds to more than n constraints in the original LP meeting the current basic feasible solution. True or false?
• An unbounded LP has infinitely many optimal solutions. True or false?
• If an LP is feasible it has a basic feasible solution. True or false?
• If an LP has an optimal value then this value is always achieved by a basic feasible solution. True or false?
• An optimal feasible dictionary with some zero coefficients for non-basic variables in the z row always indicates that the LP has infinitely many optima.
• An LP can have an optimal value but no optimal solution. True or false?
• An LP can have an unbounded feasible region but a unique optimum. True or false?
• An LP is infeasible if and only if the Auxiliary problem ends with a nonzero optimal value. True or false?
• The way the simplex method is designed guarantees that the objective function value can never decrease from one iteration to the next. True or false?

• Chapter 3 of Chvatal (pp 27-33, 42)

• Fundamental theorem of linear programming

• choosing entering variable
• detecting unboundedness
• degenerate dictionaries
• stalling
• cycling and how to prevent it (Bland's rule)

• Two phase simplex method from Prof. Burke
  These problems contain all sorts of LPs and give you practice with unboundedness, infeasibility and optimality in LPs. No groups are writing solutions. Please do these problems on your own. The answers are given with the problems.
• Problem 3.1 in Chvatal (unbounded LP)
• Problem 3.2 in Chvatal (cycling)
• Additional practice problems for midterm:
  • Simplex Method for LPs with a feasible origin from Prof. Burke

Overview: Week 6 (Feb 6-10)

• Chapter 4 of Chvatal
• Chapter 5 pp 54-62 except for Theorem 5.1 and its proof

• dual of an LP
• weak duality theorem

• pivot rules -- largest coefficient, largest-increase and smallest-subscript
• polynomial time algorithm
• how to write down the dual
• how to show that the dual of the dual is the primal
• how to prove weak duality

• Problem 4.1 b (Group 1, Group 2)
• Problem 4.1 c (Group 3, Group 4)
• If you would like a challenge, try problems 4.2 and 4.3
• Model 13 from Professor Burke's LP models (Group 5)
• Model 14 from Professor Burke's LP models (Group 6)
• Model 15 from Professor Burke's LP models (Group 7)
• Model 16 from Professor Burke's LP models (Group 8)
• Model 17 from Professor Burke's LP models (Group 9)
• Model 18 from Professor Burke's LP models (Group 10)

Overview: Week 7 (Feb 12-17)

• Chapter 5 of Chvatal
• Chapter 7 pp 97-100

• dual of an LP
• weak duality theorem
• strong duality
• complementary slackness

• how to write down the dual
• how to show that the dual of the dual is the primal
• how to prove weak duality
• how to prove and apply strong duality
• how to use complementary slackness to check optimality

• Problem 5.1 (Group 11 (2.1a), Group 12 (2.1b), Group 13 (2.1c))
  You may use the solution to these problems from Chapter 2 from before.
• Problem 5.2 (Group 14, Group 15)
• Problem 5.3 (Group 16)
• Problem 5.4 (Group 17)
• Problem 5.5 (Group 18)
• Additional practice problems on complementary slackness from Prof. Burke. The answers are given at the end.

Overview: Week 8 (Feb 21-25)

• Chapter 7 pp 97-105

• matrix form of dictionaries
• revised simplex method

• Problem 7.1 (Group 19 (2.1a), Group 20 (2.1b), Group 1 (2.1c))

Overview: Week 9 (Feb 27-Mar 3)

• Chapter 7 pp 97-105
• Chapter 5 pp 65-68

• matrix form of dictionaries
• revised simplex method
• economic interpretation of duality, complementary slackness, revised simplex method
• sensitivity analysis - changing cost, adding a column to A

• Problem 5.8
• The following problems refer to the first three problems posted here. I have converted all the final tableaux shown in these problems to the final dictionaries. You can download these final dictionaries here.
  • Silicon chip: do parts 1, 3.
  • Family Farm: parts 1, 2, 5.
  • Concrete Products: parts 1, 2, 5, 7

Overview: Week 10 (Mar 6-10)

• Chapter 10 pp 148-152

• dual feasible dictionary

• writing the dual dictionary from the primal dictionary
• sensitivity analysis

• The following problems refer to the first three problems posted here. I have converted all the final tableaux shown in these problems to the final dictionaries. You can download these final dictionaries here.
  • Silicon chip: finish
  • Family Farm: finish
  • Concrete Products: finish