Course Description:

Solution of linear programming problems by simplex method, duality theory, transportation problems, assignment problems, network analysis, dynamic programming

Instructor:

Aaron Nung Kwan Yip

Department of Mathematics

Purdue University

Contact Information:

Office: MATH 432

Email and Phone: click here

Lecture Times and Places:

Section 001 (CRN 26170): T, Th 9:00am - 10:15am, SMTH 208

Office Hours:

T, W: 4:30pm - 6pm, MATH 432, or by appointment.

Occasionally, due to unexpected events, there is a need for online meetings and lectures. These will be conducted in Zoom.
You can also find this link in Brightspace MA421 course homepage (upper left corner, second tab): Content/Course Materials.
This link will also be used in case you need to see me online.

Textbook:

Main Text (required):
[V] Linear Programming, Foundations and Extensions, 5th edition, Robert J. Vanderbei, Springer.
Accessible online from Purdue Library page, using Career account.
You are highly encouraged to make good use of the textbook by reading it.

References (recommended reading):
[MG] Understanding and Using Linear Programming, Jiri Matousek and Bernd Gartner, Springer.
Accessible online from Purdue Library page, using Career account.

[C] Linear Programming, Vasek Chvatal.

Homework:

Homeworks will be assigned weekly, due usually on Thursday in class. They will be gradually posted as the course progresses. Please refer to the course announcement below.

Steps must be shown to explain your answers. No credit will be given for just writing down the answers, even if it is correct.

As a rule of thumb, you should only use those methods that have been covered in class. If you use some other methods for the sake of convenience, at our discretion, we might not give you any credit. You have the right to contest. In that event, you might be asked to explain your answer using only what has been covered in class up to the point of time of the homeworks or exams.

Please staple all loose sheets of your homework to prevent 5% penalty.

Please resolve any error in the grading within one week after the return of each graded assignment.

No late homework will be accepted (in principle).

You are encouraged to discuss the homework problems with your classmates but all your handed-in homeworks must be your own work.

Examinations:

Tests: Midterm (in class, date TBA, soon after October Break)

Final Exam: During Final Exam Week

No books, notes or electronic devices are allowed (nor needed) in any of the tests and exam.

Grading Policy:

Homeworks (50%)

Midterm (20%)

Final Exam (30%)

The following is departmental policy for the grade cut-offs:
97% of the total points in this course are guaranteed an A+,
93% an A,
90% an A-,
87% a B+,
83% a B
80% a B-,
77% a C+,
73% a C,
70% a C-,
67% a D+,
63% a D, and
60% a D-.
For each of these grades, it's possible that at the end of the semester a lower percentage will be enough to achieve that grade.

You are expected to observe academic honesty to the highest standard. Any form of cheating will automatically lead to an F grade, plus any other disciplinary action, deemed appropriate.

Nondiscrimination Statement:

This class, as part of Purdue University's educational endeavor, is committed to maintaining a community which recognizes and values the inherent worth and dignity of every person; fosters tolerance, sensitivity, understanding, and mutual respect among its members; and encourages each individual to strive to reach his or her own potential.

Student Rights:

Any student who has substantial reason to believe that another person is threatening the safety of others by not complying with Protect Purdue protocols is encouraged to report the behavior to and discuss the next steps with their instructor. Students also have the option of reporting the behavior to the Office of the Student Rights and Responsibilities. See also Purdue University Bill of Student Rights and the Violent Behavior Policy under University Resources in Brightspace.

Accommodations for Students with Disabilities and Academic Adjustment:

Purdue University strives to make learning experiences accessible to all participants. If you anticipate or experience physical or academic barriers based on disability, you are also encouraged to contact the Disability Resource Center (DRC) at: drc@purdue.edu or by phone at 765-494-1247.

If you have been certified by the DRC as eligible for accommodations, you should contact me to discuss your accommodations as soon as possible. See also Courses: ADA Information for further information from the Department of Mathematics.

Campus Emergency:

In the event of a major campus emergency or circumstances beyond the instructor's control, course requirements, deadlines and grading percentages are subject to change. Check your email and this course web page for such information.

See also Emergency Preparedness and Planning for campus wide updates.

More information on University Policies:

See your MA421 course homepage in Brightspace.
Content (tab at upper left corner): Student Support and Resources, and University Policies and Statements.

Course Outline (tentative):

I will at least cover sections from the following chapters of [V]: Chapter 1, 2, 3, 5, 7, 11, 12, 14, 15
which touch upon simplex methods, duality, sensitivity and parametric analysis, network flows and various applications.
Additional chapters will be covered based on time and interests.

Course Progress and Announcement:

