Each week there will be either a quiz or an assignment (or a midterm), the details of which will be on this page. There will be a total of 5 quizzes and 5 assignments throughout the semester (with more quizzes at the beginning and more assignments towards the end).

- Quiz 1 - Friday Sept 15 (Solution)
- This quiz will cover things through Wednesday Sept 13:
- Linear programs in standard form (suggested problems: Chvátal 1.1, 1.2)
- Feasible/infeasible/unbounded linear programs (suggested problems: Chvátal 1.3, 1.4)
- Solving 2-variable linear programs graphically (suggested problems: try this for any of the 2-variable linear programs in the exercises of Chvátal ch. 2 or Vanderbei ch. 2)
- Rewriting a linear program in standard form with slack variables (suggested problems: try this for any of the linear programs in the exercises of Chvátal ch. 2 or Vanderbei ch. 2)

- Quiz 2 - Friday Sept 22 (Solution)
- This quiz will cover things through Wednesday Sept 20:
- The simplex method (suggested problems with feasible initial dictionaries: Exercises 2.1, 2.2 of Chvátal; also any of 2.1, 2.2, 2.8, 2.9 of Vanderbei you want to do).
- The two-phase simplex method for infeasible initial dictionaries (suggested problems: Exercise 3.9 of Chvátal; also any of 2.3-2.7,2.10 of Vanderbei you want to do).
- (Feel free to use computer tools to help with the simplex method computations - just remember, on the quiz you'll have to do it by hand, and it will be designed to be reasonable to do by hand).

- Assignment 1 - Due Friday Sept 29 (Solution)

- Quiz 3 - Friday Oct 5 (Solution)
- This quiz will cover things through Wednesday Oct 3:
- The definition of the dual to an LP, and its relation to the primal. (suggested problems: Chvátal 5.1-5.2, Vanderbei 5.1-5.4, 5.6)

- Assignment 2 - Due Friday Oct 13 (Solution)

**Midterm**: in class on Friday October 20. (Version 1 Solutions and Version 2 Solutions)- A past exam for practice (and its Solutions). We won't cover the revised simplex method before the exam, so that sort of problem won't be on our midterm.
- Problem 5 as stated also isn't something that could be on our
exam, because it involves duals to LPs with free variables /
equalities. Sorry I didn't notice that when I posted it! For a
problem that could be on our exam you could replace it with "prove
that either there exists a
**x**≥**0**such that*A***x**≤**0**and**c**·**x**>0, or a**y**≥**0**with*A*^{T}**y**≥**c**, but not both." - Topics covered by the midterm are as follows.
- Linear programs (especially in standard form) and what it means to be infeasible, unbounded, or to have an optimal solution. (Chvátal Ch. 1 / Vanderbei Ch. 1)
- The simplex method, following the standard rule: dictionaries, how to pivot for a feasible dictionary, and understanding uniqueness or non-uniqueness of optimal solutions. (Chvátal Ch. 2 / Vanderbei Ch. 2)
- The two-phase simplex method for initially infeasible dictionaries. (Chvátal Ch. 3 / Vanderbei Ch. 2.3)
- Degeneracy, the possibility of cycling, and anti-cycling methods. (Chvátal Ch. 3 / Vanderbei Ch. 3)
- Matrix formalism for linear programs and for dictionaries (Beginnings of Chvátal Ch. 7 / Vanderbei Ch. 6)
- The dual to a standard form LP, weak and strong duality, (Chvátal Ch. 5 / Vanderbei Ch. 5)
- Applications of duality: the theorem of the alternative, complementary slackness, and the economic significance of dual variables. (Chvátal Ch. 5 / Vanderbei Ch. 5)

- Quiz 4 - Friday Oct 27 (Solution)
- This quiz will cover the revised simplex method. (suggested problems: Chvátal 7.1-7.2; Vanderbei 6.1-6.3, minus the parts about dual vectors/solutions)

- Assignment 3 - Due Friday Nov 3 (Solution)

- Quiz 5 - Friday Nov 10 (Solution)
- This quiz will cover problems in general form, and the dual simplex method. (Suggested problems: Chvátal 9.1, 9.2; Vanderbei 5.6 (via the dual simplex method)).

- Assignment 4 - Due Friday Nov 17 (Solution)

- Assignment 5 - Due Friday Nov 24 (Solution)

**Final Exam**: December 5 at noon, Henry Angus building room 098.- The exam covers the entire contents of the course, so roughly Chvátal chapters 1-5, 7, 9, and 10, plus the additional topics discussed at the end (and of course minus the things not covered in class, such as eta factorization in chapter 7).
- Old exams are available on the department website. Unfortunately these don't have solutions; however, if you try them I can check if what you're doing looks right, and tell you whether or not a given problem would be reasonable for this semester's final.
- Some practice problems for the topics of the last week or so from the course, and Solutions. Questions 3 and 4 here are taken from past exams, and are a bit trickier than would be reasonable on ours (past semesters have spent more time on matrix games, I think).

For homework assignments, you may collaborate, but each person must write up their solutions independently in their own words. Two or more people turning in identical homework assignments are in violation of the UBC academic integrity code and will be given a 0. Late homeworks may not be accepted.

At the end of the semester, your **lowest quiz grade** and **lowest
homework grade** will be dropped. This policy is intended to cover situations
where you may miss a quiz or assignment for whatever reason, without you
needing to come to me to ask for a concession. Beyond this, missed quizzes,
assignments, or midterms will be given a 0 by default - the only exceptions to
this are by instructor permission beforehand, or in the case of a medical
emergency notifying me within 48 hours and presenting a doctor's note. In such
cases there will be no make-up quiz or exams; your grade will be determined
from your other work throughout the term.