CS6375 Linear Programming
Logistics
| Professor | David Bremner |
| Office | ITC321 |
| Office Hours | hours |
| Phone | 447-3300 |
| bremner ATSIGN unb.ca | |
| Web | http://www.cs.unb.ca/~bremner/teaching/cs6375 |
| Lectures | MWF 12:30-13:30 GWD110 |
Overview
Many practical problems such as
- Network Flow
- Production Planning
- Linear Regression (fitting)
- Pattern Classification
- Cutting Paper Rolls
can be modelled as finding the maximum of a linear objective function over a set of solutions constrained by linear inequalities. Such mathematical models are known as Linear Programming problems. There good algorithms to solve them, both in theory and practice.
In this course we will try to get a taste of both the mathematical foundations of Linear Programming, and the many ways in which it can be useful.
The course will be a mixture of theory and getting your hands dirty doing some optimization. Knowledge of basic linear algebra would be an asset.
Prerequisites:
- Linear algebra (matrices, vectors, linear subspaces, solving linear systems).
- A course in algorithms or equivalent mathematical maturity.
Text
The course text is Understanding and Using Linear Programming, by Matousek and Gaertner
At detailed introduction to the MathProg language can be found in the AMPL Book
For integer programming, cutting planes, and branch and bound, some of the material is based on A First Course in Combinatorial Optimization by Lee
See also books
Tentative list of topics
- Applications and Examples
- Integer Programming and Relaxation
- Standard Form and Basic Solutions
- Elementary convexity
- The Simplex Method
- Duality
- Cutting planes
- Branch and Bound
- Introduction to interior point methods.
Evaluation
| Component | percent |
|---|---|
| midterms | 30 |
| assignments | 20 |
| project | 25 |
| final exam | 25 |
Your average on the midterms and final must be a pass to get more than a D in the course.