Linear Programming (Summer Term 2023)

Overview

• Format: Lectures with exercises (3/1/0)
• Lecturer: Silvia Di Gregorio
• Creditable toward the modules CMS-LM-ADV, CMS-LM-AI, INF-BAS2, INF-BAS6, INF-LE-MA, INF-VERT2, INF-VERT6
• Enrolment
• Additional information (OPAL)

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.