Friday@Noon 2023

With coffee, tea, soft drinks and finger food

The International Chess Federation (FIDE) imposes a voluminous and complex set of player pairing criteria in Swiss-system chess tournaments and endorses computer programs that are able to calculate the prescribed pairings. The purpose of these formalities is to ensure that players are paired fairly during the tournament and that the final ranking corresponds to the players' true strength order. We present experimental work on testing whether the current system is indeed as fair as possible and investigate the chances of gaming the system from the point of view of a player.

Joint work with Pascal Führlich and Pascal Lenzner.

Optimal control problems usually involve constraints which model physical states and their possible transitions. These are represented by ordinary or partial differential equations (ODEs/PDEs) which add a component of infinite dimension to the problem.
In recent literature, one method to simulate such ODEs/PDEs are physics-informed neural networks. Typically, neural networks are highly non-linear which makes their addition to optimization problems challenging. Hence, we leverage their often available Lipschitz property on a compact domain. The respective Lipschitz constants have to be computed only once and are accessible thereafter.

We present a method that, based on this property, iteratively adds cuts involving the violation of the constraints by the current incumbent and the Lipschitz constant. Hereby, the “shape” of a cut depends on the norm used. We prove the correctness of the method by showing that it either returns an optimal solution when terminating
or creates a sequence with optimal accumulation points. This is complemented by a discussion about the termination in the infeasible case, as well as an analysis of the problem complexity. For the analysis, we show that the lower and upper iteration bound asymptotically coincide when the relative approximation error goes to zero. In the end, we visualize the method on a small example based on a two-dimensional non-convex optimization problem, as well as stress the necessity of having a globally optimal oracle for the sub-problems by another example

We start by some basics of conic optimization and in particular semidefinite programming, which is a generalization of linear programming, where instead of a vector of variables that needs to be non-negative, one has a matrix of variables that is constrained to be positive semidefinite. Furthermore, we discuss some foundations of bilevel programming, a subfield of mathematical optimization that tackles optimization problems for which the feasible region is defined by optimal solutions of another optimization problem, i.e., optimization problems that have two levels.

We utilize this knowledge by for studying a class of integer bilevel programs with conic constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a conic-programming-based cut-generating procedure. Using these DCs, we propose a branch-and-cut algorithm for the problem class we study, and a cutting-plane method for the problem variant with only binary variables. This is based on joint work with Jon Lee, Ivana Ljubić, Markus Sinnl and Kübra Tanınmış.

With coffee, tea, soft drinks and cake

We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most εh for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = pmax, the maximum processing time of the jobs.

Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most εpmax.

This is joint work with Lars Rohwedder, Tjark Vredeveld and Andreas Wiese.

I will give an overview on the mathematical theory of dynamic network equilibrium flows and present some new results for side-constrained dynamic equilibria.

In today's constantly changing demographic and social conditions, human resources planning in large companies is subject to constant challenges. The targeted control of influencing variables in personnel planning while simultaneously taking into account the causal relationships that occur and the existing framework conditions is complex, and at the same time an essential component of medium- to long-term planning of corporate development.  Especially the public service with its clearly defined promotion guidelines and medium-term defined requirements offers the possibility to mathematically model and optimize occurring processes. For this purpose, we developed mathematical models and solution algorithms that suggest medium-term transitions of the existing personnel structure into future target structures. At the same time, our methods take into account a wide variety of requirements for the personnel development to be undertaken and map the underlying personnel body on an individual basis in order to account for the many special cases of the personnel body.  The resulting high-dimensional optimization problems are difficult to solve with standard methods of mathematical optimization due to their size. By using selected techniques of combinatorial and integer optimization, our methods are nevertheless able to solve realistic problem sizes and to generate control proposals for the transition of the personnel structure.

At Gasthof Schindler (at your own expense)