Discrete Optimization - Math 570

University of South Carolina
Fall 2013

Course Information:

Our syllabus (in pdf format).
Meets in LeConte 303B, TTh 11:40 - 12:55.
The text is Linear Optimization: The Simplex Workbook by Glenn Hurlbert.
This is our awesome textbook
We will also cover some material from the following sources:
Alexander Schrijver's set of notes A Course in Combinatorial Optimization.
Santosh Vempala's course from MIT in 2003 Combinatorial Optimization. (Creative Commons License here. )

Contact Information:

Professor Aaron M. Dutle
Office: LeConte 418 B
Phone: 803-777-5965
email: dutle@mailbox.sc.edu
Office Hours: MW 1pm-2pm, or by appointment.

Notes:

We'll be using a somewhat different format for this course than for most mathematics courses you've taken before. On (most) Thursdays, I'll present some information in a standardish lecture format. I'll also give a selection of problems/ illustrations/ parts of proofs that I expect you to attempt prior to the next class period. I expect some number of these, hopefully enough to fill the entire Tuesday class, to be presented by you, the students.
Once you have written a solution to a problem well enough that you are prepared to present, let me know, and I will include you in the drawing for presenting it when it is due. If it is correct and presented well, the student will receive full credit for the solution. If not the student may recieve partial credit, and another student will be asked to present their solution. Your grade for homework and class participation will be determined in this way.
There will also be a midterm and a final exam, which will compose the rest of your grade.

Simplex Solver:

Here's a link to the textbook author's online simplex method helper WebSim. It worked this morning when I checked, but not this afternoon... Let me know if it is or isn't working for you.

THE FINAL EXAM <-- that's a link...

The solutions are due to me by midnight, Dec 12. They can be turned in to me via email, in my office, or placed in my mailbox. Please email me once you have turned your solutions in.

Schedule (tentative)

Tuesday Thursday


Aug 22:
Introduction and Syllabus; Basics of Graphs and Digraphs
Problem Set 1
Aug 27:
Presentations:
Problem Set 1: 1-4.
Aug 29:
Shortest Paths in Graphs
Problem Set 2
Sept 3:
Presentations: 1.3, 1.4, 2.1-2.6		 Sept 5:
More on Shortest Paths
Problem Set 3
Sept 10:
Presentations: 3.4		 Sept 12:
Spanning Trees
Problem Set 4
Sept 17:
Presentations:2.2, 2.3, 3.1-3.3,3.5, 4.1-4.5		 Sept 19:
Matching in Graphs I
Problem Set 5
Sept 24:
Presentations:4.2, 5.1, 5.5, 5.6		 Sept 26:
Matching in Graphs II
Problem Set 6
Oct 1:
Presentations:4.4-5, 5.2-4, 6.1-4		 Oct 3:
Review
Oct 8: Test 1 Oct 10:
Linear Optimization: Intro
Problem Set 7
Oct 15:
Linear Optimization: Continued
Problem Set 7		 Oct 17:
Fall Break, No Classes
Oct 22:
Presentations: Problem Set 7		 Oct 24:
Simplex Algorithm: Phase II
Problem Set 8
Oct 29:
Presentations: Problem Set 8		 Oct 31:
Simplex Algorithm: Phase I
Problem Set 9
Nov 5:
Presentations: Problem Set 9		 Nov 7:
Duality and Complementary Slackness
Problem Set 10
Nov 12:
Presentations: Problem Set 10		 Nov 14:
Game Theory
Problem Set 11
Nov 19:
Presentations: Problem Set 11		 Nov 21:
Intro to Complexity Classes
Problem Set 12
Nov 26:
Presentations:		 Nov 28:
Thanksgiving, No Classes
Dec 3:
Presentations:		 Dec 5:
Dec 12:
Final Exam
Final Problems, due by midnight.