## Discrete Optimization - 1

### COMP566A
Autumn 2003 ENGTR 1100
TuTh 1:05-2:25pm

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 polynomial time 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 11-12

**Teaching Assistant**: Bohdan Kaluzny

McConnell 232 beezer@cs.mcgill.ca http://www.cs.McGill.CA/~beezer

Office Hours: M 10-11, W 3:30-4:30
or by appointment

Class Tests: Thurs October
9 in class, and November 11

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

*October 16, 2003*