To support our site, Class Central may be compensated by some course providers.

Linear and Integer Programming

University of Colorado Boulder via Coursera

students interested

Taken this course? Share your experience with other students. Write review

Overview

Sign up to Coursera courses for free Learn how

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.


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

Taught by

Sriram Sankaranarayanan

Help Center

Most commonly asked questions about Coursera Coursera

Reviews for Coursera's Linear and Integer Programming
3.8 Based on 8 reviews

  • 5 stars 38%
  • 4 stars 25%
  • 3 stars 25%
  • 2 star 0%
  • 1 star 13%

Did you take this course? Share your experience with other students.

Write a review
  • 1
Anonymous
5.0 4 years ago
Anonymous completed this course.
Excellent introductory course to LPs and ILPs. The lectures were very clear, and a lot by patient repetition and emphasis helped to reinforce the ideas. While the main lectures flow well and in a structured way, the several supplementary lectures serve to give a nice complete picture.

The progamming assignments were critical to learning and very nice. Especially, the teachers had provided an exhaustive list of test cases that srongly help in the coding! The other amazing part was the participation of the lecturers in the discussion forum; almost all questions were answered! The huge amount of time put into this course (and especially the support on the forum) was incredible.

Note that the course does not claim to be more than basic and introductory. Hence, for someone with advanced knowledge and skills, the repetition may jar and even bore. Then again, there is always the option to speed up videos!
2 people found
this review helpful
Was this review helpful to you? Yes
Mark W
4.0 4 years ago
Mark partially completed this course.
This course is very useful for solving various optimization problems. I enjoyed the lectures and got quite a bit out of them. I found the quizzes easy since they were heavily math-based and I understood the math from the lectures, but I really struggled on the programming assignments. I chose to use Python since, of the suggested languages, it was the one I had the most familiarity with. I ran into some problems with libraries and since what I was using wasn’t the most common choice I had limited help. A lot of students were using Matlab, and in retrospect that might have been the better way to go since it was more supported by the instructor. Enrollment in the course does come with 3 free months of Matlab usage.
1 person found
this review helpful
Was this review helpful to you? Yes
Gregory S
4.0 3 years ago
by Gregory audited this course and found the course difficulty to be medium.
Linear and Integer Programming is a 7-week course covering linear programming

in detail. The course focuses on teaching the simplex method for optimizing systems linear equations with constraints for the first 4 weeks and then covers integer programming and applications. You should be comfortable with basic linear algebra and calculus before taking this course. The course includes optional programming assignments that allow students to build up their own simplex algorithms over the course of the class, but you can easily pass the course just taking the weekly quizzes.

Was this review helpful to you? Yes
Anonymous
5.0 5 years ago
Anonymous completed this course.
Instructors teach us details about Lp problems. Slides are excelent. Weekly homeworks helped me to understand details about simplex method. Course contains three programming homeworks for solving simplex and ILP with amazing unit tests. Instructor answers to lot of post forum.
1 person found
this review helpful
Was this review helpful to you? Yes
Anonymous
5.0 4 years ago
Anonymous completed this course.
Not very hard course with very good and detailed explanations and very active and helpful staff in the forums. Really worthy and fun :-)
1 person found
this review helpful
Was this review helpful to you? Yes
Olivia A
3.0 4 years ago
Olivia is taking this course right now, spending 2 hours a week on it and found the course difficulty to be medium.
1 person found
this review helpful
Was this review helpful to you? Yes
Anonymous
1.0 5 years ago
Anonymous completed this course.
Horribly slow going course. The slides are low quality, not ready for presentation. Not interesting at all: most time is spent on lengthy explanations about trivialities related to the simplex algorithm. Don't take the class, it's a waste of your time. Instead, go to wikipedia, and read the relevant articles.
1 person found
this review helpful
Was this review helpful to you? Yes
  • 1

Class Central

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free

Never stop learning Never Stop Learning!

Get personalized course recommendations, track subjects and courses with reminders, and more.