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.- 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)

**Final Exam**: December 5 at noon, location TBA.

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.