346:001, Fall 2017

An Introduction to Optimization Theory


General Course Information
Meeting time:  Monday and Wednesday 10:00 am - 11:15 am in 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 11:15a-12:15p 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. If you cannot make to it, 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 6, 2017).       Solution to HW1

HW2: 2.4.4, 2.4.6, 2.5.3, 2.6.9, 3.1.3 (e) and (f)        (due date: Sep 13, 2017).        Solution to HW2

HW3: 3.2.2, 3.2.6, 3.9.6, and solve the LP in Exercise 3.3.2 on Page 76 using the general representation theorem (a.k.a. fundamental theorem of LP)      (due date: Sep 20, 2017) . Solution to HW3  

HW4: 3.3.3, 3.4.5, 3.5.2(b), 3.5.6(b)        (due date: Sep 27, 2017)         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 11, 2017)        Solution to HW5
For 3.6.1(a), you can pick an objective function at your choice.

HW6: 4.2.1(e), 4.2.3, 4.4.1, 4.4.2, 4.5.2   (due date: Oct 25, 2017)         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: Nov 1)        Solution to HW7
     
HW8: 5.1.2, 5.1.3, 5.3.6, 5.5.3   (due date: Nov 8)         Solution to HW8

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

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



Tentative Outline
Chapter 1: Mathematical Models (1-2 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 23 (W)        
Course introduction, how to formulate a problem in mathematical languages, diet problem, introduction and assumptions of general linear programming, history of LP (Ch 1.1, 1.2, 2.1)

Aug 28 (M)       
Blending model, production model, graphical method to solve LP (Ch 2.2 + 2.3).

Aug 30 (W)        
Transportation model, dynamic planning model (investment portofolio), how to convert LP into the standard form. (Ch 2.4, 2.5, 3.1)

Sep 4 (M)   
--- No class due to Labor day.

Sep 6 (W)          
Canonical Form, Basic feasible solution (BFS), pivot operation on linear equations, definitions and examples of a convex set. (Ch 3.2, 3.9)

Sep 11 (M)   --- No class due to Hurricane Irma.


Sep 13 (W)      
   Definition of extreme points (vertices) of a convex set, proof of "BFS=extreme points of feasible region", definition of directions (Ch 3.9 + beyond the textbook)   

Sep 18 (M)         
Definition of extreme direction of a convex set, solving a LP using the General Representation Theorem.

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

Sep 25 (M)         
Simplex tableau, more examples of solving LP using the simplex method, artificial variables (Ch 3.5 + 3.6)

Sep 27 (W)         
Discussion of redundant systems, Big-M Method (Ch 3.7 + beyond the book)

Oct 2 (M)           
Single Artificial Variable method, the motivation to study duality. (Ch 4.1, 4.2)

Oct 4 (W)   ----  Midterm 1 (tentative)

Oct 9 (M)
 ----  No class due to the Fall recess

Oct 11 (W)         
How to obtain the dual of a linear program. Weak duality of linear programming and its implications, example that both the primal and dual are infeasible. Solution to Midterm 1 (Ch 4.2, 4.3, 4.4)

Oct 16 (M)         
 Proof of the strong duality using the Farkas Lemma. Statement of Complementary Slackness.

Oct 18 (W)         
More examples of Complementary Slackness. Proof of (special case of) strong duality via Simplex Method.  (Ch 4.4, 4.5)

Oct 23 (M)
        The Max-Flow Min-Cut Theorem, understanding it from the duality perspective.

Oct 25 (W)         
Ford-Fulkerson Algorithm. Application of  Max-Flow Min-Cut Theorem: Menger's Theorem and Konig's Theorem.

Oct 30 (M)         
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 1 (W)          
Sensitivitity analysis: (i) changes in the obj. function; (ii) addition of a new variable (Ch 5.3-5.4)

Nov 6 (M)          
Sensitivity analysis: (iii) changes in the constant-term vector; Dual simplex Algorithm. (Ch 5.5-5.6)

Nov 8 (W)  ----  Midterm 2 (tentative)

Nov 13 (M)        
Formulation of problems in IP or MIP: (i) job assignment problem; (ii) problem of alternatives; (iii) Sudoku. Gomory cutting plane method. (Ch 6.1-6.3)

Nov 15 (W)        
Branch-and-bound algorithm, an example of approximation algorithm: the knapsack problem. Solutions to Midterm 2.   (Ch 6.3, 6.4) 

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

Nov 22 (W)
--- No class due to the Thanksgiving recess

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

Nov 29 (W)          
A primal-dual method to solve the general transportation problem. (Ch 7.2)

Dec 4 (M)            
An introduction to game theory: pay-off matrix, pure/mixed strategy, security level, fundamental theorem of game theory (Ch 9.1-9.4)

Final exam will be on Tuesday, Dec 12, from 3:00 pm to 5:30 pm in the usual classroom (MSC W201).