Seminar in Discrete Optimization

Organizers: René Brandenberg, Michael Ritter, Andreas S. Schulz, Stefan Weltge, Andreas Wiese

Upcoming talks

20.05.2025 16:00 Leon Jendraszewski: Assigning new employees to positions

We study a problem arising in the management of staff positions in institutions with a cameralistic budgeting system, for example in public universities in Germany. When a new employee is hired, she needs to be assigned to one or (partially) to several of the available positions. These position may already be (partially) assigned to other staff members during certain time periods. Some positions are better suited for the new hire due to, e.g., their associated pay grades or other administrative reasons. One seeks a solution with assignments to suitable open positions and wants few changes of those assignments over time. This yields a multi-objective optimization problem with a lexicographic objective function which can be seen as a scheduling problem with non-availability periods for the machines. We derive structural insights into this problem and present several MIP-formulations for it. Their solutions are optimal w.r.t. the three most important objectives and optimal or near-optimal w.r.t. the least important objective, respectively. In particular, we are able to solve our problem faster than with a straight-forward approach if one is willing to potentially sacrifice a bit of accuracy in the least important objective. In addition, we present very fast combinatorial algorithms for important special cases of the problem. Overall, we can solve most practically relevant instances in less than a few seconds. Our optimization tool was developed in collaboration with the administration of the School of Computation, Information, and Technology (CIT) at the Technical University of Munich where it is now used on a regular basis.

Previous talks

06.05.2025 16:00 Alexandra Lassota: Integer Programs meet Fixed-Parameter Tractability

Solving Integer Programs (IPs) is generally NP-hard. But this does not imply that all instances are inherently hard. In fact, a substantial body of research has focused on identifying tractable subclasses and developing efficient (fixed-parameter tractable) time algorithms for those. This talk will give a little overview of some of the key results and techniques.

29.04.2025 16:00 Leander Schnaars: A 3.415-Approximation for Coflow Scheduling via Iterated Rounding

We provide an algorithm giving a 140/41 (3.415)-approximation for Coflow Scheduling and a 4.36-approximation for Coflow Scheduling with release dates. This improves upon the best known 4- and respectively 5-approximations and addresses an open question posed by Agarwal, Rajakrishnan, Narayan, Agarwal, Shmoys, and Vahdat [Aga+18], Fukunaga [Fuk22], and others. We additionally show that in an asymptotic setting, the algorithm achieves a (2+ϵ)-approximation, which is essentially optimal under P≠NP. The improvements are achieved using a novel edge allocation scheme using iterated LP rounding together with a framework which enables establishing strong bounds for combinations of several edge allocation algorithms.

10.04.2025 11:00 Richard J. Gardner (Western Washington University): The Hyperplane and Mahler Conjectures

The talk focuses on two the 66 problems stated in my book Geometric Tomography that are arguably the most notorious in convex geometry: Bourgain’s hyperplane conjecture from 1986 (finally confirmed last year) and Mahler’s conjecture from 1939 (still open). Both have great significance, not only for convex geometry, but for mathematics as a whole. A fairly comprehensive survey of these two important questions will be attempted, including their relationship to each other and to many other open conjectures from diverse areas of mathematics.

25.03.2025 16:00 Mojtaba Jazaeri: Some related topics on distance-regular graphs

This talk is about a certain kind of finite undirected graph, said to be distance-regular. In this talk, the following concepts will be relevant. We will consider the concepts of Q-polynomial property, perfect 1-codes, and Cayley graphs.

03.12.2024 16:00 Ruilong Zhang: Fair Allocation with Scheduling Constraints

We study a fair resource scheduling problem, where a set of interval jobs are to be allocated to heterogeneous machines controlled by intellectual agents. Each job is associated with release time, deadline, and processing time, such that it can be processed if its complete processing period is between release time and deadline. The machines gain possibly different utilities by processing different jobs, and all jobs assigned to the same machine should be processed without overlap. We consider two widely studied solution concepts, namely, maximin share fairness and envy-freeness. For both criteria, we discuss the extent to which fair allocations exist and present constant approximation algorithms for various settings.

19.11.2024 16:00 Steffen Borgwardt: A Cycle-Cancelling Heuristic for The Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is one of the most-studied hard problems in combinatorial optimization. We developed a new algorithm that uses a connection between Minimum Cost Flow Problems (MCF) and the TSP to improve on a given local optimum. MCF problems can be solved efficiently through linear programming or combinatorial algorithms such as cycle-cancelling. We investigated the potential of cycle-cancelling in the context of the TSP. Through a restriction of the search space of cycles to cancel for a given tour, practical results exhibit that only a low number of subtours is created, and a simple patching step suffices for a high success rate and gap closure towards an optimum.

05.11.2024 16:00 Elisa Dell'Arriva: Approximation Schemes on Knapsack and Packing Problems of Hyperspheres and Fat Objects

Geometric packing problems have been investigated for centuries in mathematics and a notable example is the Kepler's conjecture, from the 1600s, about the packing of spheres in the Euclidean space. In this talk, we mainly address the knapsack problem of hyperspheres. The input is a set of hyperspheres associated with profits and a hyperrectangular container, the knapsack. The goal is to pack a maximum profit subset of the hyperspheres into the knapsack. For this problem, we present a PTAS. For a more general version, where we can have arbitrary fat objects instead of hyperspheres, we present a resource augmentation scheme (an algorithm that gives a super optimal solution in a slightly increased knapsack).

