Seminar in Discrete Optimization

Upcoming talks

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.

Previous talks

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.

09.04.2024 16:00 Lehilton Lelis Chaves Pedrosa: A parameterized approximation algorithm for the Multiple Allocation k-Hub Center

In the Multiple Allocation k-Hub Center (MAkHC), we are given a connected edge-weighted graph G, sets of clients C and hub locations H, where V (G) = C ∪ H, a set of demands D ⊆ C 2 and a positive integer k. A solution is a set of hubs H ⊆ H of size k such that every demand (a, b) is satisfied by a path starting in a, going through some vertex of H, and ending in b. The objective is to minimize the largest length of a path. We show that finding a (3 − ϵ)-approximation is NP-hard already for planar graphs. For arbitrary graphs, the approximation lower bound holds even if we parameterize by k and the value r of an optimal solution. An exact FPT algorithm is also unlikely when the parameter combines k and various graph widths, including pathwidth. To confront these barriers, we give a (2 + ϵ)-approximation algorithm parameterized by treewidth, and, as a byproduct, for unweighted planar graphs, we give a (2 + ϵ)-approximation algorithm parameterized by k and r. Compared to classical location problems, computing the length of a path depends on non-local decisions. This turns standard dynamic programming algorithms impractical, thus we introduce new ideas so that our algorithm approximates the length using only local information.

05.03.2024 16:00 Maximilian Gläser: Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation

We investigate linear programming based branch-and-bound using general disjunctions, also known as stabbing planes and derive the first sub-exponential lower bound (i.e., 2^{L^\omega(1)}) in the encoding length L of the integer program for the size of a general branch-and-bound tree. In fact, this is even the first super-linear bound. This is achieved by showing that general branch-and-bound admits quasi-feasible monotone real interpolation. Specialized to a certain infeasible integer program whose infeasibility expresses that no graph can have both a k-coloring and a (k+1)-clique, this property states that any branch-and-bound tree for this program can be turned into a monotone real circuit of similar size which distinguishes between graphs with a k-coloring and graphs with a (k+1)-clique. Thus, we can utilize known lower-bounds for such circuits. Using Hrubeš' and Pudlák's notion of infeasibility certificates, one can show that certain random CNFs are sub-exponentially hard to refute for branch-and-bound with high probability via the same technique. This is joint work with Marc Pfetsch.

27.02.2024 16:00 Marin Varivoda: The Banach-Mazur distance between the cube and the cross-polytope in dimensions three and four

The Banach-Mazur distance is a well-established notion of convex geometry with numerous important applications in the fields like discrete geometry or local theory of Banach spaces. This notion has already been extensively studied by many different authors, but the vast majority of established results are of the asymptotic nature. The non-asymptotic properties of Banach-Mazur distance seem to be quite elusive and even in very small dimensions they are surprisingly difficult to establish. Actually there are rather few situations in which the Banach-Mazur distance between a pair of convex bodies was determined precisely. One example illustrating this difficulty is the case of the cube and the cross-polytope, as their Banach-Mazur distance was known only in the planar case. In this talk we prove that the distance between the cube and the cross-polytope is equal to 9/5 in the dimension three and it is equal to 2 in dimension four.

27.02.2024 16:45 Tomasz Kobos: Planar convex bodies equidistant to all symmetric convex bodies

The n-dimensional simplex is a convex body well-known for its numerous remarkable features and it was studied extensively also from the point of view of the Banach-Mazur distance. Our starting point is the following well-known and interesting property: the n-dimensional simplex is equidistant (in the Banach-Mazur distance) to all symmetric convex bodies with the distance equal to n. Moreover, it is known the simplex is the unique convex body with this property. It is therefore natural to ask if the simplex is the unique convex body that is equidistant to all symmetric convex bodies, but not necessarily with the distance equal to n. We answer this question negatively in the planar case. For all 7/4 < r < 2 we provide a general construction of a family of convex bodies K, which are with the distance r to every symmetric convex body. It should be noted that this distance r coincides with the asymmetry constant of K and the construction is based on some basic properties of the asymmetry constant.

23.01.2024 16:00 Gennadiy Averkov: Plücker-type inequalities for mixed areas and intersection numbers of curve arrangements

Any collection of n compact convex planar sets K_1,…,K_n defines a vector of n over 2 mixed areas V(K_i, K_j) for 1≤i Quelle

