TY - GEN A1 - Breugem, Thomas A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Schulz, Christof T1 - A Three-Phase Heuristic for Cyclic Crew Rostering with Fairness Requirements N2 - In this paper, we consider the Cyclic Crew Rostering Problem with Fairness Requirements (CCRP-FR). In this problem, attractive cyclic rosters have to be constructed for groups of employees, considering multiple, a priori determined, fairness levels. The attractiveness follows from the structure of the rosters (e.g., sufficient rest times and variation in work), whereas fairness is based on the work allocation among the different roster groups. We propose a three-phase heuristic for the CCRP-FR, which combines the strength of column generation techniques with a large-scale neighborhood search algorithm. The design of the heuristic assures that good solutions for all fairness levels are obtained quickly, and can still be further improved if additional running time is available. We evaluate the performance of the algorithm using real-world data from Netherlands Railways, and show that the heuristic finds close to optimal solutions for many of the considered instances. In particular, we show that the heuristic is able to quickly find major improvements upon the current sequential practice: For most instances, the heuristic is able to increase the attractiveness by at least 20% in just a few minutes. T3 - ZIB-Report - 19-43 KW - Crew Planning KW - Column Generation KW - Variable-Depth Neighborhood Search Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74297 SN - 1438-0064 ER - TY - THES A1 - Beckenbach, Isabel T1 - Matchings and Flows in Hypergraphs N2 - In this dissertation, we study matchings and flows in hypergraphs using combinatorial methods. These two problems are among the best studied in the field of combinatorial optimization. As hypergraphs are a very general concept, not many results on graphs can be generalized to arbitrary hypergraphs. Therefore, we consider special classes of hypergraphs, which admit more structure, to transfer results from graph theory to hypergraph theory. In Chapter 2, we investigate the perfect matching problem on different classes of hypergraphs generalizing bipartite graphs. First, we give a polynomial time approximation algorithm for the maximum weight matching problem on so-called partitioned hypergraphs, whose approximation factor is best possible up to a constant. Afterwards, we look at the theorems of König and Hall and their relation. Our main result is a condition for the existence of perfect matchings in normal hypergraphs that generalizes Hall’s condition for bipartite graphs. In Chapter 3, we consider perfect f-matchings, f-factors, and (g,f)-matchings. We prove conditions for the existence of (g,f)-matchings in unimodular hypergraphs, perfect f-matchings in uniform Mengerian hypergraphs, and f-factors in uniform balanced hypergraphs. In addition, we give an overview about the complexity of the (g,f)-matching problem on different classes of hypergraphs generalizing bipartite graphs. In Chapter 4, we study the structure of hypergraphs that admit a perfect matching. We show that these hypergraphs can be decomposed along special cuts. For graphs it is known that the resulting decomposition is unique, which does not hold for hypergraphs in general. However, we prove the uniqueness of this decomposition (up to parallel hyperedges) for uniform hypergraphs. In Chapter 5, we investigate flows on directed hypergraphs, where we focus on graph-based directed hypergraphs, which means that every hyperarc is the union of a set of pairwise disjoint ordinary arcs. We define a residual network, which can be used to decide whether a given flow is optimal or not. Our main result in this chapter is an algorithm that computes a minimum cost flow on a graph-based directed hypergraph. This algorithm is a generalization of the network simplex algorithm. N2 - Diese Arbeit untersucht Matchings und Flüsse in Hypergraphen mit Hilfe kombinatorischer Methoden. In Graphen gehören diese Probleme zu den grundlegendsten der kombinatorischen Optimierung. Viele Resultate lassen sich nicht von Graphen auf Hypergraphen verallgemeinern, da Hypergraphen ein sehr abstraktes Konzept bilden. Daher schauen wir uns bestimmte Klassen von Hypergraphen an, die mehr Struktur besitzen, und nutzen diese aus um Resultate aus der Graphentheorie zu übertragen. In Kapitel 2 betrachten wir das perfekte Matchingproblem auf Klassen von „bipartiten“ Hypergraphen, wobei es verschiedene Möglichkeiten gibt den Begriff „bipartit“ auf Hypergraphen zu definieren. Für sogenannte partitionierte Hypergraphen geben wir einen polynomiellen Approximationsalgorithmus an, dessen Gütegarantie bis auf eine Konstante bestmöglich ist. Danach betrachten wir die Sätze von Konig und Hall und untersuchen deren Zusammenhang. Unser Hauptresultat ist eine Bedingung für die Existenz von perfekten Matchings auf normalen Hypergraphen, die Halls Bedingung für bipartite Graphen verallgemeinert. Als Verallgemeinerung von perfekten Matchings betrachten wir in Kapitel 3 perfekte f-Matchings, f-Faktoren und (g, f)-Matchings. Wir beweisen Bedingungen für die Existenz von (g, f)-Matchings auf unimodularen Hypergraphen, perfekten f-Matchings auf uniformen Mengerschen Hypergraphen und f-Faktoren auf uniformen balancierten Hypergraphen. Außerdem geben wir eine Übersicht über die Komplexität des (g, f)-Matchingproblems auf verschiedenen Klassen von Hypergraphen an, die bipartite Graphen verallgemeinern. In Kapitel 4 untersuchen wir die Struktur von Hypergraphen, die ein perfektes Matching besitzen. Wir zeigen, dass diese Hypergraphen entlang spezieller Schnitte zerlegt werden können. Für Graphen weiß man, dass die so erhaltene Zerlegung eindeutig ist, was im Allgemeinen für Hypergraphen nicht zutrifft. Wenn man jedoch uniforme Hypergraphen betrachtet, dann liefert jede Zerlegung die gleichen unzerlegbaren Hypergraphen bis auf parallele Hyperkanten. Kapitel 5 beschäftigt sich mit Flüssen in gerichteten Hypergraphen, wobei wir Hypergraphen betrachten, die auf gerichteten Graphen basieren. Das bedeutet, dass eine Hyperkante die Vereinigung einer Menge von disjunkten Kanten ist. Wir definieren ein Residualnetzwerk, mit dessen Hilfe man entscheiden kann, ob ein gegebener Fluss optimal ist. Unser Hauptresultat in diesem Kapitel ist ein Algorithmus, um einen Fluss minimaler Kosten zu finden, der den Netzwerksimplex verallgemeinert. KW - Matchings KW - Balanced Hypergraphs KW - Normal Hypergraphs KW - Mengerian Hypergraphs KW - Factors KW - Tight Cuts KW - Network Flows Y1 - 2019 UR - http://nbn-resolving.de/urn:nbn:de:kobv:188-refubium-24385-6 ER - TY - GEN A1 - Serrano, Felipe T1 - Visible points, the separation problem, and applications to MINLP N2 - In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require that every valid cut separating the infeasible point from the restricted feasible region is still valid for the original feasible region. We translate this requirement in terms of the separation problem and the reverse polar. In particular, if the reverse polar of the restricted feasible region is the same as the reverse polar of the feasible region, then any cut valid for the restricted feasible region that \emph{separates} the infeasible point, is valid for the feasible region. We show that the reverse polar of the \emph{visible points} of the feasible region from the infeasible point coincides with the reverse polar of the feasible region. In the special where the feasible region is described by a single non-convex constraint intersected with a convex set we provide a characterization of the visible points. Furthermore, when the non-convex constraint is quadratic the characterization is particularly simple. We also provide an extended formulation for a relaxation of the visible points when the non-convex constraint is a general polynomial. Finally, we give some conditions under which for a given set there is an inclusion-wise smallest set, in some predefined family of sets, whose reverse polars coincide. T3 - ZIB-Report - 19-38 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74016 SN - 1438-0064 ER - TY - GEN A1 - Sahin, Guvenc A1 - Ahmadi, Amin A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Multi-Period Line Planning with Resource Transfers N2 - Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with transfer of resources during a finite length planning horizon of multiple periods. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of line type designs and question the choice of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions. T3 - ZIB-Report - 19-51 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74662 SN - 1438-0064 ER - TY - GEN A1 - Anderson, Daniel A1 - Hendel, Gregor A1 - Le Bodic, Pierre A1 - Viernickel, Jan Merlin T1 - Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation N2 - We propose a simple and general online method to measure the search progress within the Branch-and-Bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases. T3 - ZIB-Report - 19-11 KW - Mixed-Integer Programming solvers KW - Restart KW - Progress measures KW - tree-size estimates Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72653 SN - 1438-0064 ER - TY - GEN A1 - Serrano, Felipe A1 - Muñoz, Gonzalo T1 - Maximal Quadratic-Free Sets N2 - The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex set S. The key ingredients in this construction are a simplicial conic relaxation of S and an S-free set: a convex zone whose interior does not intersect S. Ideally, such S-free set would be maximal inclusion-wise, as it would generate a deeper cutting plane. However, maximality can be a challenging goal in general. In this work, we show how to construct maximal S-free sets when S is defined as a general quadratic inequality. Our maximal S-free sets are such that efficient separation of a vertex in LP-based approaches to quadratically constrained problems is guaranteed. To the best of our knowledge, this work is the first to provide maximal quadratic-free sets. T3 - ZIB-Report - 19-56 KW - MINLP KW - Quadratic Optimization KW - Cutting planes Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-76922 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - New Perspectives on PESP: T-Partitions and Separators N2 - In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that had been proposed in the past, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. The second of these algorithms turns a strategy, that had been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time. T3 - ZIB-Report - 19-35 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Graph Partitioning KW - Graph Separators KW - Balanced Cuts Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73853 SN - 1438-0064 ER - TY - GEN A1 - Löbel, Fabian A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing N2 - The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances. T3 - ZIB-Report - 19-36 KW - Periodic Event Scheduling Problem KW - Periodic Timetabling KW - Integrated Passenger Routing KW - Shortest Routes in Public Transport Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73868 SN - 1438-0064 ER - TY - GEN A1 - Müller, Benjamin A1 - Muñoz, Gonzalo A1 - Gasse, Maxime A1 - Gleixner, Ambros A1 - Lodi, Andrea A1 - Serrano, Felipe T1 - On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming N2 - The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate strong dual bounds through extensive computational experiments. T3 - ZIB-Report - 19-55 KW - surrogate relaxation KW - MINLP KW - nonconvex optimization Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75179 SN - 1438-0064 ER - TY - GEN A1 - Müller, Benjamin A1 - Serrano, Felipe A1 - Gleixner, Ambros T1 - Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms N2 - One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly. T3 - ZIB-Report - 19-15 KW - mixed-integer quadratically constrained programs KW - nonconvex KW - global optimization KW - separation KW - propagation KW - projection KW - bilinear terms Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72759 SN - 1438-0064 ER -