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?
- What textbooks will I need for 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?
- 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?
- What skills will I 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?
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?
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?
- What will the coursework involve?
- 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.
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.