@article{HarrodSchlechte2013, author = {Harrod, Steven and Schlechte, Thomas}, title = {A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations}, volume = {54}, journal = {Transportation Research Part E: Logistics and Transportation Review}, doi = {10.1016/j.tre.2013.04.003}, pages = {50 -- 66}, year = {2013}, abstract = {Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, RCHF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and RCHF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall.}, language = {en} } @misc{BorndoerferKarbstein2013, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {A Primal-Dual Approximation Algorithm for the Steiner Connectivity Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42430}, year = {2013}, abstract = {We extend the primal-dual approximation technique of Goemans and Williamson to the Steiner connectivity problem, a kind of Steiner tree problem in hypergraphs. This yields a (k+1)-approximation algorithm for the case that k is the minimum of the maximal number of nodes in a hyperedge minus 1 and the maximal number of terminal nodes in a hyperedge. These results require the proof of a degree property for terminal nodes in hypergraphs which generalizes the well-known graph property that the average degree of terminal nodes in Steiner trees is at most 2.}, language = {en} } @inproceedings{HeismannBorndoerfer2013, author = {Heismann, Olga and Bornd{\"o}rfer, Ralf}, title = {The Random Hypergraph Assignment Problem}, booktitle = {Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013}, pages = {599 -- 602}, year = {2013}, abstract = {The analysis of random instances of a combinatorial optimization problem, especially their optimal values, can provide a better insight into its structure. Such an extensive analysis was theoretically and practically done for the assignment problem ("random assignment problem") and several of its generalizations. For a recent generalization of the assignment problem to bipartite hypergraphs, the hypergraph assignment problem, such results do not exist so far. We consider a random version of the hypergraph assignment problem for the simplest possible complete bipartite hypergraphs. They have only edges and proper hyperedges of size four and follow a special structure, but the hypergraph assignment problem for this type of hypergraphs is, however, already NP-hard. It can be viewed as a combination of two assignment problems. For random hyperedge costs exponentially i.i.d. with mean 1 we show computational results that suggest that the expected value of minimum cost hyperassignments converges to some value around 1.05 with a small standard deviation. The computational results also suggest that the optimal value is most probably attained with half of the maximum possible number of proper hyperedges. The main result of this paper is the proof that the expected value of a minimum cost hyperassignment which uses exactly half the possible maximum number of proper hyperedges if the vertex number tends to infinity lies between 0.3718 and 1.8310 when hyperedge costs are exponentially i.i.d. with mean 1.}, language = {en} } @article{Sagnol2013, author = {Sagnol, Guillaume}, title = {On the semidefinite representation of real functions applied to symmetric matrices}, volume = {439}, journal = {Linear Algebra and its Applications}, number = {10}, doi = {10.1016/j.laa.2013.08.021}, pages = {2829 -- 2843}, year = {2013}, abstract = {We present a new semidefinite representation for the trace of a real function f applied to symmetric matrices, when a semidefinite representation of the convex function f is known. Our construction is intuitive, and yields a representation that is more compact than the previously known one. We also show with the help of matrix geometric means and the Riemannian metric of the set of positive definite matrices that for a rational number p in the interval (0,1], the matrix X raised to the exponent p is the largest element of a set represented by linear matrix inequalities. We give numerical results for a problem inspired from the theory of experimental designs, which show that the new semidefinite programming formulation yields a speed-up factor in the order of 10.}, language = {en} } @inproceedings{HildenbrandtReineltHeismann2013, author = {Hildenbrandt, Achim and Reinelt, Gerhard and Heismann, Olga}, title = {Integer Programming Models for the Target Visitation Problem}, booktitle = {Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013}, pages = {569 -- 572}, year = {2013}, abstract = {The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinato- rial optimization problems: the traveling salesman and the linear ordering problem. In this paper we present several possible IP-Models for this problem and compared them to their usability for branch-and-cut approaches.}, 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} } @article{HillerKlugTuchscherer2013, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups}, journal = {Flexible Services and Manufacturing Journal}, doi = {10.1007/s10696-013-9175-6}, pages = {1 -- 24}, year = {2013}, language = {en} } @article{BorndoerferKarbsteinPfetsch2013, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Pfetsch, Marc}, title = {The Steiner connectivity problem}, volume = {142}, journal = {Mathematical Programming A}, number = {1}, doi = {10.1007/s10107-012-0564-5}, pages = {133 -- 167}, year = {2013}, language = {en} } @article{BorndoerferLoebelReutheretal.2013, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Rapid Branching}, volume = {5}, journal = {Public Transport}, number = {1}, editor = {Mu{\~n}oz, J. C. and Voß, S.}, publisher = {Springer Berlin Heidelberg}, pages = {3 -- 23}, year = {2013}, abstract = {We propose rapid branching (RB) as a general branch-and-bound heuristic for solving large scale optimization problems in traffic and transport. The key idea is to combine a special branching rule and a greedy node selection strategy in order to produce solutions of controlled quality rapidly and efficiently. We report on three successful applications of the method for integrated vehicle and crew scheduling, railway track allocation, and railway vehicle rotation planning.}, language = {en} } @article{Sagnol2013, author = {Sagnol, Guillaume}, title = {Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs}, volume = {161}, journal = {Discrete Applied Mathematics}, number = {1-2}, doi = {10.1016/j.dam.2012.07.016}, pages = {258 -- 276}, year = {2013}, abstract = {We study a family of combinatorial optimization problems defined by a parameter \$p\in[0,1]\$, which involves spectral functions applied to positive semidefinite matrices, and has some application in the theory of optimal experimental design. This family of problems tends to a generalization of the classical maximum coverage problem as \$p\$ goes to \$0\$, and to a trivial instance of the knapsack problem as \$p\$ goes to \$1\$. In this article, we establish a matrix inequality which shows that the objective function is submodular for all \$p\in[0,1]\$, from which it follows that the greedy approach, which has often been used for this problem, always gives a design within \$1-1/e\$ of the optimum. We next study the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors. We prove an inequality which generalizes a classical result from the theory of optimal designs, and allows us to give a rounding procedure with an approximation factor which tends to \$1\$ as \$p\$ goes to \$1\$.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein2013, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {A Configuration Model for the Line Planning Problem}, volume = {33}, booktitle = {ATMOS 2013 - 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Frigioni, Daniele and Stiller, Sebastian}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/OASIcs.ATMOS.2013.68}, pages = {68 -- 79}, year = {2013}, 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} } @inproceedings{BorndoerferBuwayaSagnoletal.2013, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach}, volume = {41}, booktitle = {Proceedings of INOC'2013}, doi = {http://dx.doi.org//10.1016/j.endm.2013.05.100}, pages = {253 -- 260}, year = {2013}, abstract = {We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented.}, language = {en} }