Discrete Optimization - 1

 COMP566                  Autumn 2008    TuTh 8:35 - 9:55am   McConnell 103

This course is concerned with the formulation and solution of linear programs and related geometrical problems. In the first part of the course, the basic foundation will be laid: problem formulation, the simplex method, duality theory, the revised simplex method, the dual simplex method and connections to geometry and combinatorics. This part of the course will last about 5 weeks. The second part of the course will consist of topics selected from game theory,  network optimization, integer programming and polyhedral computation. This part of the course will last about 3 weeks.  The remainder of the course will consist of a survey of some of the latest developments in linear programming, including interior point methods, and a study of selected applications of linear programming to solve both applied and theoretical problems. The topics selected will depend on the interests of the class. For the third part of the course, each student will be expected to prepare a class presentation (20 minutes)  on one such application. Depending on the class size, students may be required to work in teams of two.

There will be two  in-class tests worth 30% each, covering material given in the first two parts of the course. The presentation or project will count 20%, and the remaining 20% of the mark will be from 4 homework assignments. Some of the homework will involve computing. In particular, we will use  the symbolic computation packages MAPLE  as a tool in solving linear programs. Students will also have access to lp-solve and the commercial package CPLEX to solve larger problems.

Assignments are due in class. Late assignments should be given directly to the TA or left in my mailbox.
Penalty: -10% per day, including weekends.

Prerequisites:  COMP360 (or COMP362) and MATH223 (or more advanced linear algebra course). These are compulsory for undergraduates.

Required Text: Linear Programming, by V. Chvatal, W.H. Freeman

Texts on Reserve at Schulich Library:
 Linear Programming, by V. Chvatal
Linear Programming, by J. Ignizio and T. Cavalier
Integer Programming, by L. Wolsey

Instructor:  David Avis
McConnell 308  avis@cs.mcgill.ca http://cgm.cs.mcgill.ca/~avis
Office Hours: Tu, Th  10-11

Teaching Assistant: Conor Meagher
Office: MC232
email: cmeagh1 at cs.mcgill.ca
Office hours, by appointment.

Class Tests: TBA

Mandatory statements:

In accord with McGill University’s Charter of Students’ Rights, students in this course have the right to submit in English or in French any written work that is to be graded.

McGill University values academic integrity.  Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see www.mcgill.ca/integrity for more information).


August 11,  2008