TY - CHAP A1 - Bargmann, Dagmar A1 - Ebbers, Mirko A1 - Heinecke, Nina A1 - Koch, Thorsten A1 - Kühl, Veronika A1 - Pelzer, Antje A1 - Pfetsch, Marc A1 - Rövekamp, Jessica A1 - Spreckelsen, Klaus T1 - State-of-the-art in evaluating gas network capacities T2 - Evaluating Gas Network Capacities Y1 - 2015 SN - 9781611973686 SP - 65 EP - 84 PB - Society for Industrial and Applied Mathematics 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 - 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 - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc ED - Kullmann, Oliver T1 - Nonlinear pseudo-Boolean optimization T2 - Theory and Applications of Satisfiability Testing – SAT 2009 Y1 - 2009 VL - 5584 SP - 441 EP - 446 PB - Springer 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 - 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 - 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 - CHAP A1 - Berthold, Timo A1 - Pfetsch, Marc ED - Fleischmann, Bernhard ED - Borgwardt, Karl ED - Klein, Robert ED - Tuma, Axel T1 - Detecting Orbitopal Symmetries T2 - Operations Research Proceedings 2008 Y1 - 2009 SP - 433 EP - 438 PB - Springer-Verlag ER - TY - JOUR A1 - Bestuzheva, Ksenia A1 - Besançon, Mathieu A1 - Chen, Wei-Kun A1 - Chmiela, Antonia A1 - Donkiewicz, Tim A1 - Doornmalen, Jasper A1 - Eifler, Leon A1 - Gaul, Oliver A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - Hulst, Rolf A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Rehfeldt, Daniel A1 - Schlein, Steffan A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Sofranac, Boro A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Wellner, Philipp A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - Enabling research through the SCIP optimization suite 8.0 JF - ACM Transactions on Mathematical Software N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP. Y1 - 2023 U6 - https://doi.org/10.1145/3585516 VL - 49 IS - 2 SP - 1 EP - 21 ER - TY - GEN A1 - Bestuzheva, Ksenia A1 - Besançon, Mathieu A1 - Chen, Wei-Kun A1 - Chmiela, Antonia A1 - Donkiewicz, Tim A1 - van Doornmalen, Jasper A1 - Eifler, Leon A1 - Gaul, Oliver A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Gottwald, Leona A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - van der Hulst, Rolf A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Maher, Stephen J. A1 - Matter, Frederic A1 - Mühmer, Erik A1 - Müller, Benjamin A1 - Pfetsch, Marc E. A1 - Rehfeldt, Daniel A1 - Schlein, Steffan A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Sofranac, Boro A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Wegscheider, Fabian A1 - Wellner, Philipp A1 - Weninger, Dieter A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 8.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 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack. T3 - ZIB-Report - 21-41 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 KW - Parallelization KW - Mixed-integer semidefinite programming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85309 SN - 1438-0064 ER - TY - GEN A1 - Bolusani, Suresh A1 - Besançon, Mathieu A1 - Bestuzheva, Ksenia A1 - Chmiela, Antonia A1 - Dionísio, João A1 - Donkiewicz, Tim A1 - van Doornmalen, Jasper A1 - Eifler, Leon A1 - Ghannam, Mohammed A1 - Gleixner, Ambros A1 - Graczyk, Christoph A1 - Halbig, Katrin A1 - Hedtke, Ivo A1 - Hoen, Alexander A1 - Hojny, Christopher A1 - van der Hulst, Rolf A1 - Kamp, Dominik A1 - Koch, Thorsten A1 - Kofler, Kevin A1 - Lentz, Jurgen A1 - Manns, Julian A1 - Mexi, Gioni A1 - Mühmer, Erik A1 - E. Pfetsch, Marc A1 - Schlösser, Franziska A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Turner, Mark A1 - Vigerske, Stefan A1 - Weninger, Dieter A1 - Xu, Liding T1 - The SCIP Optimization Suite 9.0 N2 - The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver. T3 - ZIB-Report - 24-02-29 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 KW - Parallelization KW - Mixed-integer semidefinite programming Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-95528 SN - 1438-0064 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 - 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 - 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 - 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 - Public transport to the fORe JF - OR/MS Today Y1 - 2006 UR - http://www.lionhrtpub.com/orms/orms-4-06/frtransport.html SP - 30 EP - 40 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 - 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 -