@misc{Helmberg2001, author = {Helmberg, Christoph}, title = {A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6527}, number = {01-26}, year = {2001}, abstract = {The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably.}, language = {en} } @misc{KrumkeRambau2002, author = {Krumke, Sven and Rambau, J{\"o}rg}, title = {Probieren geht {\"u}ber Studieren? Entscheidungshilfen f{\"u}r kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6723}, number = {02-05}, year = {2002}, abstract = {Die Automatisierung von innerbetrieblicher Logistik erfordert -- {\"u}ber die physikalische Steuerung von Ger{\"a}ten hinaus -- auch eine effiziente Organisation der Transporte: ein Aufgabenfeld der kombinatorischen Optimierung. Dieser Artikel illustriert anhand von konkreten Aufgabenstellungen die Online-Problematik (unvollst{\"a}ndiges Wissen) sowie die Echtzeit-Problematik (beschr{\"a}nkte Rechenzeit), auf die man in der innerbetrieblichen Logistik trifft. Der Text gibt einen {\"U}berblick {\"u}ber allgemeine Konstruktionsprinzipien f{\"u}r Online-Algorithmen und Bewertungsmethoden, die bei der Entscheidung helfen, welche Algorithmen f{\"u}r eine vorliegende Problemstellung geeignet sind.}, language = {de} } @misc{Pfetsch2005, author = {Pfetsch, Marc}, title = {A Branch-And-Cut for the Maximum Feasible Subsystem Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8797}, number = {05-46}, year = {2005}, abstract = {We present a branch-and-cut algorithm for the NP-hard maximum feasible subsystem problem: For a given infeasible linear inequality system, determine a feasible subsystem containing as many inequalities as possible. The complementary problem, where one has to remove as few inequalities as possible in order to render the system feasible, can be formulated as a set covering problem. The rows of this formulation correspond to irreducible infeasible subsystems, which can be exponentially many. The main issue of a branch-and-cut algorithm for MaxFS is to efficiently find such infeasible subsystems. We present three heuristics for the corresponding NP-hard separation problem and discuss further cutting planes. This paper contains an extensive computational study of our implementation on a variety of instances arising in a number of applications.}, language = {en} } @misc{KaibelKoch2006, author = {Kaibel, Volker and Koch, Thorsten}, title = {Mathematik f{\"u}r den Volkssport}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9225}, number = {06-28}, year = {2006}, abstract = {"`Volkssport Sudoku"' titelt der Stern in seiner Ausgabe vom 24. Mai2006. In der Tat traut sich derzeit kaum noch eine Zeitung, ohne Sudoku zu erscheinen. Die Begeisterung am L{\"o}sen dieser Zahlenr{\"a}tsel offenbart eine unvermutete Freude am algorithmischen Arbeiten. Mathematisch kann man Sudokus als lineare diophantische Gleichungssysteme mit Nichtnegativit{\"a}tsbedingungen formulieren. Solche ganzzahligen linearen Programme sind die wichtigsten Modellierungswerkzeuge in zahlreichen Anwendungsgebieten wie z.B. der Optimierung von Telekommunikations- und Verkehrsnetzen. Moderne Verfahren zur L{\"o}sung dieser Optimierungsprobleme sind durch Sudokus allerdings deutlich weniger zu beeindrucken als Zeitungsleser.}, language = {de} } @misc{PossRaack2011, author = {Poss, Michael and Raack, Christian}, title = {Affine recourse for the robust network design problem: between static and dynamic routing}, doi = {10.1002/net.21482}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12122}, number = {11-03}, year = {2011}, abstract = {Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework of two-stage network design with recourse. It is shown that affine routing can be seen as a generalization of the widely used static routing still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.}, language = {en} } @misc{BorndoerferErolGraffagninoetal.2010, author = {Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Schlechte, Thomas and Swarat, Elmar}, title = {Optimizing the Simplon Railway Corridor}, organization = {Zuse Institut Berlin}, issn = {1438-0064}, doi = {10.1007/s10479-012-1260-9}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11892}, number = {10-24}, year = {2010}, abstract = {This paper presents a case study on a railway timetable optimization for the very dense Simplon corridor, a major railway connection in the Alps between Switzerland and Italy. Starting from a detailed microscopic network as it is used in railway simulation, the data is transformed by an automatic procedure to a less detailed macroscopic network, that is sufficient for the purpose of capacity planning and amenable to state-of-the-art integer programming optimization methods. In this way, the macroscopic railway network is saturated with trains. Finally, the corresponding timetable is re-transformed to the microscopic level in such a way that it can be operated without any conflicts among the slots. Using this integer programming based micro-macro aggregation-disaggregation approach, it becomes for the first time possible to generate a profit maximal and conflict free timetable for the complete Simplon corridor over an entire day by a simultaneous optimization of all trains requests. This also allows to to undertake a sensitivity analysis of various problem parameters.}, language = {en} } @misc{BorndoerferSchlechteWeider2010, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Railway Track Allocation by Rapid Branching}, organization = {Zuse Institut Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11864}, number = {10-22}, year = {2010}, abstract = {The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.}, language = {en} } @misc{BorndoerferKarbstein2014, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Metric Inequalities for Routings on Direct Connections}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-44219}, year = {2014}, abstract = {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.}, language = {en} } @phdthesis{Karbstein2013, author = {Karbstein, Marika}, title = {Line Planning and Connectivity}, isbn = {978-3-8439-1062-0}, year = {2013}, abstract = {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.}, language = {en} } @misc{BorndoerferHoppmannKarbstein2013, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {A Configuration Model for the Line Planning Problem}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2013.68}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-41903}, year = {2013}, abstract = {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.}, language = {en} } @misc{HeismannHildenbrandtSilvestrietal.2013, author = {Heismann, Olga and Hildenbrandt, Achim and Silvestri, Francesco and Reinelt, Gerhard and Bornd{\"o}rfer, Ralf}, title = {HUHFA: A Framework for Facet Classification}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42230}, year = {2013}, abstract = {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.}, language = {en} } @phdthesis{Helmberg2000, author = {Helmberg, Christoph}, title = {Semidefinite Programming for Combinatorial Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6022}, number = {00-34}, year = {2000}, abstract = {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.}, language = {en} } @phdthesis{Martin1999, author = {Martin, Alexander}, title = {Integer Programs with Block Structure}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3911}, number = {SC-99-03}, year = {1999}, abstract = {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.}, language = {en} } @misc{Bley2008, author = {Bley, Andreas}, title = {An Integer Programming Algorithm for Routing Optimization in IP Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10814}, number = {08-30}, year = {2008}, abstract = {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.}, language = {en} } @misc{SchlechteBorndoerfer2008, author = {Schlechte, Thomas and Bornd{\"o}rfer, Ralf}, title = {Balancing Efficiency and Robustness - A Bi-criteria Optimization Approach to Railway Track Allocation}, organization = {ZIB}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10763}, number = {08-22}, year = {2008}, abstract = {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.}, language = {en} } @misc{ErolKlemenzSchlechteetal.2008, author = {Erol, Berkan and Klemenz, Marc and Schlechte, Thomas and Schultz, S{\"o}ren and Tanner, Andreas}, title = {TTPLIB 2008 - A Library for Train Timetabling Problems}, organization = {ZIB,}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10732}, number = {08-19}, year = {2008}, abstract = {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.}, language = {en} } @misc{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Line Connectivity Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10820}, number = {08-31}, year = {2008}, abstract = {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.}, language = {en} } @misc{BertholdHeinzPfetsch2008, author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc}, title = {Solving Pseudo-Boolean Problems with SCIP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10671}, number = {08-12}, year = {2008}, abstract = {Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field. In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.}, language = {en} } @misc{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Angebotsplanung im {\"o}ffentlichen Nahverkehr}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10555}, number = {08-04}, year = {2008}, abstract = {Die Angebotsplanung im {\"o}ffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen f{\"u}r die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenh{\"a}nge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abh{\"a}ngigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.}, language = {de} } @misc{Stephan2008, author = {Stephan, R{\"u}diger}, title = {On the cardinality constrained matroid polytope}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10614}, number = {08-08}, year = {2008}, abstract = {Edmonds showed that the so-called rank inequalities and the nonnegativity constraints provide a complete linear description of the matroid polytope. By essentially adding Gr{\"o}tschel's cardinality forcing inequalities, we obtain a complete linear description of the cardinality constrained matroid polytope which is the convex hull of the incidence vectors of those independent sets that have a feasible cardinality. Moreover, we show how the separation problem for the cardinality forcing inequalities can be reduced to that for the rank inequalities. We also give necessary and sufficient conditions for a cardinality forcing inequality to be facet defining.}, language = {en} }