CS6375 Linear Programming

Logistics

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

• Errata for the text

• 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

You must pass the final exam to get more than a D in the course.

  20 

  30 

  50