You should consult this section regularly, for homework assignments, additional materials and announcements.
You can also access this page through BrightSpace.

---

Some tips and comments.

NOTATION MATTERS!!!!!!!!!!!!!!!
A clear understanding of notations is one of the keys to fullly appreciate mathematics.

READ THE TEXTBOOK!
Get used to how mathematics are formulated and presented.

My MOTTO on the use of technology (which I use often):
IF TECHNOLOGY HELPS YOU UNDERSTRAND, BY ALL MEANS USE IT. OTHERWISE, USE IT AT YOUR OWN RISK!
For the homework, I believe all the problems should be and can be done by hand. In order to get full credit, sufficient steps must be shown. You are welcome to use technology to check your answers.

BEWARE THAT DURING THE TESTS AND EXAM, NO TECHNOLOGY WILL BE ALLOWED.

---

Week 1 (Aug 20, 22):
[V, Chapter 1, 2]; [MG, Chapter 1, 2, 4, 5]; [C, Chapter 1, 2, 3].
Examples of linear programming;
Simplex method.

Examples of diet problems: [MG], [C].

Homework 1: due Thursday, Aug 29th, in class.
[V] (make sure you have the 5th Edition.)
Chapter 1, Exercises, p.8: #1.2;
Chapter 2, Exercises, p.21: #2.1, 2.2, 2.5, 2.10;
(Use simplex method to solve 2.1, 2.2, 2.5, following the procedure in p.11-14. For 2.2 and 2.5, you also need to draw in R^2 the feasible set and also the sequence of vertices you go through during the simplex method. For your graphs, use one page for each problem. See p.21 for an example of such a graph. For 2.10, you can use whatever method. If you can "visualize" the geometry of the problem, even in R^4, then the solution is extremely simple.)
Chapter 4, Exercises, p.57: #4.9
(Read [V, p.45] for a motivation of this problem. One method of solution seems to be by mathematical induction, though I haven't tried it myself.)

---

Week 2 (Aug 27, 29):
[V, Chapter 1, 2]; [MG, Chapter 1, 2, 4, 5]; [C, Chapter 1, 2, 3].
Examples of simplex method.
Choice of initial point, Phase I and Phase II.
Some pitfalls of simplex method:

non-uniqueness [C] p.23;

unboundedness;

degeneracy;

cycling; lexicographic method and Bland's rule.

Note: Examples of simplex method

Homework 2: due Thursday, Sept 5th, in class.
[C]
p.9: #1.2 (Use simplex method to solve the actual minimization problem. In addition, can you think of a "simpler" method to solve this problem? Recall [V] Chapter 2, p.21, #2.10.)
p.9: #1.3 (Prove by using simplex method AND also by graphing.)
p.26: #2.2;
p.44: #3.9(a);
[V] (make sure you have the 5th Edition.)
Chapter 3, Exercises, p.40: #3.4;
Chapter 3, For the cycling example in p.29, which step does the sequence violate Bland rule? Then use Bland rule to fix the cycling problem and find the optimal solution for this example.

---

Week 3 (Sept 3, 5):
[MG, Section 5.7] Pivoting rules:
Largest coefficient, largest increase, steepest slope, random, etc

[V, Chapter 4][C, Chapter 4][MG Section 5.9]
Efficiency of simplex method: average vs worst case analysis;
Klee-Minty example;
([MG, Chapter 7] Peek at other methods: ellipsoid and interior point methods.)

[V, Chapter 5][C, Chapter 5][MG, Chapter 6]
Duality, primal (P) and dual (D) problems;
Upper and lower bounds, duality gap, Weak Duality Theorem [V, Thm. 5.1].

Note: Efficiency of Simplex Method

Homework 3: due Thursday, Sept 12th, in class.
[C]:
Use Bland rule to do the cycling example in [C] p.31.
[V]:
Chapter 4: 4.1, 4.2, 4.3. (For each problem, provide graphical illustrations.)
Chapter 5: 5.1, 5.2, 5.3, 5.4.
You can use the pivoting app. provided by the texbook to aid your computations.
For 5.2, 5.3, 5.4, ``illustrate'' means that for any optimal solution of the primal problem, find the optimal solution of the dual problem and verify that the objective functional values of the primal and dual problems are the same.

---

Week 4 (Sept 10, 12):
[V, Chapter 5][C, Chapter 5][MG, Chapter 6]
Duality, primal (P) and dual (D) problems;
Complementary variables: x_j vs z_j, and w_i vs y_i;
Matrix representation of (P) and (D), preservation of negative transpose of matrices during simplex iterations;
Stong Duality Theorem [V, Thm. 5.2];
Complementary Slackness [V, Thm. 5.3];
Certificate of Optimality.
Given (optimal) X, how to find (optimal) Y?

Note: Duality

Homework 4: due Thursday, Sept 19th, in class.
[V] (Re-)do Exercises #2.10, #3.4, #3.5 by considering their dual problems;
[V] #5.6.
[C] Chapter 5, p.69, #5.3

---

Week 5 (Sept 17, 19):

Interpretation of duality: Cost vs profit.
Duality in general form.

Note: Duality of Diet Problem
Note: General Duality
See also:
Convex Optimization (Chapter 5), by Boyd and Vandenberghe
The Theory of Linear Economic Models (Chapter 1), by Gale.

Homework 5: due Thursday, Sept 26th, in class.
[V] p.83: #5.12, 5.16

---

Week 6 (Sept 24, 26):

[V] Chapter 5: Simplex in matrix form.
[V] Chapter 6: Sensitivity analysis.

Note: Simplex in Matrix Form
Note: Sensitivity Analysis

Homework 6: due Thursday, Oct 3rd, in class.
[V] Exercises
Chapter 5: 5.14;
Chapter 6: 6.1, 6.6;
Chapter 7: 7.1, 7.2.

---

Week 7 (Oct 1, 3):

Further applications of duality:

sensitivity and duality; [C] p.67

dual simplex method; [V] Chapter 5.6;

dual phase I method; [V] Chapter 5.7;
[V] Chapter 8.3: Revised simplex method.

Note: Sensitivity and Duality
Note: Dual of General LP
Note: Dual Simplex Method

Homework 7: due Tuesday, Oct 15th, in class.
[V] Exercises: 5.7, 5.8, 6.7;
[C] Problems: 9.2, 9.5.
(For 9.5, you do not need to extend Theorems 5.2 and 5.3. Simply determine if the suggested solution is optimal or not.)

---

Week 8 (Oct 8, 10):
(Oct 8: October Break)

[V, Chapter 12]
Data regression: L^2 versus L^1;
L^1 minimization as an LP problem.

---

Week 9 (Oct 15, 17):
Midterm: Thursday, Oct 17th, in class.
No calculator or any electronic devices are allowed (or needed).
Necessary formula will be provided inside the exam.

Note: Selected Homework Solutions

Midterm Statistics: Average = 79.06;
A: >= 85 (8); B >= 70 (4); C >=55 (3); D < 54 (1).
Midterm Solution

Homework 8: due Thursday, Oct 24th, in class.
[V] Exercises: 12.1, 12.2, 12.3, 12.4, 12.7
In addition, do the L^\infinity-error regression for Figure 12.8.
For 12.1, 12.2 and the L^\infinity versions, plot/compare/contrast in the same graph your regression lines.

---

Week 10 (Oct 22, 24):

[V Chapter 12]
L^2, L^1, L^infinity-regression;
Binary classification;
[MG Chapter 2.6] Biggest ball inside a convex polyhedron

[V Chapter 10] Convex analysis
Convex set, convex combination, convex hull
Caratheodory Theorem (Thm 10.3)
Separation Theorem (Thm 10.4)
Farkas Lemma (Lem 10.5)

Note: Regression
Note: Convex Analysis

Homework 9, due: Thursday, Oct 31st, in class.
Some hints for Homework 9

---

Week 11 (Oct 29, 31):

Note: Farkas Lemma
Note: Examples and Applications of Linear Programming
Note: Integer Linear Programming

Homework 10: due Thursday, Nov 7th, in class.
[V] p.414, Exercises: 23.4, 23.5

---

Week 12 (Nov 5, 7):

[V Chapter 14]
Nodes, arcs, networks, incidence matrices, spanning trees.
Basic solutions in terms of spanning trees.
Network primal and dual simplex methods: modification of spanning trees.
Updating of primal, dual and dual slack variables.

Note: Network Flows
Note: Network Simplex Methods

---

Week 13 (Nov 12, 14):

Integrality Theorem [V, Thm 14.2],
Konig (Matching) Theorem [V, Thm 14.3]
Transshipment, transportation and assignment problems.
Inequality constraints for network flow problems [C, p.321]
Upper bounded network flows [V, 15.4]
Shortest path (as a network flow problem),
Bellman equation (label correcting), Dijkstra algorithm (label setting).

Note: Variants of Network Flows and Applications

Homework 11, due: Tuesday, Nov 26th, in class.

---

Week 14 (Nov 19, 21):

Note: Max-Flow-Min-Cut

---

Week 15 (Nov 26, 28):
(Nov 28: Thanksgiving Break)

---

Week 16 (Dec 3, 5):

---

Week 17 Final exam week
Final Exam: Tuesday, Dec 10th, 1:00pm-3:00pm, SMTH 208