Spring 2003 INEN 689: Theory of Linear Inequalities

Hours: 3

Contact Info:

Illya V. Hicks

Office: 237k Zachry

Phone: 458-4182

Email: ivhicks@ie.tamu.edu

Office Hours: 1:30pm-2:30pm MW or by appointment

Prerequisites: Linear Algebra

Course Description: This course focuses on fundamental concepts in polyhedral theory such as Farkas’ Lemma, LP-duality, Caratheodory’s Theorem, faces, decomposition of polyhedra, polarity, blocking and anti-blocking polyhedra and total dual integrality. We will also study clutters and their relationship to perfect graphs.

Textbook: Schrijver, A., Theory of Linear and Integer Programming, John Wiley & Sons, New York, 1986

Grading Policy:

Homework (2-4) and Final Presentation 100%

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:

Fundamental concepts Chapter 7

Structure of Polyhedra Chapter 8

Polarity, Blocking and Anti-blocking Polyhedra Chapter 9

Integer Polyhedra and Total Dual Integrality Chapter 22

Clutters Notes

Perfect graphs Notes

Final Presentation:

The final presentation will consist of your critique of a fairly recent journal publication (with my approval) related to one of the subjects discussed in class. A report is also required. The report and presentation should consist of an overview of the paper, history of the problem, intellectual merit of the paper and any possible future work that could be derived from the paper. Time allotted for the presentation should be 10 to 15 minutes. The presentations will begin on April 21^th. The final report will also be due on that date.

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).