The course is an introduction to linear and discrete optimization - an important part of computational mathematics with a wide range of applications in many areas of everyday life.

Preview LecturesThis
course serves as an introduction to linear and discrete
optimization from the viewpoint of a mathematician or computer
scientist. Besides learning how linear and discrete optimization can be applied, we focus on
understanding methods that solve linear programs and discrete optimization problems in a mathematically
rigorous way.

We will answer questions like:

- Does a particular method work correctly?
- Does it terminate and, if yes, in what time?
- Can we prove that a solution is optimal?

The course constitutes about half of the material on linear and discrete optimization that is taught for mathematics and computer science undergraduates at EPFL and will feature video lectures, quizzes, programming assignments, and a final exam.

- Linear programming, modeling, equivalence of standard forms
- Basic solutions, primal and dual feasible basic solutions, pivoting and the simplex method
- Termination and complexity of the simplex method
- Integer programming, bipartite matching and flows
- Models of computation, bit-complexity

The
most important prerequisite is familiarity with linear algebra. It will
be useful to have some programming proficiency in a higher level
programming language such as Java or Python.

Although
the course is self-contained and the lecture notes will be available on-line, it will be useful to consult further literature. There are many
excellent texts on discrete optimization. Among our favorites are the
books Introduction to Linear Optimization by Bertsimas and Tsitsiklis, Understanding and Using Linear Programming, by Matousek and Gärtner, and Theory of Linear and Integer Programming by Schrijver.

The
class consists of lecture videos punctuated by quizzes. There will
also be standalone homeworks that are not part of the video lectures, programming assignments, and a final exam.

Students who successfully complete the class (70% of assignments and final exam) will receive a certificate signed by the instructor.

For this course, all you need is an Internet connection, and the time to read and think.

The most important prerequisites are solid knowledge of linear algebra and some programming proficiency in a higher level programming language such as Java or Python.