Seminar in Discrete Optimization

Vortrag über die Problemstellung und deren Komplexität sowie die Entwicklung zweier Lösungsalgorithmen von Sonja Eberle im Rahmen ihrer Bachelorarbeit.

Each semester, faculties must allocate their staff members to exam supervision and correction duties. These problems were modelled as a joint mixed-integer linear program, incentivizing simultaneous allocation of staff to supervise and correct the same exam. This MILP is then modified to enable an adjustment of a given solution based on explicit assignments or exclusions of staff members. A long-term perspective that links semesters by carrying over unfulfilled duties and allows staff to work ahead was further given as a modification.

Solving Integer linear programs (ILPs) is significantly harder than finding optimal solutions for their linear relaxations which can be solved using many algorithms, most popularly the Simplex Algorithm. Depending on their structure and dimensions, the problem scales in complexity really fast. Here, cutting planes serve as an important tool to iteratively approach the integer optimal solution. Starting from a fractional optimal solution, a hyperplane (called cutting plane) is generated, that cuts off the fractional solution and eventually approaches the optimal integer solution in a few iterations. The generation of cutting planes (separation technique) and the approach of obtaining the optimal solution via the cutting planes provide good geometric insights and can often be visualised. The theoretical ideas of prominent cutting planes like the Chvátal-Gomory cuts, Lift and Project Cuts and Intersection Cuts will be described and applied on a few examples, thus visualizing the generation and approach of these cutting planes in the Optimization process. The geometrical ideas complement the theoretical framework and improve the overall intuition in generating these cutting planes.

In this talk, I will discuss two of our recent results on three-dimensional (3D) packing problems: the 3D Knapsack problem and the 3D Bin Packing problem. In both settings, we are given a collection of axis-aligned cuboids. In the Knapsack problem, each cuboid is associated with a profit, and the objective is to pack a subset of cuboids non-overlappingly into a unit cube to maximize total profit. In contrast, the Bin Packing problem seeks to pack all the cuboids using the minimum number of unit cubes (bins). Both problems are NP-hard and unlike their two-dimensional counterparts that have been extensively studied, the 3D variants have received much less attention. The previously best-known approximation ratios for 3D Knapsack and 3D Bin Packing are 7 + ε and (T_∞)^2 + ε ≈ 2.86, respectively for any constant ε > 0, where T_∞ ≈ 1.691 is the well-known Harmonic constant in Bin Packing. We provide improved approximation ratios of 139/29 + ε ≈ 4.794, and 3T_∞/2 + ε ≈ 2.54, for 3D Knapsack and 3D Bin Packing, respectively. Our key technical contribution is container packing -- a structured packing in 3D wherein all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. I shall also discuss few extensions of our techniques to related 3D packing problems.

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.

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.

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.

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.

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.

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.

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