# Linear and Integer Programming

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.

## About the Course

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.

## Course Syllabus

Introductory Material

• Introduction to Linear Programming.
Week #1:
• The Diet Problem.
• Linear Programming Formulations.
• Tutorials on using GLPK (AMPL), Matlab, CVX and Microsft Excel.
• The Simplex Algorithm (basics).
Week #2:
• Handling unbounded problems
• Degeneracy
• Geometry of Simplex
• Initializing Simplex.
• Cycling and the Use of Bland's rule.
Week #3:
• Duality: dual variables and dual linear program.
• Strong duality theorem.
• Complementary Slackness.
• KKT conditions for Linear Programs.
• Understanding the dual problem: shadow costs.
• Extra: The revised simplex method.
Week #4:
• Advanced LP formulations: norm optimization.
• Least squares, and quadratic programming.
• Applications #1: Signal reconstruction and De-noising.
• Applications #2: Regression.
Week #5:
• Integer Linear Programming.
• Integer vs. Real-valued variables.
• NP-completeness: basic introduction.
• Reductions from Combinatorial Problems (SAT, TSP and Vertex Cover).
• Approximation Algorithms: Introduction.
Week #6:
• Branch and Bound Method
• Cutting Plane Method
Week #7:
• Applications: solving puzzles (Sudoku), reasoning about systems and other applications.
• Classification and Machine Learning

## Recommended Background

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:

• Basic College Level mathematics: calculus and some linear algebra: matrices, matrix operations and solving linear equations.
• Programming skills:  However,   students without a programming background  can pass the course by solving all the weekly assignments.

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.

1. Combinatorial optimization: Algorithms & Complexity, by Christos Papadimitrou and Ken Steglitz.
2. Linear Programming series of two books by G.B. Danzig and M.K. Thapa.
3. Schrijver's book on the Theory of Integer Linear Programming and Integer, Integer and Combinatoral Optimization book by Wolsey and Nemhauser are also good references.
4. Convex Optimization by Boyd and Vandenbreghe is a good reference for the more general area of convex optimization.
5. Numerical Optimization by Nocedal and Wright is a great reference for solving non-linear optimization problems.

## Course Format

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.

## FAQ

• Will I get a statement of accomplishment after completing this class?
Yes.

• What textbooks will I need for this class?
No textbook is officially required. However, there are numerous great textbooks on this topic. We are hoping you will be able to find one. You can always cross check whether your textbook has adequate coverage for the topics to be taught in this class.

We recommend a great textbook by Prof. Vanderbei (see http://www.princeton.edu/~rvdb/LPbook/). It is available as a free download.
The classic book by Chvatal is an excellent textbook but sadly out-of-print.

• What are the pre-requisites?
The prerequisites for this class include:
• Basic College Level mathematics: calculus and some knowledge of linear algebra.
• Some programming skills:  However,   students without a programming background  can pass the course by solving the weekly assignments.

• What will the level of the class be?
Normally, this will be a junior/senior level undergraduate class or even a beginning graduate class, depending on the major and the university. A highly motivated high school student with advanced mathematical skills can follow along.
• What skills will I learn?
The class is about Linear and Integer Programming. You will definitely learn:

what optimization problems are, what are linear optimization problems, what are the applications, what are the algorithms used for solving LPs, and how do they work?

In addition, we found through our previous offering in 2013 that the course helps many students think mathematically and improve the programming skills. We were proud of the many students from last year who took on some of the challenging programming assignments and reported a big confidence boost in their skills.
• Can I get university course credits for this class?
Unfortunately, not at this time. University of Colorado, Boulder may be considering ways of recognizing Coursera classes, but there is no consensus at this point in time.

However, Prof. Sankaranarayanan teaches an on-campus class (CSCI 5654) at the University of Colorado, Boulder, and it will be available simultaneously on-line for credit through CAETE (see http://cuengineeringonline.colorado.edu/ ). You can enroll for our class CSCI 5654 through CAETE from anywhere in the world.

• Are we going to do rigorous mathematical proofs? How much programming do you expect to do?
We will cover proofs for interested students. But we will never have proofs in the assignments.

Assignments will test the conceptual ideas in the class including algorithms, and many assignments may ask you to use an existing LP solver (open source or commercial) to solve a LP/ILP and interpret its answer. We do not consider this part as programming: any computer user should be able to manage this.

We will have programming assignments: in fact, students will get to build their own LP and later ILP solver in stages. But the programming is not going to be for everyone. The last assignment (ILP) will be quite intense and definitely challenging to students.

• Is there a particular programming language that you expect for the assignments?
No. We will allow students to program in most general purpose languages. However, by the very nature of the assignments, some languages such as python, C/C++, Java, Haskell, Scheme, Lisp, MATLAB/Octave, ... will be more suitable than others. You can judge for yourselves as soon as the assignments are posted on week 1.

• What will the coursework involve?
Coursework will involve watching videos, solving weekly assignments and tackling four programming assignments. See below on how the grading will work.
• How do I pass? How does distinction work?

To pass the class: you will need to get at least 35% of the total grade.  The pass cutoff is  designed so that students can pass either by solving some/all of the programming assignments OR by solving some/all of the weekly assignments.

To score a distinction: you will need to get at least 85% of the total grade. To score a distinction, students must do well in ALL aspects of the course: programming as well as weekly assignments.