Seminar in Discrete Optimization

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.

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).

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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