## Discrete Optimization - 1

###
COMP566A
Autumn 2005 McConnell 103

### TuTh 8:35 - 9:55am

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,
computer implementations, and integer programming. This part of the
course will last about 5-6 weeks. The second part of the course will
concern the interplay between linear programming and geometry and its
application to networks and
games. This part of the course will last about 2-3 weeks. The third
part 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) and written report 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:** 308-360 (or 308-362) and 189-223.

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

Mon and Wed 10-11 or by appointment

Class Tests:
October 13 and November 17.

Academic Integrity: Please read http://www.mcgill.ca/integrity/

*August 25 2005*