CAO

Consolidation-based carriers transport shipments that are small compared to the capacity of the used vehicles. To enable cost-effective operations, they need to consolidate shipments. The Service Network Design Problem consists of determining the paths of shipments in the carriers network as well as the timing of the dispatches. Boland et al. (2017) proposed the Dynamic Discretization Discovery (DDD) framework to solve large scale instances of this problem to optimality by iteratively solving and refining a relaxed time-discretized model. We present a new relaxation for their DDD framework that uses an arc-based discretization of time and leads to significantly smaller models that can be solved faster. We also adapt some recent theoretical and algorithmic advances from the DDD literature to our relaxation. Computational experiments demonstrate that a DDD implementation based on our relaxation leads to models that are about five times smaller and solved twice as fast as those of a comparable node-based discretization approach for a hard set of instances from the literature.

We consider a greedy algorithm for the submodular cover problem that corrects partial solutions whenever it detected that a previous decision turned out to be non-optimal. This algorithm uses one-to-many exchanges (a generalization of one-to-one exchanges of matroids) to improve a solution that contains redundant elements, which do not yield additional coverage.
We investigate on which types of submodular cover problems this greedy algorithm computes an optimal solution and attempt to build a theory around those submodular functions that behave well on the aforementioned one-to-many exchanges. This is joint work with Waldo Gálvez, Britta Peis, Victor Verdugo, and José Verschae.

Algorithms for solving the quickest transshipment problem have advanced substantially since Hoppe and Tardos first solved the problem in polynomial time. However, most of these improvements come at the expense of fractional solutions. We replace two central subroutines in the algorithm with methods that require vastly fewer minimizations of submodular functions. This improves the state-of-the-art runtime for computing integral quickest transshipments from Õ(m⁴k¹⁵) down to Õ(m²k⁵+m⁴k²), where k is the number of terminals and m is the number of arcs.

We study single-source capacitated facility location problems with customer preferences (CFLP-CP). These problems consist in solving an instance of the single-source capacitated facility location problem (CFLP) in which customers have individual preferences regarding the facilities and have to be served at one of their most preferred open facilities. While the CFLP and CFLP-CP are strongly NP-complete, preference constraints imply interesting combinatorial structures rendering some previously NP-complete special cases of the CFLP easy to solve. We strengthen the well-known cover inequalities by utilising structures that arise from the synergy of capacities and preferences. We evaluate the impact of these inequalities for two preference types in a computational study. Our results show a clear positive impact, in particular, when preferences are defined by assignment costs.

Prominent opinion formation models such as the one by Friedkin and Johnsen (FJ) concentrate on the effects of peer pressure on public opinions. In practice, opinion formation is also based on information about the state of the world and persuasion efforts.
In this talk, we will present an approach of Bayesian persuasion in the FJ model. There is an unknown state of the world that influences the internal beliefs of n agents. A sender S can (partially) reveal information about the state to all agents. The agents update their internal beliefs, and an equilibrium of public opinions emerges. We propose algorithms for the sender to reveal information in order to optimize various aspects of the emerging equilibrium.
For many natural sender objectives, we will show that there are simple optimal strategies. After that, the focus will be on a general class of range-based objectives based on desired opinion ranges for each agent. We will present efficient algorithms in several cases, e.g., when the matrix of internal beliefs in all states has constant rank, or when there is only a polynomial number of range combinations that lead to positive value for S. This generalizes, e.g., instances with a constant number of states and/or agents, or instances with a logarithmic number of ranges. Finally, we will show for the general case that subadditive range-based objectives allow a simple n-approximation, while obtaining an n^{1-ε}-approximation is NP-hard, for any constant ε > 0, even for additive ones. This is joint work with Martin Hoefer and Tolga Tel.

