Fall 2006 INEN 628:  Combinatorial Optimization

 

Hours:  3

 

Contact Info:

Professor Illya V. Hicks

Office:  237k Zachry

Phone:  458-4182

Email:  ivhicks@tamu.edu

Office Hours: 11:00am-12:00pm TTh or by appointment

 

 

Prerequisites:  INEN 622 or equivalent

 

Course Description:  Formulation techniques are studied, along with general approaches for solving integer and combinatorial optimization problems:  basic polyhedral theory, cutting planes, branch and bound, minimum spanning trees, shortest paths, network flow problems, matchings and matroids.  The course also covers NP-completeness and the traveling salesman problem.

 

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                                                         25%

 

Groups:  The students will divide into groups of 2 or 3 for group presentations and to discuss homework.

 

Group Project: the group project will involve C or C++ programming.

 

Homework Policy:  Students can only discuss homework with their group members and me.  Also, students may use outside references. Although homework can be discussed within the groups, homework must be turned individually.

 

Late Homework:  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.5

Optimal Matchings                                            Sections 5.1-5.4

Matroids                                                             Sections 8.1-8.2

Traveling Salesman Problem                           Sections 7.3-7.4

NP-Completeness                                               Sections 9.5-9.8

 

Americans with Disabilities Act Statement:

If you believe you have a disability requiring an accommodation, please contact the Department of Student Life, Services for Students with Disabilities in Room 126 of the Koldus Building (845-1637).

 

Excused Absences:

For an excused absence due to illness please fill out a Texas A&M University Explanatory Statement for Absence from Class form which is available at http://attendance.tamu.edu.  Also, an absence for a non acute medical service does not constitute an excused absence.