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.


Frequently Asked Questions

  • 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.


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.