Dr. Bogdan Savchynskyy, WiSe 2025/26
Summary
This lecture will be offered as a block-course from September 29 till October 10, 2025
This lecture substitutes the previously offered "Optimization for machine learning".
This lecture belongs to the Master in Physics (specialization Computational Physics, code "MVSpec"), Masters of Data and Computer Science, Applied Informatics, as well as Master Mathematics programs, but is also open for students of Scientific Computing and anyone interested.
The course is devoted to combinatorial optimization, which includes but not limited to algorithms on graphs, integer linear programming, pseudo-boolean optimization and submodularity.
A distinctive feature of this course is its motivation by machine learning applications, which shifts the optimization accent from attaining an optimal solution to a problem, to obtaining an accurate enough solution very fast. The reason for this shift is complexity of models used in modern artificial intelligence-related branches and the lesson they teach us: Better results can be easier attained by more accurate models rather than by more accurate optimization.
To build an accurate problem model, the latter must be learnable. To be used in learning pipelines, combinatorial algorithms must be fast. To attain the best practical results, the algorithms must be accurate enough.
Fast, accurate enough and learnable algorithms are three aspects we address in this lecture.
The material selection for the course emerges from lecturer's experience of combinatorial optimization in computer vision and machine learning.
The goals of the course:
- competent modeling of real-life combinatorial problems and usage of existing program packages to solve them;
- learn typical combinatorial optimization techniques and have a sufficient background for an independent literature search;
- learn how scalable, fast and accurate combinatorial solvers are build;
- understand the basics of convex analysis, convex optimization, convex duality theory, (integer) linear programs and their geometry.
- learn the cutting-edge results in the area of learning combinatorial solvers, i.e. estimating cost vectors and problem structure based on the training set.
Table of Contents
- Linear and Integer Linear Programs (ILP) and Their Geometry: Convexity, polyhedra, LP relaxation
- Linearization: From quadratic to linear integer objectives and constraints; Fortet’s and Sherali–Adams methods
- Convex Functions: Definitions and basic properties
- Lagrangian Duality: Subgradients, optimality conditions, relation to LP relaxation, reduced costs
- Scalable Convex (Dual) Optimization Techniques: Gradient, subgradient, coordinate descent, smoothing methods
- ILP Solvers Overview: How off-the-shelf solvers work—branching and cutting, presolving, simplex method for LPs
- Scalable Primal Heuristics: Greedy construction, local search, optimal recombination, memetic algorithms
- Quadratic Pseudo-Boolean Optimization: Algorithms, applications, role of submodularity
- Learning Parameters of Combinatorial Problems from Data: Bayesian optimization, structured SVMs, black-box differentiation, and recent advances
Schedule and Information
The lectures and exercises will be given in English .
Venue:
All lectures and exercises will take place in Mathematikon B (Berliner Str. 43), SR B128 Entrance through the door at the side of Berlinerstrasse. Ring the door bell labelled "HCI am IWR" to be let in. The lecture room is on the 3rd floor.
Lecture schedule:
- Lecture: Mo-Fr, 9:00 – 16:00, block-course, from September 29 till October 10, 2025
- Programming Exercises: Tue, 11:00 – 13:00, each weak in WiSe 25/26, the first exercise will take place on October 14, 2025
Contact: Dr. Bogdan Savchynskyy , Sebastian Stricker.
In case you contact us via email, its subject should contain the tag [ACO]. Emails without this tag have a very high chance to be lost and get ignored therefore!
The seminar Optimization in Machine Learning and Vision complements this lecture by taking a closer look at recent results and developments. We highly recommend it to all students interested in the topic.
Registration
Please register for the course in Müsli -- this is mz waz to communicate with you.
Course Material and Exercises
Will be uploaded to HeiBox.
Exam
- Format: Oral
- Eligibility: At least 50% of the total points from programming exercises. There will be 4 exercise sheets, you are not required to sit the exercise sessions in person and can submit your solutions online.
- Date and Time: Flexible. We typically use a doodle poll to accommodate both your schedule and mine. I usually offer several time slots: one to three in February and another one to three between March and May.