# CS6375 Linear Programming

## Logistics

Professor |
David Bremner |

Office |
Gillin C115 |

Office Hours |
hours |

Phone |
447-3300 |

Email |
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 LeeSee 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.