TY - GEN A1 - Pfetsch, Marc A1 - Borndörfer, Ralf T1 - Routing in Line Planning for Public Transportation N2 - The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a network such that a giv en demand can be satisfied. There are two objectives. Passengers want to minimize travel times, the transport company wishes to minimize operating costs. We investigate three variants of a multi-commo dity flow model for line planning that differ with respect to passenger routings. The first model allows arbitrary routings, the second only unsplittable routings, and the third only shortest path rou tings with respect to the network. We compare these models theoretically and computationally on data for the city of Potsdam. T3 - ZIB-Report - 05-36 KW - line planning KW - column generation KW - passenger routing Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8706 ER - TY - GEN A1 - Bosse, Hartwig A1 - Grötschel, Martin A1 - Henk, Martin T1 - Polynomial Inequalities Representing Polyhedra N2 - Our main result is that every $n$-dimensional polytope can be described by at most $2n-1$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an $n$-dimensional pointed polyhedral cone we prove the bound $2n-2$ and for arbitrary polyhedra we get a constructible representation by $2n$ polynomial inequalities. T3 - ZIB-Report - 04-53 KW - polyhedra and polytopes KW - semi-algebraic sets KW - polyhedral combinatorics KW - polynomial inequalities KW - stability index Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8284 ER - TY - GEN A1 - Stephan, Rüdiger T1 - Facets of the (s,t)-p-path polytope N2 - \noindent We give a partial description of the $(s,t)-p$-path polytope of a directed graph $D$ which is the convex hull of the incidence vectors of simple directed $(s,t)$-paths in $D$ of length $p$. First, we point out how the $(s,t)-p$-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the $p$-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length $p$ in $D$. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identifie d to be valid for $(s,t)$-paths of cardinality at most $p$. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the $(s,t)-p$-path polytope. T3 - ZIB-Report - 06-38 Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9328 ER - TY - GEN A1 - Joswig, Michael A1 - Pfetsch, Marc T1 - Computing Optimal Morse Matchings N2 - Morse matchings capture the essential structural information of discrete Morse functions. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results. T3 - ZIB-Report - 04-37 KW - discrete Morse function KW - Morse matching Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8120 ER - TY - GEN A1 - Jokar, Sadegh A1 - Pfetsch, Marc T1 - Exact and Approximate Sparse Solutions of Underdetermined Linear Equations N2 - In this paper, we empirically investigate the NP-hard problem of finding sparse solutions to linear equation systems, i.e., solutions with as few nonzeros as possible. This problem has received considerable interest in the sparse approximation and signal processing literature, recently. We use a branch-and-cut approach via the maximum feasible subsystem problem to compute optimal solutions for small instances and investigate the uniqueness of the optimal solutions. We furthermore discuss five (modifications of) heuristics for this problem that appear in different parts of the literature. For small instances, the exact optimal solutions allow us to evaluate the quality of the heuristics, while for larger instances we compare their relative performance. One outcome is that the basis pursuit heuristic performs worse, compared to the other methods. Among the best heuristics are a method due to Mangasarian and a bilinear approach. T3 - ZIB-Report - 07-05 KW - sparse representations KW - basis pursuit KW - orthogonal matching pursuit KW - maximum feasible subsystem problem Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9488 ER - TY - GEN A1 - Bley, Andreas T1 - Approximability of Unsplittable Shortest Path Routing Problems N2 - In this paper, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph $D=(V,A)$ and a set $K$ of directed commodities, an USPR is a set of flow paths $\Phi_{(s,t)}$, $(s,t)\in K$, such that there exists a metric $\lambda=(\lambda_a)\in \mathbb{Z}^A_+$ with respect to which each $\Phi_{(s,t)}$ is the unique shortest $(s,t)$-path. In the \textsc{Min-Con-USPR} problem, we seek for an USPR that minimizes the maximum congestion over all arcs. We show that this problem is hard to approximate within a factor of $\mathcal{O}(|V|^{1-\epsilon})$, but easily approximable within min$(|A|,|K|)$ in general and within $\mathcal{O}(1)$ if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of $\Omega(|V|^2)$ larger than that achievable by unsplittable flow routing or by shortest multi-path routing, and a factor of $\Omega(|V|)$ larger than by unsplittable source-invariant routing. In the CAP-USPR problem, we seek for a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is $\mathcal{NP}$-hard to approximate within $2-\epsilon$ (even in the undirected case), and we devise approximation algorithms for various special cases. The fixed charge network design problem \textsc{Cap-USPR}, where the task is to find a minimum cost subgraph of $D$ whose fixed arc capacities admit an USPR of the commodities, is shown to be $\mathcal{NPO}$-complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi-path routing problems. T3 - ZIB-Report - 06-02 KW - Shortest path routing KW - unsplittable flow KW - computational complexity KW - approximation Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8968 ER - TY - GEN A1 - Shioura, Akiyoshi T1 - Note on L#-convex Function Minimization Algorithms: Comparison of Murota's and Kolmogorov's Algorithms N2 - The concept of L##-convexity is introduced by Fujishige--Murota (2000) as a discrete convexity for functions defined over the integer lattice. The main aim of this note is to understand the difference of the two algorithms for L##-convex function minimization: Murota's steepest descent algorithm (2003) and Kolmogorov's primal algorithm (2005). T3 - ZIB-Report - 06-03 Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8979 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Pfetsch, Marc T1 - A Column-Generation Approach to Line Planning in Public Transport N2 - The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported. T3 - ZIB-Report - 05-18 KW - line planning KW - column generation Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8522 ER - TY - GEN A1 - Grötschel, Martin T1 - Schnelle Rundreisen: Das Travelling Salesman-Problem N2 - Das Travelling-Salesman-Problem (TSP) ist das am intensivsten untersuchte kombinatorische Optimierungsproblem. In diesem Abschnitt wird eine Einführung in das TSP gegeben. Es werden Problemstellungen erläutert, Anwendungen skizziert und einige Schwierigkeiten bei der korrekten Modellierung der Zielfunktion dargelegt. Es ist gar nicht so klar, was in einem konkreten Problem die wirkliche Entfernung ist. Exakte und approximative Lösungsverfahren werden an Beispielen skizziert, und es wird angedeutet, dass man, obwohl TSPs zu den theoretisch schweren Problemen zählen, in der Praxis TSPs von atemberaubender Größe lösen kann. T3 - ZIB-Report - 05-57 KW - Travelling-Salesman-Problem KW - TSP KW - Rundreisen KW - optimale Tour Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8901 ER - TY - GEN A1 - Shioura, Akiyoshi A1 - Tanaka, Ken'ichiro T1 - Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems N2 - The concept of jump system, introduced by Buchet and Cunningham (1995), is a set of integer points with a certain exchange property. In this paper, we discuss several linear and convex optimization problems on jump systems and show that these problems can be solved in polynomial time under the assumption that a membership oracle for a jump system is available. We firstly present a polynomial-time implementation of the greedy algorithm for the minimization of a linear function. We then consider the minimization of a separable-convex function on a jump system, and propose the first polynomial-time algorithm for this problem. The algorithm is based on the domain reduction approach developed in Shioura (1998). We finally consider the concept of M-convex functions on constant-parity jump systems which has been recently proposed by Murota (2006). It is shown that the minimization of an M-convex function can be solved in polynomial time by the domain reduction approach. T3 - ZIB-Report - 06-19 KW - jump system KW - discrete convex function KW - bisubmodular function KW - bisubmodular polyhedron KW - polynomial-time algorithm Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9122 ER -