29.10.2024 16:00 Dario Schmid: Optimization of Endurance Runs of Electric Engines Using MIP

This thesis presents a mathematical formulation for time-shortening endurance runs of electric drive machines in the automotive industry. These runs test motor service life, identifying issues for future development. A program developed here automatically generates endurance profiles, factoring in conditions like maximum temperature and damage targets. Predefined blocks of speed and torque are combined to create a profile with minimum running time using Mixed Integer Programming (MIP) and solvers like Gurobi, HiGHS, or SCIP. This reduces manual labor and guarantees the shortest possible endurance run, while also enabling the consideration of various damage mechanisms that would be difficult to handle manually.

24.09.2024 16:00 Yelena Yuditsky: Domination and packing in graphs

The dominating number of a graph is the minimum size of a vertex set whose closed neighborhoods cover all the vertices of the graph. The packing number of a graph is the maximum size of a vertex set whose closed neighborhoods are disjoint. We show constant bounds on the ratio of the above two parameters for various graph classes. For example, we improve the bound for planar graphs. The result implies a constant integrality gap for the domination and packing problems. This is a joint work with Marthe Bonamy, Monika Csikos and Anna Gujgiczer.

30.07.2024 16:00 Kurt Klement Gottwald: Šoltés’s problem for the Kirchhoff index of a graph

A good vertex of a graph is a vertex whose removal doesn't change the Wiener Index of the graph. Šoltés posed the problem of finding all simple graphs with only good vertices. He found that the cycle on 11 vertices does the trick and to this day it is still the only known graph with this property. Due to the challenge of finding more examples of such graphs, the relaxed version of the problem was tackled, namely the problem of finding graphs with a large proportion of good vertices. We consider a similar problem, but instead of the shortest path distance as in the Wiener Index, we use the resistance distance and the Kirchhoff Index. Similarly to the original problem, we find only the cycle on 5 vertices to solve the full problem. We construct several families of graphs with large proportions of good vertices.

30.07.2024 16:30 Thomas Jahn: Minkowski chirality of triangles

The Minkowski asymmetry of a convex body K in R^d, i.e., the smallest dilation factor λ for which K is contained in a translate of λ(-K), is known to be at most d. The maximizers of the Minkowski symmetry are precisely the simplices, in particular those which are mirror symmetric with respect to some hyperplane. In order to quantify how mirror symmetric a given convex body K in R^d is, we may study the smallest dilation factor λ for which K is contained in a translate of some λ A_L(K) where A_L is the reflection about some j-dimensional linear subspace L of R^d. The Minkowski asymmetry is the j=0 case, and in this talk we focus on the case where d=2, j=1, and K is a triangle. We present some numerical evidence and discuss our analytical findings.

12.07.2024 14:15 Vivian Haller: Presentation of a Master's Thesis on "Development of a software tool facilitating exam staff allocation"

Assigning supervisors and correctors to exams is a recurrent task handled at the TUM-CIT Department of Mathematics. The current practice of determining a suitable allocation has several drawbacks leading to increased time consumption, which the implemented tool should help mitigate.

25.06.2024 16:00 Regina Bühler: DER operation in residential areas: Modelling coordination strategies via Linear Programming

Ongoing changes in the residential energy sector, along with the emergence of Distributed Energy Resources (DER) such as photovoltaic (PV) energy generation and battery storage, as well as newer (and potentially more flexible) energy demands like heat pumps and electric vehicle charging, have significantly increased the importance of demand response management to ensure grid stability. The goal of this thesis is to formulate a linear program to model the operation of DER technologies such as electric vehicle charging, battery energy storage, heat pumps, and thermal storages in residential households. The objective is to minimize customers' energy costs based on given energy prices and demands. Different use-case scenarios are established. In these scenarios, households can either be considered individually or as a community where households have the option to share excess energy with their neighbors in a coordinated manner. Furthermore, the scenarios are distinguished based on whether they enforce network limitations, i.e., constrain the available power a transformer substation can supply, or not. After defining the corresponding LPs for these scenarios, some necessary conditions for solutions to the problems are analyzed and proven. Numerical experiments on exemplary data sets provided by Siemens are performed using the Pyomo modeling framework and Gurobi. Key performance indicators such as substation and household load profiles, substation peak loads, and energy costs for households are evaluated. This thesis was done in cooperation with the Siemens AG.

18.06.2024 16:00 Lars Rohwedder: Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems

We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be small discrete values or more generally m-dimensional vectors of small discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by the maximum weight and m for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in 0/1, or arbitrary and m = 1. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection. This is joint work with Friedrich Eisenbrand and Karol Węgrzycki.

28.05.2024 16:00 Mia Runge: General properties of (r,D,R)-Blaschke-Santaló Diagrams in arbitrary Minkowski spaces

We study Blaschke-Santaló diagrams for the inradius, circumradius and diameter in general Minkowski spaces. Independent of the gauge, they can be described by at most five parts of boundaries. We analyse which bodies fill these bounds and for which gauges they become redundant. Furthermore, we give a complete description of the union over all these diagrams with respect to planar symmetric gauges (solving an open problem stated by Brandenberg and Gonzáles Merino in a recent paper) by providing a new inequality that tightens Bohnenblust's bound. This union is equal to the union over all diagrams with respect to intersections of triangles with their origin reflection. This is joint work with René Brandenberg and Bernardo Gonzáles Merino.

For talks not listed above please have a look at the Munich Mathematical Calendar.