Friday@Noon – Bavarian Workshop on Optimization brings together Bavaria-based researchers working on various topics of mathematical optimization, focusing on finite dimensional optimization. After previous events in Augsburg, Nuremberg and Munich, we are looking forward to hosting Friday@Noon on June 23rd, 2023, in Bayreuth.
University of Bayreuth, Building NW III
Schedule (June 23rd, 2023)
- 12:00-13:00 Get TogetherEinklappen
With coffee, tea, soft drinks and finger food
- 13:00-14:00 Big picture talk by Ágnes Cseh (U Bayreuth): “Fair player allocation at chess tournaments”Einklappen
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.
- 14:00-14:30 Contributed talk by Adrian Göß (FAU): “Norm-induced Cuts: Optimization with Lipschitzian Black-box Functions”Einklappen
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
- 14:30-15:30 Big picture talk by Elisabeth Gaar (U Augsburg): “Conic Programming meets Bilevel Programming”Einklappen
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ış.
- 15:30-16:00 Coffee breakEinklappen
With coffee, tea, soft drinks and cake
- 16:00-16:30 Contributed talk by Moritz Buchem (TUM): “Additive approximation schemes for load balancing problems”Einklappen
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.
- 16:30-17:30 Big picture talk by Tobias Harks (U Passau): “Dynamic Network Equilibrium Flows”Einklappen
I will give an overview on the mathematical theory of dynamic network equilibrium flows and present some new results for side-constrained dynamic equilibria.
- 17:30-18:00 Contributed talk by Philipp Hausenblas (UniBw M): “Mathematical models for manpower planning in the public sector”Einklappen
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.
- 18:30 Joint dinnerEinklappen
At Gasthof Schindler (at your own expense)
Please send an email to Sonja Strobel by June 12th, 9 a.m., for registering to the workshop. For organizational purposes, please indicate in your registration, in case you
- will arrive after 13:00 or
- will not participate in the joint dinner.
If you are interested in sharing your research in one of the talks, Ágnes Cseh will be pleased to receive some details, i.e. a title for your talk. We are looking forward to your contributions!
There is no conference fee.
The get together and all talks will take place in building NW III (see the map below), located in the main campus of the University of Bayreuth.
The closest bus stop is “Geowissenschaften” and can be reached from the central railway station Bayreuth Hbf via line 316 or from the central bus stop ZOH via lines 304 and 306 (further details may be found on the VGN-website).
The joint dinner will be in Gasthof Schindler, which is very close to the central railway station. Details on the transfer by bus (on your own expense) can be found on the VGN-website.
Wir brauchen Ihr EinverständnisUm aktuelle Videos, Karten oder Fremdinhalte der UNI Bayreuth einbinden zu können, nutzen wir die Services von Drittanbietern. Diese sammeln unter Umständen Daten zu Ihren Aktivitäten. Unter dem Punkt "Mehr Informationen" finden Sie weitere Details.
For further questions please contact Jörg Rambau (chairholder) or Sonja Strobel (secretary).