09.01.2024 16:00 Florian Grundbacher: p-Means of Convex Bodies and a New Suggestion for the Geometric Mean of Convex Bodies

In light of the log-Brunn-Minkowski conjecture, various attempts have been made to define the geometric means of convex bodies. Many of these constructions are fairly complex and/or fail to satisfy some natural properties one would expect of such a mean. To improve our understanding of potential geometric mean definitions, we study the closely related p-means of convex bodies, with the usual definition extended to two series ranging over all p in [-∞,∞]. We characterize their equality cases and obtain (in almost all instances tight) inequalities that quantify how well these means approximate each other. Based on our findings, we propose a fairly simple definition of the geometric mean that satisfies the properties considered in recent literature, and discuss potential axiomatic characterizations. Finally, we conclude that some of these properties are incompatible with approaches to proof the log-Brunn-Minkowski conjecture via geometric means.

08.01.2024 17:00 Steffen Borgwardt: Optimal Sites for Least-Squares Assignments

Least-squares assignments are a common way to partition a data set in clustering applications. While the combined choice of best clusters and representative sites is a known hard problem, linear programming methods and polyhedral theory provide insight into closely related tasks. We show that it is efficient to decide whether a given clustering can be represented as a least-squares assignment, and extend the related algorithm to arrive at soft-margin multiclass support vector machines. Further, we connect the search for optimal sites for a given clustering to volume computations for normal cones of an associated vertex in a certain polyhedron. This leads to new measures for the robustness of clusterings and explains why popular algorithms like k-means work well in practice.

19.12.2023 16:00 Katja Ettmayr: A (3 + ε)-approximation algorithm for the minimum sum of radii problem with outliers

Clustering is a fundamental problem setting with applications in many different areas. For a given set of points in a metric space and an integer k, we seek to partition the given points into k clusters. For each computed cluster, one typically defines one point as the center of the cluster. A natural objective is to minimize the sum of the cluster center’s radii, where we assign the smallest radius r to each center such that each point in the cluster is at a distance of at most r from the center. The best-known polynomial time approximation ratio for this problem is 3.389. In the setting with outliers, i.e., we are given an integer m and allow up to m points that are not in any cluster, the best-known approximation factor is 12.365. In this paper, we improve both approximation ratios to 3 + ε. Our algorithms are primal-dual algorithms that use fundamentally new ideas to compute solutions and to guarantee the claimed approximation ratios. For example, we replace the classical binary search to find the best value of a Lagrangian multiplier λ by a primal-dual routine in which λ is a variable that is raised. Also, we show that for each connected component due to almost tight dual constraints, we can find one single cluster that covers all its points and we bound its cost via a new primal-dual analysis. We remark that our approximation factor of 3 + ε is a natural limit for the known approaches in the literature.

12.12.2023 16:00 Alexander Armbruster: Simpler constant factor approximation algorithms for weighted flow time -- now for any p-norm

A prominent problem in scheduling theory is the weighted flow time problem on one machine. We are given a machine and a set of jobs, each of them characterized by a processing time, a release time, and a weight. The goal is to find a (possibly preemptive) schedule for the jobs in order to minimize the sum of the weighted flow times, where the flow time of a job is the time between its release time and its completion time. It had been a longstanding important open question to find a polynomial time O(1)-approximation algorithm for the problem and this was resolved in a recent line of work. These algorithms are quite complicated and involve for example a reduction to (geometric) covering problems, dynamic programs to solve those, and LP-rounding methods to reduce the running time to a polynomial in the input size. In this paper, we present a much simpler (6+ϵ)-approximation algorithm for the problem that does not use any of these reductions, but which works on the input jobs directly. It even generalizes directly to an O(1)-approximation algorithm for minimizing the p-norm of the jobs' flow times, for any 0

1 only a pseudopolynomial time O(1)-approximation algorithm was known for this variant, and no algorithm for p<1. For the same objective function, we present a very simple QPTAS for the setting of constantly many unrelated machines for 0


10.11.2023 15:00 Lola Bermes: Integer programming methods for the Student Course Matching Problem

We study many-to-one matching problems for assigning a set of students to a set of courses according to their preference lists in which they rank the agents from the other set. The agents can also rate several agents of the other set equally or exclude them. Our goal is to find a stable matching that maximizes students’ satisfaction using Integer Programming (IP) methods. The flexibility of these methods becomes apparent by introducing additional conditions on the type of students and/or on the minimum number of students that must attend a course for it to be offered.

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