TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - Metric Inequalities for Routings on Direct Connections N2 - We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We show that the concept of metric inequalities to characterize capacities that support a multi-commodity flow can be generalized to deal with direct connections. T3 - ZIB-Report - 14-04 KW - metric inequalities KW - direct connection KW - multi-commodity flow problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44219 SN - 1438-0064 ER - TY - THES A1 - Karbstein, Marika T1 - Line Planning and Connectivity N2 - This thesis introduces the Steiner connectivity problem. It is a generalization of the well known Steiner tree problem. Given a graph G = (V, E) and a subset T ⊆ V of the nodes, the Steiner tree problem consists in finding a cost minimal set of edges connecting all nodes in T . The Steiner connectivity problem chooses, instead of edges, from a given set of paths a subset to connect all nodes in T . We show in the first part of this thesis that main results about complexity, approximation, integer programming formulations, and polyhedra can be generalized from the Steiner tree problem to the Steiner connectivity problem. An example for a straightforward generalization are the Steiner partition inequalities, a fundamental class of facet defining inequalities for the Steiner tree problem. They can be defined for the Steiner connectivity problem in an analogous way as for the Steiner tree problem. An example for a generalization that needs more effort is the definition of a directed cut formulation and the proof that this dominates the canonical undirected cut formulation enriched by all Steiner partition inequalities. For the Steiner connectivity problem this directed cut formulation leads to extended formulations, a concept that is not necessary for the Steiner tree problem. There are also major differences between both problems. For instance, the case T = V for the Steiner connectivity problem is equivalent to a set covering problem and, hence, not a polynomial solvable case as in the Steiner tree problem. The Steiner connectivity problem is not only an interesting generalization of the Steiner tree problem but also the underlying connectivity problem in line planning with inte- grated passenger routing. The integrated line planning and passenger routing problem is an important planning problem in service design of public transport and the topic of the second part. Given is the infrastructure network of a public transport system where the edges correspond to streets and tracks and the nodes correspond to stations/stops of lines. The task is to find paths in the infrastructure network for lines and passengers such that the capacities of the lines suffice to transport all passengers. Existing models in the literature that integrate a passenger routing in line planning either treat transfers in a rudimentary way and, hence, neglect an important aspect for the choice of the pas- senger routes, or they treat transfers in a too comprehensive way and cannot be solved for large scale real world problems. We propose a new model that focuses on direct connections. The attractiveness of transfer free connections is increased by introducing a transfer penalty for each non-direct connection. In this way, a passenger routing is computed that favors direct connections. For the computation of this model we also implemented algorithms influenced by the results for the Steiner connectivity problem. We can compute with our model good solutions that minimize a weighted sum of line operating costs and passengers travel times. These solutions improve the solutions of an existing approach, that does not consider direct connections, by up to 17%. In contrast to a comprehensive approach, that considers every transfer and for which we could not even solve the root LP within 10 hours for large instances, the solutions of the new model, computed in the same time, are close to optimality (<1%) or even optimal for real world instances. In a project with the Verkehr in Potsdam GmbH to compute the line plan for 2010 we showed that our approach is applicable in practice and can be used to solve real world problems. Y1 - 2013 UR - www.zib.de/karbstein/scplpp.pdf SN - 978-3-8439-1062-0 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - A Configuration Model for the Line Planning Problem N2 - We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model. T3 - ZIB-Report - 13-40 KW - combinatorial optimization KW - polyhedral combinatorics KW - line planning Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-41903 SN - 1438-0064 ER - TY - GEN A1 - Heismann, Olga A1 - Hildenbrandt, Achim A1 - Silvestri, Francesco A1 - Reinelt, Gerhard A1 - Borndörfer, Ralf T1 - HUHFA: A Framework for Facet Classification N2 - Usually complete linear descriptions of polytopes consist of an enormous number of facet-defining inequalities already for very small problem sizes. In this paper, we describe a method for dividing the inequalities into equivalence classes without resorting to a normal form. Within each class, facets are related by certain symmetries and it is sufficient to list one representative of each class to give a complete picture of the structural properties of a polytope. We propose an algorithm for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem. T3 - ZIB-Report - 13-45 KW - facet classification KW - symmetry KW - polyhedral structure Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42230 SN - 1438-0064 ER - TY - THES A1 - Helmberg, Christoph T1 - Semidefinite Programming for Combinatorial Optimization N2 - This book offers a self-contained introduction to the field of semidefinite programming, its applications in combinatorial optimization, and its computational methods. We equip the reader with the basic results from linear algebra on positive semidefinite matrices and the cone spanned by them. Starting from linear programming, we introduce semidefinite programs and discuss the associated duality theory. We then turn to semidefinite relaxations of combinatorial optimization and illustrate their interrelation. In the second half we deal with computational methods for solving semidefinite programs. First, the interior point approach, its iteration complexity, and implementational issues are discussed. Next, we explain in great detail the spectral bundle method, which is particularly suited for large scale semidefinite programming. One of the most successful techniques in integer linear programming is the cutting plane approach which improves an initial relaxation by adding violated inequalities. We explore possibilities to combine the two solution methods with the cutting plane approach in order to strengthen semidefinite relaxations of combinatorial optimization problems. T3 - ZIB-Report - 00-34 KW - positive semidefinite matrices KW - semidefinite cone KW - semidefinite Programming KW - semidefinite duality KW - combinatorial optimization KW - max-cut KW - quadrati Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6022 ER - TY - THES A1 - Martin, Alexander T1 - Integer Programs with Block Structure N2 - In this thesis we study and solve integer programs with block structure, i.\,e., problems that after the removal of certain rows (or columns) of the constraint matrix decompose into independent subproblems. The matrices associated with each subproblem are called blocks and the rows (columns) to be removed linking constraints (columns). Integer programs with block structure come up in a natural way in many real-world applications. The methods that are widely used to tackle integer programs with block structure are decomposition methods. The idea is to decouple the linking constraints (variables) from the problem and treat them at a superordinate level, often called master problem. The resulting residual subordinate problem then decomposes into independent subproblems that often can be solved more efficiently. Decomposition methods now work alternately on the master and subordinate problem and iteratively exchange information to solve the original problem to optimality. In Part I we follow a different approach. We treat the integer programming problem as a whole and keep the linking constraints in the formulation. We consider the associated polyhedra and investigate the polyhedral consequences of the involved linking constraints. The variety and complexity of the new inequalities that come into play is illustrated on three different types of real-world problems. The applications arise in the design of electronic circuits, in telecommunication and production planning. We develop a branch-and-cut algorithm for each of these problems, and our computational results show the benefits and limits of the polyhedral approach to solve these real-world models with block structure. Part II of the thesis deals with general mixed integer programming problems, that is integer programs with no apparent structure in the constraint matrix. We will discuss in Chapter 5 the main ingredients of an LP based branch-and-bound algorithm for the solution of general integer programs. Chapter 6 then asks the question whether general integer programs decompose into certain block structures and investigate whether it is possible to recognize such a structure. The remaining two chapters exploit information about the block structure of an integer program. In Chapter 7 we parallelize parts of the dual simplex algorithm, the method that is commonly used for the solution of the underlying linear programs within a branch-and-cut algorithm. In Chapter 8 we try to detect small blocks in the constraint matrix and to derive new cutting planes that strengthen the integer programming formulation. These inequalities may be associated with the intersection of several knapsack problems. We will see that they significantly improve the quality of the general integer programming solver introduced in Chapter 5. T3 - ZIB-Report - SC-99-03 KW - integer programming KW - cutting planes KW - block structure Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3911 ER - TY - GEN A1 - Bley, Andreas T1 - An Integer Programming Algorithm for Routing Optimization in IP Networks N2 - Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm. T3 - ZIB-Report - 08-30 KW - Shortest Path Routing KW - Integer Programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10814 SN - 1438-0064 ER - TY - GEN A1 - Schlechte, Thomas A1 - Borndörfer, Ralf T1 - Balancing Efficiency and Robustness – A Bi-criteria Optimization Approach to Railway Track Allocation N2 - Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional $\epsilon$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network. T3 - ZIB-Report - 08-22 KW - Train Timetabling Problem KW - Bicriteria Optimization KW - Column Generation Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10763 SN - 1438-0064 ER - TY - GEN A1 - Erol, Berkan A1 - Klemenz, Marc A1 - Schlechte, Thomas A1 - Schultz, Sören A1 - Tanner, Andreas T1 - TTPLIB 2008 - A Library for Train Timetabling Problems N2 - We introduce (TTPlib), a data library for train timetabling problems that can be accessed at http://ttplib.zib.de. In version 1.0, the library contains data related to 50 scenarios. Most instances result from the combination of macroscopic railway networks and several train request sets for the German long distance area containing Hannover, Kassel and Fulda, short denoted by Ha-Ka-Fu. In this paper, we introduce the data concepts of TTPlib, describe the scenarios included in the library and provide a free visualization tool TraVis. T3 - ZIB-Report - 08-19 KW - Fahrplanung KW - Problembibliothek KW - Optimierung KW - Train Timetabling Problem KW - Data Library KW - Optimization Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10732 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc T1 - The Line Connectivity Problem N2 - This paper introduces the "line connectivity problem", a generalization of the Steiner tree problem and a special case of the line planning problem. We study its complexity and give an IP formulation in terms of an exponential number of constraints associated with "line cut constraints". These inequalities can be separated in polynomial time. We also generalize the Steiner partition inequalities. T3 - ZIB-Report - 08-31 KW - Steiner Tree Generalization Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10820 SN - 1438-0064 ER -