In the Travelling Salesman Problem, every vertex of an edge-weighted graph has to be visited by an agent who traverses the edges of the graph. In this problem, it is usually assumed that the costs of each edge are given in advance, making it computationally hard but possible to calculate an optimal tour for the agent.
In the Graph Exploration Problem, every vertex of a given graph must be visited as well, but here the graph is not known in the beginning. At every point, an algorithm only knows about the already visited vertices and their neighbors. Both however are not necessarily realistic settings: Usually the structure of the graph (for example underlying road network) is known in advance, but the details are not. One usually has a prediction of how long it takes to traverse through a particular road, but due to road conditions or imprecise maps, one might realize that a road will take slightly longer than expected when arriving at it. To deal with those deviations, it is natural to assume that an agent can adapt to the situation: When realizing that taking a particular road is more expensive than expected, recalculating the tour and taking another road instead is possible.
In a sense, this setting lies in between the offline travelling salesman problem, and the online problem of graph exploration, as it allows some computation at the beginning, but remains an online problem during traversal through the graph. We analyze the competitive ratio of this problem based on the perturbation factor a of the edge weights. For general graphs, we show that for realistic factors a smaller than 2, no strategy achieves a competitive ratio better than a, which can be matched by a simple algorithm. In addition, we will also have a look at restricted graph classes like complete graphs with uniform announced edge weights. Here, we present a matching lower bound as well, proving that the strategy for those graph classes is the best possible. A preliminary version of those results can be found on arxiv with the name "Graph Exploration with Edge Weight Estimates" (together with Ralf Klasing and Émile Naquin).

We consider the problem of planning the out-of-hours service for pharmacies, which ensures a continuous supply of pharmaceuticals. The problem consists in assigning 24-hour shifts to a subset of pharmacies on each day such that an appropriate supply is guaranteed while the burden on pharmacists is minimized. Using a model developed in collaboration with the Chamber of Pharmacists North Rhine, we compute plans minimizing the total number of shifts. The computed plans save many shifts compared to the real plan of the Chamber of Pharmacists North Rhine, but they exhibit an unfair concentration of burden to the disadvantage of some pharmacies. We propose a strategy for integrating fairness into the planning based on a lexicographic fairness criterion. Using theoretical insights, we compute out-of-hours plans that are almost maximally fair while also assigning only a few more shifts.

We study multi-follower bilevel optimization problems with binary linking variables where the second level consists of many independent integer-constrained subproblems. This problem class not only generalizes many classical interdiction problems but also arises naturally in many network design problems where the second-level subproblems involve complex routing decisions of the actors involved. We propose a novel branch-and-cut decomposition method that starts by solving the first level and then iteratively generates second-level feasibility and optimality cuts that are obtained by solving a slightly adjusted second-level problem. Compared to many other existing solution methods, we do not rely on solving the HPR of the bilevel problem but fully project out the second level, resulting in significant computational advantages when the second-level problem is very large or possesses a weak LP relaxation. Also, our approach can be fully automated within a MIP solver, making it very easy to apply for those who do not want to design problem-tailored algorithms for their bilevel problem. Computational results for a bilevel network design problem demonstrate that our approach efficiently solves instances with hundreds of subproblems in a few minutes, significantly outperforming the Benders-like decomposition from the literature on challenging instances.

