Given a set of departments, their lengths and pairwise weights the single-row facility layout problem (SRFLP) asks for an arrangement of the departments along one side of a path such that the weighted sum of the center-to-center distances is minimized. In 2009 Amaral presented the well-known betweenness model for the SRFLP. We will strengthen his model by new cutting planes which are separated heuristically in our tests. The combination with some new construction heuristic allows us to solve instances which up to 60 departments exactly. In the second part of this talk we extend our setting of the standard SRFLP since in practice, especially in job shop production systems, there are often several departments which are of the same or a similar type and could do the same job steps. So the paths of the products and the exact transport amounts between each pair of departments, which equal the weights in the SRFLP, are not known beforehand. This motivates the simultaneous assignment of the tasks to the departments without exceeding the capacity of each of them as well as the determination of an SRFLP layout in order to minimize the overall transportation costs. We present two new models for this extended problem. Computational results show that a pure 0-1 modelling approach based on the betweenness model combined with symmetry-breaking constraints works best.

In this paper, we explore envy-free pricing problems with unit-demand that naturally arise when considering revenue maximization strategies for venues like planetaria. We are given a set of customers, each with a preference for one specific seat within the planetarium's layout. For any seat other than their preferred one, a customer's valuation decreases with the distance from their preferred seat. The planetarium operator decides on the prices for all seats within the layout and aims to maximize revenue by pricing seats and allocating them to customers in an envy-free and price non-discriminatory manner. This means that every assigned customer receives a seat that provides the highest possible utility for given non-discriminatory prices, while all unassigned customers do not desire any available seat. We examine a continuous variant where customers can be placed arbitrarily within the Planetarium's layout, without being limited by seat size constraints. In the discrete counterpart, seats layout correspond to typical seat configurations in cinemas and theaters. For the special case of the continuous variant of the problem, wherein all customers have a mutual preferred seat, we introduce a dynamic programming algorithm solving the problem in polynomial time. For the discrete variant of the problem, we extend the dynamic programming approach, solving the problem in pseudo-polynomial time. In the final part of our study, we unravel an intriguing connection between the arrangement of seats and principles of lattice theory.

We present a combinatorial algorithm for determining a maximum packing of hypertrees in a capacitated hypergraph.
This extends algorithms for packing spanning trees in graphs.
It gives an algorithmic proof of a theorem by Frank et al. This allows the extension of several algorithms developed for graphs to hypergraphs, for the k-cut problem.

Let $G=(V,E)$ be a multigraph with a set $T$ of terminals. A path in $G$ is called a $T$-path if
its ends are distinct vertices in $T$ and no internal vertices belong to $T$.
In 1978, Mader showed a characterization of the maximum number of edge-disjoint $T$-paths.

In this talk, we provide a combinatorial, deterministic algorithm for finding the maximum number of
edge-disjoint $T$-paths. The algorithm adopts an augmenting path approach. More specifically,
we utilize a new concept of short augmenting walks in auxiliary labeled graphs to capture
a possible augmentation of the number of edge-disjoint $T$-paths. To design a search procedure for
a short augmenting walk, we introduce blossoms analogously to the matching algorithm of Edmonds (1965).
When the search procedure terminates without finding a short augmenting walk, the algorithm provides
a certificate for the optimality of the current edge-disjoint $T$-paths. From this certificate,
one can obtain the Edmonds--Gallai type decomposition introduced by Seb\H{o} and Szeg\H{o} (2004).
The algorithm runs in $O(|E|^2)$ time, which is much faster than
the best known deterministic algorithm based on a reduction to linear matroid parity.

We also present a strongly polynomial algorithm for the maximum integer free multiflow problem,
which asks for a nonnegative integer combination of $T$-paths maximizing the sum of the coefficients
subject to capacity constraints on the edges.