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 to:
1. Understand the basic theory behind LP, algorithms to solve LPs, and the basics of (mixed) integer programs (ILP).
2. Understand important and emerging applications of LP and ILPs to economic problems (optimal resource allocation, scheduling problems), machine learning (SVM), and combinatorial optimization problems.
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.
Mathematical Maturity (undergraduate algorithms or CS theory) and basic programming ability.
A background in engineering or applied sciences could be useful, as well.
The prerequisites for this class include:
Textbook: Linear Programming by Robert J. Vanderbei (available online from author's webpage).
Alternative: Linear Programming by Vasek Chvatal, W.H. Freeman published, 1983. This book still remains a very clear and concise presentation.
Other texts: We may borrow material that is covered in some of the texts below. As you go down this list, the texts become less relevant for this class but remain very important for the broader field of optimization that we seek to introduce through this class.
Each class will consist of many short lecture videos between 10-15 minutes in length with nearly 1.5-2 hours of lectures each week. We will have weekly assignments involving 5-10 problems each week. These assignments will either be multiple choice or ask you to compute something and enter the answer. We will have four programming assignments (one every two weeks) that will incrementally help you build an ILP solver. Programming assignments can be done in virtually any general purpose language.
The course will be structured with two interactive tracks: algorithms/theory for linear optimization problems and applications. The applications will include ideas on modeling real-life optimization problems as linear programs and the appropriate use of concepts like duality in finding and interpreting solutions.