Linear Programming and Combinatorial Optimization

Math 482 Spring 2006 Sections X13/X14

Announcements:
(May 11) I have finished grading the final exam. The class did very well; the average was 189/200. I have computed and submitted the final grades. If you want to know your specific scores, please email me. I will be around this week and next week, so if you want to see your final exam, please email me to arrange a time.
I really enjoyed teaching this class. Thanks for all your hard work, and enjoy the summer!
 
Course Materials:
    Course outline and course log recording topics covered in each lecture.
    Textbook: Combinatorial Optimization: Algorithms and Complexity by C. Papadimitriou and K. Steiglitz, Dover Publications, 1998.

Handouts:
homework #1 solutions, due Wed Jan 25
homework #2 solutions, due Wed Feb 1
homework #3 solutions, due Wed Feb 8
practice #4 solutions, not to be submitted
test #1 solutions
homework #5 solutions, due Wed Feb 22
homework #6 solutions, due Wed Mar 1
homework #7 solutions, due Wed Mar 8
practice #8 solutions, not to be submitted
test #2 solutions
homework #9 solutions, due Wed Mar 29
homework #10 solutions, due Wed Apr 5
homework #11 solutions, due Wed Apr 12
homework #12 solutions, due Wed Apr 19
test #3 solutions
homework #13 solutions, due Wed May 3

 
Instructor:
    Stephen Hartke, hartke @ math . No . Spam . uíuc . edu (appropriately changed)
    Office: Illini Hall Room 227A, Phone: 217-265-6760
    Office Hours: Mon, Wed, and Fri at 4pm, or by appointment.
Meeting Times:
    Mon, Wed, and Fri, 12:00pm-12:50pm, Altgeld Hall Room 441
Tests:
    6pm-8pm on Wed Feb 15, Wed Mar 15, and Wed Apr 26, Altgeld Hall Room 145
Final Exam:
    Tue, May 9, 7:00pm-10:00pm, Altgeld Hall Room 441
 
Links:
    simplex Java applet, another Java LP solver.
    Kenji Ikeda has several Java demos.
    Jozsef Balogh is teaching Math 588 Optimization in Networks this semester.
    Alexandr Kostochka taught Math 482 in spring 2005.
    Hayri ├ľnal is teaching ACE 567: Advanced Programming for Applied Economics this semester.
 
Old Announcements:
(May 8) There was an error in the solution of the matrix game problem on Test #2; I had computed the optimal strategy of Player II, not Player I. A corrected solution is below. The useful facts on Test #3 also had an error: when using the lexicographic anticycling rules for dual simplex, the pivot is chosen by taking the lex-max over entries that are negative. A corrected version of the Test #3 facts, which will be given on the final exam, is below.
(May 3) The final exam is Tue, May 9, 7:00pm-10:00pm in 441 Altgeld. The exam will be cumulative over the entire semester. The final exam is worth 200 points, and will be about 50% longer than one of the tests. The format will be similar. At most one question in Part I and at most one question in Parts II and III will be about matroids.
(May 3) On Fri May 5 at 4pm we will have another review session in 141 Altgeld. You can pick up your graded Homework #13 then. I will be around at other times during the week and next week; email me for an appointment.
(Apr 21) The following useful facts will be given to you to use during Test 3.
(Apr 17) There will be a review session on Fri Apr 21 from 4pm-5pm in 441 Altgeld in lieu of normal office hours. The review session will be the same as previous ones: come prepared with questions.
(Mar 29) It's official: The third test will be held on Wed, Apr 26, 6pm-8pm, in 145 Altgeld. The test will cover the material up through Fri Apr 14 (branch and bound).
(Apr 9) Problem 4 on Homework 11 has a typo: the second constraint should be 3x1 -101 x2<= 1 (NOT >=). A corrected version is posted below.
(Mar 23) Thanks to everyone for filling out the informal early feedback form. Here is a summary of the results. I am always open to feedback from students. If you have any suggestions or comments during the rest of the semester, please let me know.
(Feb 20) I will be away the week of April 24-28. I am considering moving test #3 from Apr 19 to Wed, Apr 26, 6pm-8pm. Please check to see if you have any conflicts with this date.
(Mar 13) The following useful facts will be given to you to use during Test 2.
(Mar 8) The second test will be Wed Mar 15 from 6pm-8pm in Altgeld Hall Room 145. The test will cover everything up through Fri Mar 10's lecture, including duality, the revised simplex algorithm, and the primal-dual algorithm. There will be both computational problems and proofs, and three parts as last time. Calculators (including graphing calculators) may be used during the test for simple arithmetic; however, programmable functions (ie, doing the simplex algorithm or inverting a matrix) may not be used during the test. We'll use an honor code for this.
We will have lecture on Wed Mar 15 during our normal class time.
(Mar 13) Instead of normal office hours today, I will hold a review session at 4pm in 145 Altgeld. Come prepared with questions.
(Feb 28) I have posted a correction to the payoff matrix appearing in the solution for #3 of Homework #5. If this affects your grade, please see me and I will adjust your grade accordingly.
(Feb 16) There is a typo on Homework #5, problem #2. The third constraint should read 2x1+x2<=2, as it appeared in Practice #4. The version below is correct.
(Feb 13) We will have a review session for the test today 4pm-5pm in 441 Altgeld. The review session will be in place of my normal office hours. Bring any questions that you have.
(Feb 12) Below I have added three links to webpages with Java applets that demonstrate or solve linear programming problems. If you know of any other worthwhile sites, please let me know.
(Feb 8) All tests will be held in 145 Altgeld.
(Feb 6) The first test will be Wed Feb 15 from 6pm-8pm. I will announce the room for it shortly. The test will cover everything up through Wed Feb 8's lecture: concentrating on chapter 2 and the simplex algorithm. There will be both computational problems and proofs. Calculators (including graphing calculators) may be used during the test for simple arithmetic; however, programmable functions (ie, doing the simplex algorithm or inverting a matrix) may not be used during the test. We'll use an honor code for this.
We will have lecture on Wed Feb 15 during our normal class time.
(Jan 20) The tests will be held 6pm-8pm on Wed Feb 15, Wed Mar 15, and Wed Apr 19.
(Dec 12) Assignment of instructor to class.

    Back This page last modified .