In the Eisenberg-Noe model, a model for debt between financial institutions and quantifying systemic risk, there are n banks represented by nodes in a directed graph. Directed edges represent debt claims, and edge weights are liabilities. Each bank can use incoming payments to clear its debt. Moreover, each bank has a non-negative amount of external assets, which can also be used for payment of claims. With this talk, I will convey basic intuitions for problems in the model, specifically claims trades. In claims trades, there is a bank v in distress and a trading partner w. The latter is taking over some claims of v and in return giving liquidity to v. The idea is to rescue v (or mitigate contagion effects from v's insolvency). We focus on the impact of trading claims fractionally, i.e. when v and w can agree to trade only part of a claim. This is joint work with Martin Hoefer and Lisa Wilhelmi.

Multi-stage decision-making under uncertainty, where decisions are taken under sequentially revealing uncertain problem parameters, is often essential to faithfully model managerial problems. Given the significant computational challenges involved, these problems are typically solved approximately. This short note introduces an algorithmic framework that revisits a popular approximation scheme for multi-stage stochastic programs by Georghiou et al. (2015) and improves upon it to deliver superior policies in the stochastic setting, as well as extend its applicability to robust optimization and a contemporary Wasserstein-based data-driven setting. We demonstrate how the policies of our framework can be computed efficiently, and we present numerical experiments that highlight the benefits of our method.

Assigning patients to rooms is a fundamental task in hospitals and, especially, within wards. This so-called patient-to-room assignment problem (PRA) has gained more and more attention in the last few years and many heuristics have been proposed with a large variety of different practical constraints reflecting different settings in hospitals. Classical objectives are avoiding patient transfers between rooms, respecting single-room requests, or choosing patients of similar age as roommates. Apart from age difference, there are many other potential criteria for determining the roommate suitability. In this talk, we show how a feasible patient-to-room assignment with optimal roommate fit can be computed efficiently.

A common way to present graphs in an online fashion is by presenting them vertex-wise, together with all the edges that are induced by the already presented vertices. An online algorithm therefore needs to decide what he does with the current input at a defined time, usually after a vertex got presented or some other property is fulfilled. In this talk we will focus on the Online Feedback Vertex Set Problem, where a graph gets presented vertex-wise, and the online algorithm needs to delete a vertex as soon as he sees an circle. If the circle got destroyed, the instance continues. We will show that the Online Feedbeck Vertex Set has an approximation ratio between four and five (also called competitive ratio). This talk bases on a chapter of "Delaying Decisions and reservation costs" of last year's COCOON.

We introduce a novel optimization problem inspired by the pricing of public transport tickets. We assume a straightforward pricing model where each customer pays a fixed price for each fare zone traversed. Additionally, based on empirical studies, we assume that customers have a preferred route and will opt for alternative transportation methods if their individual cost ceilings are exceeded. Formally, the problem can be described as follows: Given an undirected graph G=(V,E) and k commodities, where each commodity represents a group of customers with identical routes and cost ceilings, the objective is to partition the graph into fare zones such that the provider's revenue is maximized. The structure of the profit function renders the problem algorithmically intriguing. In the trivial solution with a single fare zone, revenue is collected for all commodities. However, if a commodity crosses too many fare zones, the associated profit drops to zero as customers choose alternative transportation options. We demonstrate that this problem is NP-hard for nearly every non-trivial graph class. Specifically, it is NP-hard even on paths and APX-hard on stars. Currently, we are exploring complementary positive complexity results through various approaches, including a non-trivial linear programming (LP) formulation.

Graph burning is a discrete-time process mimicking the spread of fire in graphs and was introduced to model the spread of influence in networks. In every step existing fires spread to neighboring vertices and a new vertex is set ablaze. Its associated graph parameter, the burning number, denotes the minimal number of steps needed to fully burn a graph. We explore the complexity and mathematical programming formulations of graph burning and its variations.

To reduce emissions, traffic, and noise, municipalities and governments are imposing fees and toll schemes to logistic companies for accessing particular roads. Because such measures increase delivery costs, transportation companies have to consider them when planning routes. In this talk, we address the edge set vehicle routing problem with time windows (ESVRPTW) initially introduced by Reinhardt et al. (2016). The ESVRPTW is a generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges. We propose an improved formulation for the ESVRPTW, and new variable fixing techniques and valid inequalities. We introduce a new variant of the ESVRPTW to represent urban contexts in which waiting at customers for the opening of their time windows is not allowed. To solve these problems, we present a matheuristic, called MS-LBM, that consists of a multi-start local descent framework that uses a local branching scheme. In addition to its flexibility in solving all ESVRPTW variants addressed in this talk, MS-LBM provides high-quality solutions faster than a commercial optimization solver and finds new best-known solutions. With an extensive computational study, we derive insights into how allowing waiting at customers affects the edge-set activation and routing decisions depending on the type of infrastructure for which fixed costs must be paid.

Providing affordable healthcare is a major societal challenge, both in Germany and abroad. In this context, hospitals play a central role, with beds being one critical ressource therein. Efficiently managing beds serves multiple objectives: it can both help save "non-value-added-time", i.e. by avoiding unecessary reassignments, and generate revenue by ensuring private room entitlements are met. However, even in large hospitals such as the RWTH Aachen University Hospital, bed management is currently done by hand. This talk presents binary integer programming formulations that can exactly solve bedmanagement, i.e. patient-to-room assignment problems (PRA) in (fractions of) seconds for even the largest real-world instances. This is novel insofar as that the current state of the art either relies on heuristic methods or makes very strong assumptions before employing integer programming. The proposed work does neither and is able to capture all relevant special cases through simple model extensions. The aforementioned results are made possible through a combination of combinatorial insights into possible objective values, and restrictions of the solution space in terms of possible transfers. Combining both allows us to solve a sequence of heuristic problem variations while also proving optimality combinatorically. The results are verified through a computational study, showcasing that we achieve almost optimal results for single room entitlements and a reduction of transfers by an order of magnitude compared to real-world data, even in the context of a dynamic model with uncertain patient arrivals.

Many NP-hard or W[1]-hard problems are (fixed-parameter) tractable when restricted to special graph classes, especially sparse ones like planar graphs, graphs of bounded treewidth or even graph classes excluding minors. This is prominently captured by powerful meta-theorems like Courcelle's theorem or the result of Grohe, Kreutzer and Siebertz: Every problem expressible in first-order logic is fixed-parameter tractable on nowhere dense classes of graphs. Classes of bounded expansion and those classes generalize many familiar classes of sparse graphs and are in some sense the most general robust notion of sparsity. For example, this result implies that the k-Dominating Set Problem has an f(k) n^(1+o(1)) algorithm on all nowhere dense classes. However, it does not cover problems that use counting in some sense as first-order logic is not able to count. An example is the Partial Dominating Set Problem which asks, given integers k and t, for a set of k vertices that dominate t vertices. Or the Partial Red-Blue Dominating Set problem which asks to find k vertices that dominate t_r of the red and t_b of the blue vertices. Those problems can be expressed in the counting logic FO(>0) which augments first-order logic with a special kind of counting quantifiers. Our contribution is a model-checking algorithm for formulas of the form "∃ = ∃x1...∃xℓ P(#y φ_1(x1...xℓ,y), ..., #y φ_r(x1...xℓ,y))", where P is some predicate on numbers and φ_i are first-order formulas. The running time is f(|φ|)n^(r+1) polylog(n) on graph classes of bounded expansion. We also provide a lower bound under SETH which is tight up to an almost linear factor. In this talk, I will present the notion of sparsity in graphs, especially classes of bounded expansion, some known meta-theorems for logics with and without counting, and our contribution (without any proofs!).

The b-matching problem is a well-known variant of the famous matching problem with many applications. Given an undirected graph, each vertex v has to be matched b(v) times and edges can be used multiple times. It is also solvable in polynomial time. Applications include matching workers or produce to customers, as in the Chinese Postman Problem, but it is also used in Heuristics for other well-known Problems like TSP. In theory, the capacity b(v) is fixed and known for each vertex. However, in practice, the capacity is often subject to uncertainties, as workers get sick or customers drop out. In this talk, we present a new variant of the b-matching problem under uncertain capacity ensuring robustness, called the robust directed b-matching problem. An instance of the problem consists of a directed graph with costs on each arc and uncertain capacities on each vertex. The problem has two stages: first, we set the sum of the matching over all outgoing arcs for each vertex. Second, after realization of the uncertain capacity, we set the b-matching minimizing the costs. We examine the problem's complexity on different graph classes and show NP-hardness even on directed trees, which are directed acycle graphs whose underlying undirected graph is a tree. We also showcase the influence of requiring a perfect matching, where each vertex has to be matched exactly b(v) times, which turns out to make the problem easier on some graph classes. This is joint work with Arie Koster.

We propose a new mathematical approach for designing a counting zone tariff system in public transportation. The goal is to maximize revenue while considering spatial patterns like rings or stripes in the resulting zones. The approach assumes discrete zone prices, trip numbers influenced by prices, and passengers choosing the time-shortest path. We present a Lagrangian approximation method, scaling linearly with the number of stops. Extensive numerical studies evaluate network and demand structures. The approach achieves optimal solutions for instances with 121 stops within a few hours. Instances with over 500 stops can be solved in under an hour. Findings show that revenue increases with network connectivity, spatial patterns may slightly decrease revenue (stripes less than rings), and time-shortest paths mostly always come at minimum cost. A case study of the San Francisco Bay Area with 1,400 stops demonstrates the approach's practicality. Enforcing a stripe pattern results in more balanced zone areas but sacrifices 3-5% of optimal revenue compared to no pattern.

We present a logistics planning problem for prepositioning relief commodities in preparation for an impending hurricane landfall. We assume that the hurricane's intensity, landfall time, and location evolve according to a Markov chain and model the problem as a multistage stochastic programming (MSP) problem with random number of stages. Our work is the first to introduce an MSP model with a random number of stages for the case where the stochastic process is stage-wise dependent. We benchmark the performance of the MSP model with several alternative decision policies, based on two-stage stochastic programming models, including a static policy, a rolling-horizon policy, and a decision tree-based policy. Our numerical results provide key insights into the value of MSP models in hurricane disaster relief logistics planning.

Determining prices on a market where a seller aims to sell a finite set of indivisible distinguishable goods to a finite set of buyers is a well-studied problem with countless applications. Prices on the items are called Walrasian (equilibrium) prices if they admit an envy-free allocation of items to the buyers such that all items with positive prices are sold. Such Walrasian prices are guaranteed to exist if the buyers' valuations are gross substitute, a concept introduced by Kelso and Crawford. A very natural process to determine prices of the goods is an ascending auction, where prices are raised step by step on overdemanded sets. Provided that all buyers have gross substitute valuations, Gul and Stacchetti have shown that an ascending auction which iteratively raises prices on inclusion-wise minimal maximal overdemanded sets terminates with the (unique) componentwise minimal Walrasian price vector. It is by now known that an inclusion-wise minimal maximal overdemanded set can be computed in polynomial time with tools from discrete convexity. We present a simple and purely combinatorial polynomial time algorithm for their computation: we show that the desired overdemanded sets can be computed using the exchange graph of the classical matroid partitioning algorithm. Moreover, we show that for gross substitute valuations the component-wise minimal prices that admit an envy-free allocation are the same as the minimal Walrasian prices. This enables us to show a very natural monotonicity of minimal Walrasian prices with respect to changes in supply and demand. This is joint work with Britta Peis, Niklas Rieken, Laura Vargas Koch and László A. Végh.

An online algorithm is a special kind of optimization algorithm that is required to take immediate and irrevocable decisions given only a prefix of an instance. In the design of such algorithms, one usually interested in bounding the worst-case ratio of the algorithm's solution in relation to the optimal solution on the same instance, which is commonly called the competitive ratio of an algorithm. In this talk, we explore two novel approaches of modifying the classical online model to better model real-life optimization. The first is that of so-called reservations, in which elements of the instance may be "made offline" for a price. The second model is that of predictions, in which the algorithm is given information about the upcoming instance. This information may however be flawed, up to a constant or multiplicative error. We discuss both models using the Online Simple Knapsack Problem as an example. This is joint work with Hans-Joachim Böckenhauer, Elisabet Burjons, Felix Frei, Matthias Gehnen, Juraj Hromkovic and Peter Rossmanith