640:354 Linear Optimization

Resources:

Web sites:

Course web site http://sites.math.rutgers.edu/~asbuch/linopt_f18/

Section 02 Homework and exam scores

Section 03 Homework and exam scores

Text:

Kolman and Beck, Elementary Linear Programming with Applications (2nd ed.)

Notes on Branch and Bound algorithm

Syllabus

You are welcome to look at my class notes if they help you digest the book, but not everything from the book is covered, and you are still expected to read and understand the book. Here are some examples that we worked through in the lecures.

Solutions to selected homework problems:

Homework 1-3, Homework 6, Homework 7, Homework 8-10

Lectures:

Section 02: Tuesday and Friday 12:00 - 1:20 PM in HLL-116 (Busch)

Section 03: Tuesday and Friday 10:20 - 11:40 AM in LSH-A143 (Livingston)

Office hours:

Monday 3-4 PM, Tuesday 2-3 PM, and Friday 2-3 PM in HILL-234 (Busch).

iOffice hours by Xin Fu:

Monday 4-5 PM, Wednesday 4-5 PM, and Friday 5-6 PM in HILL 628 (Busch).

Grading:

Midterm 1, Friday October 5 in class, 22%

Midterm 2, Friday November 9 in class, 22%

Final Exam, December 20-21, 44%

Weekly Homework, 12% total.

Section 02 Final Exam Time: Thursday, December 20, 2018, 8:00 AM - 11:00 AM, in HLL-116

Section 03 Final Exam Time: Friday, December 21, 2018, 8:00 AM - 11:00 AM, in LSH-A143

Midterm 1:

Friday October 5 in class.

Closed-book exam, no calculators, no formula sheet.

Covered sections: 1.1, 1.2, 1.3, 1.4, 1.5, 2.1

Practice problems with solutions.

Review session by Xin Fu on Wednesday October 3 7:00-8:30 PM in Hill 525.

Solutions

Average 69, Median 70, Max 85.

F < 51 ≤ D < 60 ≤ C < 68 ≤ B < 77 ≤ A ≤ 85.

Midterm 2:

Friday November 9 in class.

Closed-book exam, no calculators, no formula sheet.

Covered sections: 1.1, 1.2, 1.3, 1.4, 1.5, 2.1, 2.2, 2.3 (except Big M Method), 3.1, 3.2, 3.3, 3.4

Most emphasis will be on sections covered since Midterm 1.

Study guide:

(1) Read and understand all covered sections.

(2) Learn and understand the statements of Theorems and Definitions.

(3) Know how to do Homework and Midterm 1 problems to perfection.

(4) Understand what things mean and represent, and how to carry out algorithms.

(5) Understand the proofs of theorems that we did in class.

Practice problems: Review the homework problems, plus:

Bland's method: 2.2: 9

Practice proof problem: Let T be a tableau that can be used in the dual simplex algorithm. That is, T has a pivot in each row, and all entries in the objective row are non-negative. Let P be the linear problem encoded in T. Prove that the dual problem of P has at least one feasible solution.

Solutions

Average 47, Median 47, Max 70

F < 35 ≤ D < 42 ≤ C < 51 ≤ B < 60 ≤ A

Final Exam:

Section 02 Final Exam Time: Thursday, December 20, 2018, 8:00 AM - 11:00 AM, in HLL-116

Section 03 Final Exam Time: Friday, December 21, 2018, 8:00 AM - 11:00 AM, in LSH-A143

Closed-book exam, no calculators, no notes, etc.

The following formula sheet will be available.

Covered sections: All sections mentioned on the syllabus. We did not cover the Big M Method and Complementary Slackness.

See the study guide from Midterm 2, but add MT2 and the examples to point (3).

Final exam from 2015 (partial solutions).

Average 72, Median 73, Max 110

Homework Policy:

(1) Late homework is not accepted.

(2) It is fine to discuss the problems with others, but write-ups must be individual. If you have received help for solving a problem, then cite your source(s).

(3) Regard a homework problem as an essay with rigorous mathematical content. Explain what you do without making your explanation longer than necessary. Write neatly. It is your responsibility that whoever reads your work will understand and enjoy it!

(4) STAPLE your work!!!

Assigned homework sets will show up on this course web site.

Assigned homework:

Homework 0:

Bookmark this page and buy a STAPLER!

Homework 1: Due Tuesday 9/18 in class.

0.1: 14

0.5: 1, 5, 16, 18, 19

1.1: 1, 4

1.2: 7, 13, 14, 16

Homework 2: Due Tuesday 9/25 in class.

1.3: List the numbers of all convex figures on page 83.

1.3: 30, 32, 34

1.4: 15, 16

1.5: 1, 6, 8

Homework 3: Due Tuesday 10/2 in class.

Since we did not finish discussing the simplex algorithm in class, here is an example.

2.1: 1, 3, 5, 8, 19, 21, 23

2.2: 1, 3, 5

Homework 4: Due Tuesday 10/16 in class.

Here is the example of the two-phase algorithm from class.

2.1: 18, 20, 22

2.2: 2, 4, 8

2.3: 6, 7, 8, 10, 12, 18, 20, 21, 22

Homework 5: Due Tuesday 10/23 in class.

2.3: Solve these problems using the two-phase algorithm: 1, 2, 3, 4, 5

3.1: 1, 2, 3, 4, 5, 6

Homework 6: Due Tuesday 10/30 in class.

2.3: 9, 13, 14, 23, 24

3.2: 1, 2, 3, 4, 5, 6, 8

Homework 7: Due Tuesday 11/13 in class.

3.3: 3, 4

3.3: For each of the problems 6, 7, 8, 9, do the following: (Example 1, Example 2)

(a) State the dual problem.

(b) Solve both the primal and the dual problem with any method that works.

(c) Check that your optimal solutions are correct by verifying they are feasible and the primal and dual objective functions give the same value.

3.4: 1, 3, 5, 8

Homework 8: Due Wednesday 11/21 in class.

3.3: For each of the problems 10 and 12, do points (a), (b), (c) from Homework 7.

3.4: 2, 4

3.6: 1, 2, 3, 4

Homework 9: Due Friday 12/7 in class.

4.1: 5, 6

4.2: 3, 5, 6, 8, 9, 10

Practice Problems (do not turn in).

4.2: Redo with Branch and Bound method: 3, 5, 6, 8, 9, 10.