Oct 20th 2014

Linear and Integer Programming (Coursera)

This course will cover the very basic ideas in optimization. Topics include the basic theory and algorithms behind linear and integer linear programming along with some of the important applications. We will also explore the theory of convex polyhedra using linear programming.

Linear Programming (LP) is arguably one of the most important optimization problems in applied mathematics and engineering. The Simplex algorithm to solve linear programs is widely regarded as one among the " top ten " algorithms of the 20th century. Linear Programs arise in almost all fields of engineering including operations research, statistics, machine learning, control system design, scheduling, formal verification and computer vision. It forms the basis for numerous approaches to solving hard combinatorial optimization problems through randomization and approximation.

The primary goals of this course will be

1. Understand the basic theory behind LP, algorithms to solve LPs, and basics of (mixed) integer programs.

2. Understand important and emerging applications of LP to economic problems (optimal resource allocation, scheduling problems), machine learning (SVM), control design (finite horizon optimal control, dynamic programming), and formal verification (ranking functions, symbolic execution, SMT solvers).

At the end of the course, the successful student will be able to cast various problems that may arise in her research as optimization problems, understand the cases where the optimization problem will be linear, choose appropriate solution methods and interpret results appropriately. This is generally considered a useful ability in many research areas.

Suggested Readings: