## 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

http://www.cs.mcgill.ca/~cmeagh1/

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*