346:002, Fall 2019

An Introduction to Optimization Theory

General Course Information

Meeting time: Monday and Wednesday 11:30 am - 12:45 pm in W303 W201

Instructor: Hao Huang

Textbook: P. Thie and G. Keough, An Introduction to Linear Programming and Game Theory, 3/e

Syllabus: Please click here for the syllabus of this course, which includes more details on the course goal, grading scheme, exam and homework policy.

My Contact Information

E-mail: hao.huang AT emory.edu
Office: MSC E432
Office hour: Monday/Wednesday 10:30am-11:30am or by appointment.

Communicating with me: If you have a general question about this class, you are welcome to send me an email. For mathematical questions, the best way is to come to my office hour, or talk to me after class. If you cannot make it to these, you can send me an email to make an appointment with me. Please include the course number in the subject line of your emails.

Homework Assigments

The homework assignements will be posted below, together with their due dates.

HW1: 2.2.8, 2.2.12, 2.3.7, 2.3.16, 2.3.23        (due date: Sep 11, 2019).     Solution to HW1

HW2: 2.4.4, 2.4.6, 2.5.3, 2.6.9, 3.1.3 (e) and (f), 3.9.6 (due date: Sep 18, 2019).         Solution to HW2

HW3: (I) 3.2.2, (II) 3.2.6, (III) solve the LP in Exercise 3.3.2 on Page 76 using the general representation theorem (a.k.a. fundamental theorem of LP), (IV) prove
that the intersection of a finite number of convex sets is still convex.     (due date: Sep 25, 2019) Solution to HW3

HW4: 3.3.3, 3.4.5, 3.5.2(b), 3.5.6(b)        (due date: Oct 2, 2019) Solution to HW4

HW5: 3.6.1(b), 3.6.1(a) (use big-M method), 3.6.2(c) (use two-phase method), 3.7.2        (due date: Oct 9, 2019) Solution to HW5

HW6: 4.2.1(e), 4.2.3, 4.4.1, 4.4.2, 4.5.2   (due date: Oct 23, 2019) Solution to HW6

HW7: 4.4.5, 4.5.3(d), 4.5.3(h), and show that the flow shown below in this file is indeed a max flow.      (due date: Oct 30, 2019) Solution to HW7

HW8: 5.1.2, 5.1.3, 5.2.2, 5.3.6.    (due date: Nov 6, 2019) Solution to HW8

HW9: 5.5.3, 5.6.1, 6.2.5, 6.2.16, 6.4.1(a) (due date: Nov 20, 2019) Solution to HW9

HW10: 7.1.1 (b), 7.2.1(a), 7.3.23(b), 7.3.35 (due date: Dec 4, 2019) Solution to HW10

Tentative Outline

Chapter 1: Mathematical Models (2-3 classes)
Chapter 2: The Linear Programming Model (1-2 classes)
Chapter 3: The Simplex Method (7 classes)
Chapter 4: Duality (4-5 classes)
Chapter 5: Sensitivity Analysis (2-3 classes)
Chapter 6: Integer Programming (2 classes)
Chapter 7: The Transportation Problem (2-3 classes)
Chapter 9: Two-Person, Zero-Sum Games (2-3 classes)

Course Schedule

The materials covered in the classes will be updated and posted below after each class.

Aug 28 (W)     Course introduction, how to formulate a problem in mathematical languages, diet problem, introduction and assumptions of general linear programming (Ch 1.1, 1.2, 2.1)

Sep 2 (M)        ---- Labor day, no class

Sep 4 (W)         Blending model, the graphical method to solve 2-variable LP, Portfolio problem (Ch 2.2).

Sep 9 (M)     Production Model, transportation model, convert a LP into standard form. (Ch 2.3, 2.4, 3.1)

Sep 11 (W)        Canonical form of LE/LP, basic feasible solutions (BFS) of LP, definition of convex sets (Ch 3.1, 3.2, 3.9)

Sep 16 (M)       Definition of extreme points, a proof that Extreme points of feasible region of LP in standard form = BFS. Definition of directions

Sep 18 (W)       Definition of unit and extreme directions. Solve a LP using the Generation Representation Theorem.

Sep 23 (M)       An introduction to the simplex method; solve the LP assuming an initial BFS exists. (Ch 3.3 + 3.4)

Sep 25 (W)       Simplex tableau, more examples of solving LP using the simplex method, anti-cycling pivot rules. (Ch 3.5 + 3.6)

Sep 30 (M)      Finding initial BFS: introduction of artificial variables. The two-phase method. Redundant systems, Big-M Method. (Ch 3.6 + 3.7+ beyond the book)

Oct 2 (W)     Discussions on how large M needs to be, the Single Artificial Variable Method, the motivation to study duality. (Ch 4.1+ beyond the book)

Oct 7 (M)     How to obtain the dual of a LP. Weak duality of linear programming and its implications. (Ch 4.2-4.4)

Oct 9 (W)        ---- Midterm 1

Oct 14 (M)    ---- Fall break, no class!

Oct 16 (W)    Proof of the strong duality using Farkas Lemma.

Oct 21 (M)   Complementary Slackness and its applications. Proof of (special case of) strong duality via Simplex Method. (Ch 4.4, 4.5)

Oct 23 (W)    The Max-Flow Min-Cut Theorem, the Ford-Fulkerson algorithm.

Oct 28 (M)         Understanding the Max-Flow Min-Cut theorem from the duality perspective. Application: Konig's Theorem.

Oct 30 (W)    An introduction to the sensitivity analysis: the case of two variables or two constraints. Simplex method in the matrix form. (Ch 5.1, 5.2)

Nov 4 (M)    Sensitivitity analysis: (i) changes in the obj. function; (ii) addition of a new variable; (iii) changes in the constant-term vector (Ch 5.3-5.5)

Nov 6 (W)    Dual simplex Algorithm. (Ch 5.6)

Nov 11 (M)     Formulation of problems in IP or MIP: (i) job assignment problem; (ii) problem of alternatives; (iii) Sudoku. (Ch 6.1-6.2)

Nov 13 (W)     ---- Midterm 2

Nov 18 (M)     Gomory cutting plane method. Branch-and-bound algorithm, an example of approximation algorithm: the knapsack problem. (Ch 6.3-6.4)

Nov 20 (W)    An introduction to the transportation problem, the use of Hungarian algorithm to solve the job assignment problem.

Nov 25 (M)    An augmenting-path-type algorithm to solve the distribution problem. (Ch 7.1)

Nov 27 (W)    ---- Thanksgiving break, no class!

Dec 2 (M)        A primal-dual method to solve the general transportation problem. (Ch 7.2)

Dec 4 (W)    An introduction to game theory: pay-off matrix, pure/mixed strategy, security level, equilibrium, saddle point. (Ch 9.1-9.3)

Dec 9 (M)             Fundamental theorem of game theory (Ch 9.4-9.5)

Dec 17 (Tu)           The final exam will be on Dec 17, 2019, Tuesday from 3:00pm to 5:30pm in the usual classroom (MSC W201)!