Math 340: Linear Programming

• All assignments, quizzes and exams have been taken offline.

Linear Programming means maximizing or minimizing linear functions of variables subject to linear equations or inequalities (so maybe “Linear Optimization” would be a more descriptive name).

• Classes: Monday, Wednesday and Fridays from 2pm to 3pm in Mathematics Annex 1100.

• Office Hours for final exam (all in LSK 300):

  [2016-12-05 Mon]	11am-12pm
  [2016-12-07 Wed]	4pm-5pm
  [2016-12-09 Fri]	11am-12pm
  [2016-12-13 Tue]	2pm-3pm

We will use Linear Programming by Vašek Chvátal. This text explains the simplex method using the dictionary format that we will use in class.¹

You can get the course notes in a single PDF or each topic in a separate web page:

• What is Linear Programming? [2016-09-07 Wed] (Ch. 1)²
• Standard form for linear programs [2016-09-07 Wed], [2016-09-09 Fri] (Ch. 1)
• Thinking of linear programs geometrically [2016-09-09 Fri]
• Introduction to the simplex method [2016-09-12 Mon] (Ch. 2; examples by Richard Anstee)
• Multiple optimal solutions [2016-09-14 Wed] (Ch. 3; example of an unbounded LP by Richard Anstee)
• Unbounded linear programs [2016-09-14 Wed] (Ch. 3)
• The 2-phase Simplex Method and infeasible linear programs [2016-09-16 Fri] (Ch. 3)
• Degenerate pivots and cycling [2016-09-19 Mon] (Ch.3; slides of Chvátal’s example of cycling)
• Matrix formulas for dictionaries [2016-09-21 Wed] (Ch. 7, first section)³
• Bland’s Rule guarantees termination [2016-09-23 Fri] (Ch. 3, Theorems 3.1 & 3.3)
• Recap of the Simplex Method
• Duality theorems (Ch. 5) [2016-09-26 Mon], [2016-09-28 Wed], [2016-09-30 Fri]
• Complementary Slackness (Ch. 5) [2016-10-03 Mon]
• Coffee stain problem (by Richard Anstee)
• Theorem of the Alternative [2016-10-07 Fri]
• Marginal values (Ch. 5, p. 65) [2016-10-12 Wed]
• The Revised Simplex Method (Ch. 7) [2016-10-14 Fri], [2016-10-17 Mon]
• Sensitivity Analysis (Ch. 10) [2016-10-21 Fri], [2016-10-24 Mon] (see also these examples by Richard Anstee)
• The Dual Simplex Method (Ch. 10) [2016-10-26 Wed] (for examples of dual pivoting see Anstee’s sensitivity analysis examples, or the solutions to practice quiz 5).
• Branch and Bound
• The New Forrest problem (Ch. 11)
• Some combinatorial optimization problems [2016-11-09 Wed]
• The tollbooth staffing problem
• Matrix Games (Ch. 15) [2016-11-18 Fri]–[2016-11-25 Fri]
• All problems are basically the same [2016-11-30 Wed]
• The cutting stock problem

Quizzes will be held in class from 2:25pm to 2:50pm on the indicated dates. I will post links to practice quizzes about a week before each quiz.

There will be an in-class midterm on [2016-10-31 Mon]. Here is a practice midterm. It is important to really try the problems before looking at the solutions! You can get solutions to the practice midterm if you’re sure you’re ready to look at them.

Each of the following topics will take approximately 2 weeks (the chapters listed are from Chvátal’s book):

• Simplex Method (chapters 1–4 & 8)
• Duality Theory (chapters 5,9)
• Revised Simplex Method (chapters 6,7)
• Sensitivity Analysis (chapter 10)

After that we will cover some of the following topics:

• Applications and some modeling techniques (chapters 11-14)
• Branch and Bound
• Game theory (chapter 15)
• Non-linear Programming and the Karush-Kuhn-Tucker conditions
• General Upper Bounding (chapter 25)

On some problems you will be asked to use computer software to solve linear programming problems. I recommend the Classic LINDO application for Microsoft Windows. You can obtain a free evaluation copy from that link to install on your own computer, or use the computer lab in LSK 310. You either should choose a time with no labs or, you can work quietly at the back of the lab even if a lab is scheduled (assuming there are some empty computers). Your ID is the first 8 characters in lower case of your name as recorded first name, middle name (if you have one), final name. The password is set to capital S followed by the first 7 numbers of your student ID. You can change your password. Access the Windows system and click on LINDO.

You don’t need to use LINDO, specially if you have prior programming experience. Other options include:

• Glpk.js and online-optimizer. These are websites, you don’t need to install anything on your own computer! The second also does sensitivity analysis (for the constraints).
• The MixedLinearIntegerProgram class in SageMath. Sage can be used without installing any software at SageMathCell. If you chose the GLPK solver, it can also do sensitivity analysis.
• The scipy.optimize.linprog function from SciPy.

The grade will be computed as 55% final; 15% midterm; 15% quizzes and 15% assignments.

Quizzes

These will be mostly computational problems. There will be 5 quizzes of 25 minutes in length. Practice questions will be given in advance.

Assignments

There will be 5 assignments. They will have an emphasis on theory. Some assignments will give computational questions and you will be able to utilize the computer Lab and the LINDO and LINGO software for Linear programming (available in the computer lab in LSK 310; you will be given accounts) or software of your choosing. Students may work together on assignments but must write up their solutions independently.

Midterm and Final

There will be one 50 minute midterm, it will be during class on Monday, October 31st. The final will be 3 hours long.