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 - 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 - Kaibel, Volker A1 - Peinhardt, Matthias A1 - Pfetsch, Marc T1 - Orbitopal Fixing N2 - The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up the branch-and-cut tree. We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving this kind of symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the branch-and-cut tree, removes redundant parts of the tree produced by the above mentioned permutations. The method relies on certain polyhedra, called orbitopes, which have been investigated in (Kaibel and Pfetsch (2006)). However, it does not add inequalities to the model, and thus, it does not increase the difficulty of solving the linear programming relaxations. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem motivated from frequency planning in mobile telecommunication networks. T3 - ZIB-Report - 06-48 KW - symmetry breaking KW - variable fixing KW - orbitopes Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9422 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 - Kaibel, Volker A1 - Pfetsch, Marc T1 - Packing and Partitioning Orbitopes N2 - We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal subject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain insight into ways of breaking certain symmetries in integer programs by adding constraints, e.g., for a well-known formulation of the graph coloring problem. We provide a thorough polyhedral investigation of packing and partitioning orbitopes for the cases in which the group acting on the columns is the cyclic group or the symmetric group. Our main results are complete linear inequality descriptions of these polytopes by facet-defining inequalities. For the cyclic group case, the descriptions turn out to be totally unimodular, while for the symmetric group case, both the description and the proof are more involved. The associated separation problems can be solved in linear time. T3 - ZIB-Report - 06-17 KW - integer programming KW - symmetry breaking KW - lexicographic representatives Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9104 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 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Pfetsch, Marc T1 - Public Transport to the fORe! N2 - Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question ``What is a good public transport network?. T3 - ZIB-Report - 05-22 KW - Public transport KW - vehicle scheduling KW - duty scheduling Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8562 UR - http://www.lionhrtpub.com/orms/orms-4-06/frtransport.html ER - TY - JOUR A1 - Le Bodic, P. A1 - Pfetsch, Marc A1 - Pavelka, J. A1 - Pokutta, Sebastian T1 - Solving MIPs via Scaling-based Augmentation JF - Discrete Optimization Y1 - 2018 N1 - Additional Note: doi: 10.1016/j.disopt.2017.08.004 N1 - URL of the PDF: http://dx.doi.org/10.1016/j.disopt.2017.08.004 VL - 27 SP - 1 EP - 25 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Pfetsch, Marc ED - Hickman, Mark ED - Mirchandani, Pitu ED - Voß, Stefan T1 - Models for Line Planning in Public Transport T2 - Computer-aided Systems in Public Transport (CASPT 2004) Y1 - 2008 U6 - https://doi.org/10.1007/978-3-540-73312-6_18 VL - 600 SP - 363 EP - 378 PB - Springer-Verlag ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Pfetsch, Marc T1 - A Column-Generation Approach to Line Planning in Public Transport JF - Transportation Science (INFORMS) Y1 - 2007 U6 - https://doi.org/10.1287/trsc.1060.0161 VL - 41 IS - 1 SP - 123 EP - 132 ER - TY - GEN A1 - Gamrath, Gerald A1 - Anderson, Daniel A1 - Bestuzheva, Ksenia A1 - Chen, Wei-Kun A1 - Eifler, Leon A1 - Gasse, Maxime A1 - Gemander, Patrick A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Halbig, Katrin A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Le Bodic, Pierre A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Miltenberger, Matthias A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Tawfik, Christine A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 7.0 N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders’ decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders’ decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP. T3 - ZIB-Report - 20-10 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78023 SN - 1438-0064 ER - TY - GEN A1 - Hendel, Gregor A1 - Anderson, Daniel A1 - Le Bodic, Pierre A1 - Pfetsch, Marc T1 - Estimating the Size of Branch-And-Bound Trees N2 - This paper investigates the estimation of the size of Branch-and-Bound (B&B) trees for solving mixed-integer programs. We first prove that the size of the B&B tree cannot be approximated within a factor of~2 for general binary programs, unless P equals NP. Second, we review measures of the progress of the B&B search, such as the gap, and propose a new measure, which we call leaf frequency. We study two simple ways to transform these progress measures into B&B tree size estimates, either as a direct projection, or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using Machine Learning techniques, which yields more precise estimates than any individual measure. The best method we have identified uses all individual measures as features of a random forest model. In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B&B tree sizes within a factor of 3 on the set of unseen test instances even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor 2 over the entire search on each out of six additional sets of homogeneous instances we have tested. All techniques are available in version 7 of the branch-and-cut framework SCIP. T3 - ZIB-Report - 20-02 KW - mixed integer programming KW - machine learning KW - branch and bound KW - forecasting Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-78144 SN - 1438-0064 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 - TY - GEN A1 - Gleixner, Ambros A1 - Eifler, Leon A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gemander, Patrick A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Viernickel, Jan Merlin A1 - Vigerske, Stefan A1 - Weninger, Dieter A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 5.0 N2 - This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG. T3 - ZIB-Report - 17-61 KW - constraint integer programming KW - linear programming KW - mixed-integer linear programming KW - mixed-integer nonlinear programming KW - optimization solver KW - branch-and-cut KW - branch-and-price KW - column generation framework KW - parallelization KW - mixed-integer semidefinite programming KW - Steiner tree optimization Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66297 SN - 1438-0064 ER - TY - JOUR A1 - Koch, Thorsten A1 - Schmidt, Martin A1 - Hiller, Benjamin A1 - Pfetsch, Marc A1 - Geißler, Björn A1 - Henrion, René A1 - Joormann, Imke A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Schewe, Lars A1 - Schultz, Rüdiger T1 - Capacity Evaluation for Large-Scale Gas Networks JF - German Success Stories in Industrial Mathematics Y1 - 2020 SN - 978-3-030-81454-0 U6 - https://doi.org/10.1007/978-3-030-81455-7 VL - 35 SP - 23 EP - 28 ER - TY - GEN A1 - Gleixner, Ambros A1 - Bastubbe, Michael A1 - Eifler, Leon A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Hojny, Christopher A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schlösser, Franziska A1 - Schubert, Christoph A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Viernickel, Jan Merlin A1 - Walter, Matthias A1 - Wegscheider, Fabian A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 6.0 N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders’ decomposition in a generic framework. GCG’s detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders’ framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP. T3 - ZIB-Report - 18-26 KW - constraint integer programming KW - linear programming KW - mixed-integer linear programming KW - mixed-integer nonlinear programming KW - optimization solver KW - branch-and-cut KW - branch-and-price KW - column generation framework KW - parallelization KW - mixed-integer semidefinite programming KW - Steiner tree optimization Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-69361 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Pfetsch, Marc T1 - Models for Line Planning in Public Transport N2 - The \emph{line planning problem} is one of the fundamental problems in strategic planning of public and rail transport. It consists of finding lines and corresponding frequencies in a public transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize its operating cost; the passengers request short travel times. We propose two new multi-commodity flow models for line planning. Their main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. T3 - ZIB-Report - 04-10 KW - line planning KW - column generation Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7854 ER - TY - GEN A1 - Pfetsch, Marc T1 - A Branch-And-Cut for the Maximum Feasible Subsystem Problem N2 - 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. T3 - ZIB-Report - 05-46 KW - infeasible linear inequality system KW - irreducible infeasible subsystem KW - (IIS) maximum feasible subsystem problem KW - minimum IIS-cover KW - branch-and-cut Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8797 ER - TY - GEN A1 - Harks, Tobias A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Competitive Online Multicommodity Routing N2 - We study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining the routing weights. We discuss an online algorithm that routes each commodity by minimizing a convex cost function that depends on the demands that are previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is $4K/2+K$-competitive, where $K$ is the number of commodities. For the parallel arc case this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably. T3 - ZIB-Report - 06-27 KW - Online Optimization KW - Routing KW - Telecommunications Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9212 ER - TY - GEN A1 - Harks, Tobias A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Competitive Online Multicommodity Routing N2 - In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably. T3 - ZIB-Report - 07-16 KW - Online Optimization KW - Routing KW - Telecommunications Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9599 ER -