## Discrete Optimization - 1

### 308-566A
Autumn 2002 Leacock 14
TuTh 1-2:30pm

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 instead do a project involving an application of the techniques
learned in the course, instead of the presentation.
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-405) 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://www.cs.mcgill.ca/~avis

Office Hours: Tu, Th 11-12

**Teaching Assistant**: Bohdan Kaluzny
(to be confirmed)

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

Office Hours: 10:30-11:30 Mon and Wed, MC232

Class Tests: Thurs
October 10 in class, and November(tba)

*October 1, 2002*