TY - GEN A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc T1 - Fare Planning for Public Transport N2 - In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments. T3 - ZIB-Report - 05-20 KW - fare planning KW - demand function KW - discrete choice model Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8541 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc T1 - The Steiner Connectivity Problem N2 - The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role. T3 - ZIB-Report - 09-07 KW - Steiner Tree KW - Partition Inequalities KW - Paths KW - Connectivity KW - Generalization Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11171 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Nonlinear pseudo-Boolean optimization: relaxation or propagation? N2 - Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver. T3 - ZIB-Report - 09-11 KW - Pseudo-Boolean KW - constraint integer programming KW - linear relaxation KW - separation algorithm KW - domain propagation Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11232 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 - TY - GEN A1 - Berthold, Timo A1 - Pfetsch, Marc T1 - Detecting Orbitopal Symmetries N2 - Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment structure. We investigate the detection of symmetries appearing in this approach. We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear time if the assignment structure is known. T3 - ZIB-Report - 08-33 KW - Symmetrie-Erkennung KW - Orbitope KW - Ganzzahlige Programmierung KW - Symmetrie-Brechung KW - Graphenisomorphie KW - symmetry detection KW - orbitopes KW - integer programming KW - symmetry breaking KW - graph ismorphism Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10842 SN - 1438-0064 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System N2 - Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated. T3 - ZIB-Report - 08-35 KW - line planning KW - computational complexity KW - public transport KW - integer programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10869 SN - 1438-0064 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - On the Line Planning Problem in Tree Networks N2 - We introduce an optimization model for the line planning problem in a public transportation system that aims at minimizing operational costs while ensuring a given level of quality of service in terms of available transport capacity. We discuss the computational complexity of the model for tree network topologies and line structures that arise in a real-world application at the Trolebus Integrated System in Quito. Computational results for this system are reported. T3 - ZIB-Report - 08-52 KW - line planning KW - computational complexity KW - public transport optimization Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11069 SN - 1438-0064 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System (Extended Abstract) N2 - Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated. T3 - ZIB-Report - 08-53 KW - line planning KW - computational complexity KW - public transport KW - integer programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11076 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Solving Pseudo-Boolean Problems with SCIP N2 - 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. T3 - ZIB-Report - 08-12 KW - Pseudo-Boolean KW - Constraint Programming KW - Ganzzahlige Programmierung KW - Branch-And-Cut KW - Optimierungssoftware KW - Pseudo-Boolean KW - constraint integer programming KW - integer programming KW - branch-and-cut KW - optimization software Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10671 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc T1 - Models for Fare Planning in Public Transport N2 - The optimization of fare systems in public transit allows to pursue objectives such as the maximization of demand, revenue, profit, or social welfare. We propose a non-linear optimization approach to fare planning that is based on a detailed discrete choice model of user behavior. The approach allows to analyze different fare structures, optimization objectives, and operational scenarios involving, e.g., subsidies. We use the resulting models to compute optimized fare systems for the city of Potsdam, Germany. T3 - ZIB-Report - 08-16 KW - Preisplanung KW - Nachfragefunktion KW - Optimierung KW - Nahverkehr Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10708 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc T1 - Optimal Fares for Public Transport N2 - The \emph{fare planning problem} for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a d iscrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands. T3 - ZIB-Report - 05-35 KW - fare planning KW - demand function KW - discrete choice model Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8698 ER - TY - GEN A1 - Harks, Tobias A1 - Heinz, Stefan A1 - Pfetsch, Marc A1 - Vredeveld, Tjark T1 - Online Multicommodity Routing with Time Windows N2 - We consider a multicommodity routing problem, where demands are released \emph{online} and have to be routed in a network during specified time windows. The objective is to minimize a time and load dependent convex cost function of the aggregate arc flow. First, we study the fractional routing variant. We present two online algorithms, called Seq and Seq$^2$. Our first main result states that, for cost functions defined by polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of Seq and Seq$^2$ is at most $(d+1)^{d+1}$, which is tight. We also present lower bounds of $(0.265\,(d+1))^{d+1}$ for any online algorithm. In the case of a network with two nodes and parallel arcs, we prove a lower bound of $(2-\frac{1}{2} \sqrt{3})$ on the competitive ratio for Seq and Seq$^2$, even for affine linear price functions. Furthermore, we study resource augmentation, where the online algorithm has to route less demand than the offline adversary. Second, we consider unsplittable routings. For this setting, we present two online algorithms, called U-Seq and U-Seq$^2$. We prove that for polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of U-Seq and U-Seq$^2$ is bounded by $O{1.77^d\,d^{d+1}}$. We present lower bounds of $(0.5307\,(d+1))^{d+1}$ for any online algorithm and $(d+1)^{d+1}$ for our algorithms. Third, we consider a special case of our framework: online load balancing in the $\ell_p$-norm. For the fractional and unsplittable variant of this problem, we show that our online algorithms are $p$ and $O{p}$ competitive, respectively. Such results where previously known only for scheduling jobs on restricted (un)related parallel machines. T3 - ZIB-Report - 07-22 KW - Online Optimization KW - Routing KW - Telecommunications Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9654 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc A1 - Vigerske, Stefan T1 - Large Neighborhood Search beyond MIP N2 - Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics. T3 - ZIB-Report - 11-21 KW - Large Neighborhood Search KW - Primal Heuristic KW - MIP KW - MIQCP KW - Pseudo-Boolean Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12989 ER - TY - GEN A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Pfetsch, Marc ED - Jünger, Michael ED - Reinelt, Gerhard T1 - Progress in Academic Computational Integer Programming T2 - Facets of Combinatorial Optimization Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38189-8_19 SP - 483 EP - 506 PB - Springer ER - TY - BOOK A1 - Koch, Thorsten A1 - Hiller, Benjamin A1 - Pfetsch, Marc A1 - Schewe, Lars T1 - Evaluating Gas Network Capacities Y1 - 2015 SN - 978-1-611973-68-6 PB - SIAM ER - TY - JOUR A1 - Pfetsch, Marc A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Geißler, Nina A1 - Gollmer, Ralf A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Vigerske, Stefan A1 - Willert, Bernhard T1 - Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions JF - Optimization Methods and Software N2 - In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult feasibility problem. The first phase consists of four distinct algorithms applying linear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before. Y1 - 2014 U6 - https://doi.org/10.1080/10556788.2014.888426 PB - Taylor & Francis ER - TY - JOUR A1 - Humpola, Jesco A1 - Joormann, Imke A1 - Oucherif, Djamal A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schwarz, Robert T1 - GasLib - A Library of Gas Network Instances JF - Optimization Online N2 - The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances that can be used by researchers in the field of gas transport. The advantages are that researchers save time by using these instances and that different models and algorithms can be compared on the same specified test sets. The library instances are encoded in an XML format. In this paper, we explain this format and present the instances that are available in the library. Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57950 ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc A1 - Vigerske, Stefan T1 - Large Neighborhood Search beyond MIP T2 - Proceedings of the 9th Metaheuristics International Conference (MIC 2011) N2 - Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics. Y1 - 2011 SN - 978-88-900984-3-7 SP - 51 EP - 60 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Pfetsch, Marc T1 - The Steiner connectivity problem JF - Mathematical Programming A Y1 - 2013 U6 - https://doi.org/10.1007/s10107-012-0564-5 VL - 142 IS - 1 SP - 133 EP - 167 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Pfetsch, Marc T1 - Models for Fare Planning in Public Transport JF - Discrete Applied Mathematics Y1 - 2012 U6 - https://doi.org/10.1016/j.dam.2012.02.027 VL - 160 IS - 18 SP - 2591 EP - 2605 ER -