Linear Programming (Summer Term 2021)

Overview

• Format: Lectures with exercises (3/1/0)
• Head Teaching Assistant: Silvia Di Gregorio
• Creditable toward the modules INF-BAS2, INF-BAS6, INF-VERT2, INF-VERT6, CMS-LM-AI, CMS-LM-ADV (pending approval by the faculty council)
• Enrolment
• Forum

Contents

The course studies optimization problems whose objective function and constraints are expressed by linear inequalities. Geometric and algebraic insights into the structure of the problem are developed, with an emphasis on formal proofs. The theory behind the simplex method, the main algorithm used to solve linear optimization problems, is presented. In the course, we explore duality theory (including a brief introduction of sensitivity analysis) as well as theorems of the alternatives. If time permits, we will first examine how linear programming can be used to solve network flow problems and then discuss complexity of linear programming and the ellipsoid method.