VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

401-3902-25L 9 Credits BSC , MSC D-MATH
You're viewing possible stale or outdated data. Please check the latest semester for more up-to-date information.

Discrete Optimization

Lecturers & Examiners: Prof. Dr. Robert Weismantel
VVZ CR n/a

Last Updated: 2026-06-01 11:33:47

Abstract

This course gives an introduction to discrete optimization problems.A discrete optimization problem is the task to optimize a linear function over the integer points in a polyhedron. This topic is very rich in terms of the underlying theoretical tools that one can use to understand and solve such problems.

Objective

The goal of this course is to obtain an understanding of the theory of discrete optimization that underlies algorithms to solve such problem. Discrete optimization is a rich topic that includes lattice theory, approximation algorithms and polyhedral combinatorics.

Content

Part 1: From linear to integer optimization Linear and Integer optimization problems are strongly related via underlying polyhedra. This is the classical setting of polyhedral combinatorics. Part 2: Binary optimization We study various topics and techniques related to linear problems in variables that can attain values zero or one only. This is the classical setting of approximation algorithms and cutting plane procedures. Part 3: General integer optimization This part is devoted to a study of integer optimization in general integer variables. We will discuss lattice theory and the theory of integral generating sets in cones to understand the subject.

Resources

Lecture Notes

Lecture notes are available

General Information

Language
English
Levels
BSC , MSC
Frequency
Yearly recurring

Examination

Type
session examination
Mode
written 120 minutes
Aids
None

Course Components

Type Title Time & Place Hours
lecture Discrete Optimization
on 27 February 2025, 10:15-12:00 in ML J 34.1 (instead of HG E 1.1)
  • Wed 10:15-12:00 (HG E 1.1)
  • Thu 10:15-12:00 (HG E 1.1)
  • 27.02 Date 10:15-12:00 (ML J 34.1)
4 h weekly
exercise Discrete Optimization
Groups are selected in myStudies. Tue 16-17 (starting in the second week of the semester)
  • Tue 16:15-17:00 (HG E 1.1)
1 h weekly

Offered In