Computer Science Math
Introduction to network optimization and discrete optimization

Course Details

Language English
Duration 5 week
Effort 6 hour/week
Description

Introduction to the mathematical concept of networks, and to two important optimization problems on networks: the transshipment problem and the shortest path problem. Short introduction to the modeling power of discrete optimization, with reference to classical problems. Introduction to the branch and bound algorithm, and the concept of cuts.

What you will learn


  • Networks: you will be introduced to the mathematical formalism of graphs and networks.

  • Transhipment: you will learn about the transhipment problem (also called "minimum cost flow problem"), its properties, and some special instances.

  • Shortest path: you will learn about algorithms to find the shortest path in a network.

  • Discrete optimization: you will learn how to specify a discrete optimization problem.

  • Exact methods for discrete optimization: you will be introduced to two algorithms to solve discrete optimization problems.

Prerequisites

The course assumes no prior knowledge of optimization. It relies heavily on linear algebra, analysis and calculus (matrices, derivatives, eigenvalues, etc.)
The knowledge of the programming language Python is an asset to learn the details of the algorithms. However, it is possible to follow the course without programming at all.

Plan

The course is structured into 5 sections.


  • Networks: you will be introduced to the mathematical formalism of graphs and networks.

  • Transhipment: you will learn about the transhipment problem (also called "minimum cost flow problem"), its properties, and some special instances.

  • Shortest path: you will learn about algorithms to find the shortest path in a network.  

  • Discrete optimization: you will learn how to specify a discrete optimization problem.

  • Exact methods for discrete optimization: you will be introduced to two algorithms to solve discrete optimization problems.

Course instructors

Prof. Michel Bierlaire

Michel Bierlaire holds a PhD in Mathematical Sciences from the University of Namur, Belgium. Between 1995 and 1998, he was research associate and project manager at the Intelligent Transportation Systems Program of the Massachusetts Institute of Technolog…

École polytechnique fédérale de Lausanne

Free online courses from École polytechnique fédérale de Lausanne

EPFL is the Swiss Federal Institute of Technology in Lausanne. The past decade has seen EPFL ascend to the very top of European institutions of science and technology: it is ranked #1 in E…

93 instructors