Linear Optimization

Math 432/832 Fall 2008 Sections 001

(Dec 18) I have finished grading the final exams and calculating the course grades. These have been posted on Blackboard and submitted to the math department office.
I greatly enjoyed teaching this class, and I hope that you enjoyed it, too. Thanks for your hard work this semester. Enjoy the winter break!
Course Materials:
    Course policies and course log recording topics covered in each lecture.
    Textbook: Introduction to Linear Optimization by D. Bertsimas and J. N. Tsitsiklis, Athena Scientific, 1997.

homework #1, due Wed Sept 3
homework #2, due Fri Sept 12 Mon Sept 15
homework #3, due Wed Sept 24
homework #4 (tex), due Fri Oct 3
homework #5 (tex), due Wed Oct 15
homework #6 (tex), due Mon Oct 27 Wed Oct 29
homework #7 (tex), due Wed Nov 12
homework #8, due Mon Nov 24 by 1pm on Tues Nov 25 at my office
homework #9 (tex), due Wed Dec 10

    Stephen Hartke, hartke @ No . Spam . únl . edu (appropriately changed)
    Office: Avery Hall Room 339, Phone: 402-472-7001
    Office Hours: Mon, Wed, Fri 11:40am-12:30pm, or by appointment.
Meeting Times:
    Mon, Wed, and Fri, 8:30am-9:20am, Avery Hall Room 110
    There will be two in-class tests: Fri Oct 10 and Fri Nov 21
Final Exam:
    Mon, Dec 15, 7:30am-9:30am Avery Hall Room 110
Old Announcements:
(Dec 12) The final exam is Mon Dec 15 7:30am-9:30am in Avery Hall Room 110. The final exam is cumulative over the entire semester, but with an emphasis on later material, particularly the material after the second test. The same calculator and notes sheet policies as the tests apply: calculators may be used for scalar arithmetic but not linear algebra operations, and you may bring one 8.5x11 sheet of paper with anything written on it (front and back).
(Dec 12) This is the website with more information about the Traveling Salesman Problem, including the optimal tour through Sweden.
(Dec 10) Here is a handout showing that the Gomory cutting plane algorithm terminates in a finite number of steps. Here is the example done in class.
(Dec 7) Here is a handout for deriving the Ford-Fulkerson algorithm for maximum flow from the primal-dual algorithm.
(Dec 3) Here is the handout for the primal-dual algorithm.
(Oct 8) Here are some programs that you can use to solve linear programs. Simplex Java applet and some applet demos. Free programs that you need to install: GLPK and lp_solve (I recommend using the CPLEX file format.) Octave, Matlab, Maple, and Mathematica also have linear programming functionality. Sage is convenient for matrix operations, but doesn't have linear programming built-in; you can try it at
(Nov 21) Homework #8 can be turned in up to 1pm on Tues Nov 25. Please give it to me at my office (339 Avery) or slip it under my office door if I am not there. You may also turn it in on Mon Nov 24 during class.
(Nov 19) The second test will be during class on Fri Nov 21. The test will focus on the material from chapters 4 (duality) and 5 (sensitivity analysis) and include the uncapacitated network simplex algorithm (as far as the lecture on Fri Nov 14). As on the previous test, you may bring one 8.5x11 sheet of paper with whatever notes you wish written on the front and back. Also, calculators may be used, but only for arithmetic computations, not linear algebra computations.
(Nov 14) Here is the network for the example done in class.
(Nov 5) The example of Farkas' lemma done in class was incorrect since the inequalities in the minimization problem were reversed. The example has been re-worked with the correct inequalities.
(Oct 29) Here is the example in class correctly worked out. As pointed out to me after class, the initial error in calculation was the computation of the last row when adding to the previous optimal tableau. The easiest way to form this row is to add the coefficients of the constraints and then use elementary row operations (essentially pivots) to put the tableau into appropriate form.
(Oct 29) I will not be holding office hours today.
(Oct 26) Due to questions about Farkas' lemma, the due date of homework #6 is postponed to Wednesday October 29.
(Oct 24) Here is the Farkas' lemma example from class that was done in Sage. The example done in class was incorrect; this version has been corrected.
(Oct 23) Thanks to the students who filled out the informal feedback survey! Here is a summary of the responses.
(Oct 13) Here is the handout on two-player games.
(Oct 3) A discussion of the Klee-Minty example where the simplex algorithm does an exponential number of pivots.
(Oct 1) Here is the updated example of anticycling (pdf) using Bland's rule. Here is the example showing Phase I (pdf).
(Sept 29) Here is the example done in class for anticycling (pdf) using the lexicographic pivoting rules.
(Sept 26) On Homework #4, each LP should be solved using the simplex algorithm. In particular, you should solve #2 with the simplex algorithm, even though the question did not explicitly ask you to. A clarified homework sheet is below.
(Sept 24) The first test will be during the regular class time on Fri Oct 10. The test will cover all of the material up through Chapter 3. The test will be closed-book and notes, but you may bring one 8.5"x11" sheet of paper with whatever you want written on it (front and back). You must turn in this notes sheet with your test. You may also use a calculator for arithmetic computations (addition, subtraction, multiplication, and division), but you may not use the calculator for any vector or matrix calculations (such as inverting a matrix).
(Sept 10) The due date of Homework 2 is delayed until Monday Sept 15. We will talk about degeneracy on Friday; one question on the homework asks about degeneracy.
(Sept 1) The University Bookstore has 10 more copies of the textbook on order; they are to arrive sometime this week.
(Aug 29) HW #1 has another typo: In problem 4, there should be no x's in P2: only y's and z's. The version posted below has been corrected.
(Aug 25) HW #1 handed out in class had a typo: General form involves constraints Ax>=b, not Ax>=0. The version posted below has been corrected.

    Back This page last modified .