CAAM 474: Combinatorial Optimization
Course Description
Formulation techniques are studied, along with general approaches for solving integer and combinatorial optimization problems. Topics include basic polyhedral theory, cutting planes, minimum spanning trees, shortest paths, network flow problems, matchings, and matroids. The course also discusses branch-and-bound and the traveling salesman problem.
Time and Room
T TH 9:25 - 10:40
Sewall Hall 560
Instructor
Office: Duncan Hall 3020
Phone: x5667
Office Hours: 11-12pm T & TH or by appointment
email: ivhicks AT rice.edu
Textbook
Cook, William J., Cunningham, William H., Pulleyblank, William R. and Schrijver, Alexander, Combinatorial Optimization, John Wiley and Sons, New York, 1998.
Grading Policy
Tests (2) and Project (1) 75%
Homework (2-3) 25%
Groups
The students will divide into groups of 3 or 4 for group presentations and to discuss homework.
Homework Policy
Students can only discuss homework with their group members and the instructor. Also, students may use outside references with proper citation. Although homework can be discussed within the groups, homework must be turned in individually.
Homework is due at the end of class of the due date and 10% will be deducted from the grade of homework for each day late.
Course Outline
Duality and Farkas’ Lemma Appendix A
Integrality of Polyhedra Chapter 6
Optimal Trees and Paths Chapter 2
Maximum Flow Problems Sections 3.1-3.4
Optimal Matchings Sections 5.1-5.3
Matroids Sections 8.1-8.2
Americans with Disabilities Act Statement
Any student with a documented disability seeking academic adjustments or accommodations is requested to speak with me during the first two weeks of class. All discussions will remain as confidential as possible. Students with disabilities will need to also contact Disability Support Services in the Ley Student Center.
