@misc{MasingLindnerBorndoerfer2022, author = {Masing, Berenike and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {The Price of Symmetric Line Plans in the Parametric City}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2201.09756}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85648}, year = {2022}, abstract = {We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. The symmetry gap is provably small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations.}, language = {en} } @misc{Masing2021, author = {Masing, Berenike}, title = {Optimal Line Planning in the Parametric City}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83238}, year = {2021}, abstract = {We formulate the line planning problem in public transport as a mixed integer linear program (MILP), which selects both passenger and vehicle routes, such that travel demands are met with respect to minimized travel times for both operators and users. We apply MILP to the Parametric City, a generic city model developed by Fielbaum et al. While the infrastructure graph and demand are entirely rotation symmetric, asymmetric optimal line plans can occur. Using group theory, we analyze the properties of symmetric solutions and introduce a symmetry gap to measure their deviation of the optimum. We also develop a 1+(1+\sqrt{2})/g-approximation algorithm, depending only on the cost related parameter g. Supported by computational experiments, we conclude that in practice symmetric line plans provide good solutions for the line planning problem in the Parametric City.}, language = {en} } @misc{HendelAndersonLeBodicetal.2020, author = {Hendel, Gregor and Anderson, Daniel and Le Bodic, Pierre and Pfetsch, Marc}, title = {Estimating the Size of Branch-And-Bound Trees}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78144}, year = {2020}, abstract = {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.}, language = {en} } @misc{WitzigBerthold2019, author = {Witzig, Jakob and Berthold, Timo}, title = {Conflict-Free Learning for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/978-3-030-58942-4_34}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75338}, year = {2019}, abstract = {Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search. We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set.}, language = {en} } @misc{GrimmBorndoerferSchlechte2019, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73976}, year = {2019}, abstract = {Planning rolling stock movements in industrial passenger railway applications isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for the ICE high speed fleet of DB Fernverkehr AG one of the largest passenger railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended.}, language = {en} } @misc{BertholdGamrathSalvagnin2019, author = {Berthold, Timo and Gamrath, Gerald and Salvagnin, Domenico}, title = {Exploiting Dual Degeneracy in Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73028}, year = {2019}, abstract = {Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 \% on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 \% on average.}, language = {en} } @misc{Hendel2018, author = {Hendel, Gregor}, title = {Adaptive Large Neighborhood Search for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71167}, year = {2018}, abstract = {Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP.}, language = {en} } @misc{HendelMiltenbergerWitzig2018, author = {Hendel, Gregor and Miltenberger, Matthias and Witzig, Jakob}, title = {Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69563}, year = {2018}, abstract = {State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the \scip Optimization Suite on publicly available MIP instances.}, language = {en} } @misc{GeorgesGleixnerGojicetal.2018, author = {Georges, Alexander and Gleixner, Ambros and Gojic, Gorana and Gottwald, Robert Lion and Haley, David and Hendel, Gregor and Matejczyk, Bartlomiej}, title = {Feature-Based Algorithm Selection for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68362}, year = {2018}, abstract = {Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance. In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out. We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented.}, language = {en} } @misc{BertholdPerregaardMeszaros2017, author = {Berthold, Timo and Perregaard, Michael and M{\´e}sz{\´a}ros, Csaba}, title = {Four good reasons to use an Interior Point solver within a MIP solver}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_22}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64599}, year = {2017}, abstract = {"Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex." This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation.}, language = {en} } @misc{GottwaldMaherShinano2016, author = {Gottwald, Robert Lion and Maher, Stephen J. and Shinano, Yuji}, title = {Distributed domain propagation}, issn = {1438-0064}, doi = {10.4230/LIPIcs.SEA.2017.6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61380}, year = {2016}, abstract = {Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.}, language = {en} } @phdthesis{Berthold2014, author = {Berthold, Timo}, title = {Heuristic algorithms in global MINLP solvers}, publisher = {Dr. Hut Verlag}, isbn = {978-3-8439-1931-9}, pages = {366}, year = {2014}, abstract = {In the literature for mixed integer programming, heuristic algorithms (particularly primal heuristics) are often considered as stand-alone procedures; in that context, heuristics are treated as an alternative to solving a problem to proven optimality. This conceals the fact that heuristic algorithms are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP). In the present thesis, we focus on this latter aspect; we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are: - Shift-and-Propagate, a novel propagation heuristic for MIP that does not require the solution to an LP relaxation, - a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP, - an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures, - RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution, - Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP, - Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs, - Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection. Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics on six test sets with altogether 983 instances from academic and industrial sources, including our project partners ForNe, SAP, and Siemens. We observe that heuristics improve the solver performance regarding all measures that we used - by different orders of magnitude. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes. The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have also been re-implemented within several commercial and noncommercial MIP and MINLP software packages, including Bonmin, CBC, Cplex, Gams, Sulum, and Xpress.}, language = {en} } @misc{ShinanoHeinzVigerskeetal.2013, author = {Shinano, Yuji and Heinz, Stefan and Vigerske, Stefan and Winkler, Michael}, title = {FiberSCIP - A shared memory parallelization of SCIP}, issn = {1438-0064}, doi = {10.1287/ijoc.2017.0762}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42595}, year = {2013}, abstract = {Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.}, language = {en} } @misc{Berthold2013, author = {Berthold, Timo}, title = {Measuring the impact of primal heuristics}, issn = {1438-0064}, doi = {10.1016/j.orl.2013.08.007}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17887}, year = {2013}, abstract = {In modern MIP solvers, primal heuristics play a major role in finding and improving feasible solutions early in the solution process. However, classical performance measures such as time to optimality or number of branch-and-bound nodes reflect the impact of primal heuristics on the overall solving process badly. This article discusses the question of how to evaluate the effect of primal heuristics. Therefore, we introduce a new performance measure, the "primal integral" which depends on the quality of solutions found during the solving process as well as on the points in time when they are found. Our computational results reveal that heuristics improve the performance of MIP solvers in terms of the primal bound by around 80\%. Further, we compare five state-of-the-art MIP solvers w.r.t. the newly proposed measure.}, language = {en} } @misc{HeinzKuBeck2013, author = {Heinz, Stefan and Ku, Wen-Yang and Beck, J. Christopher}, title = {Recent improvements using constraint integer programming for resource allocation and scheduling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17676}, year = {2013}, abstract = {Recently, we compared the performance of mixed-integer programming (MIP), constraint programming (CP), and constraint integer programming (CIP) to a state-of-the-art logic-based Benders manual decomposition (LBBD) for a resource allocation/scheduling problem. For a simple linear relaxation, the LBBD and CIP models deliver comparable performance with MIP also performing well. Here we show that algorithmic developments in CIP plus the use of an existing tighter relaxation substantially improve one of the CIP approaches. Furthermore, the use of the same relaxation in LBBD and MIP models significantly improves their performance. While such a result is known for LBBD, to the best of our knowledge, the other results are novel. Our experiments show that both CIP and MIP approaches are competitive with LBBD in terms of the number of problems solved to proven optimality, though MIP is about three times slower on average. Further, unlike the LBBD and CIP approaches, the MIP model is able to obtain provably high-quality solutions for all problem instances.}, language = {en} } @misc{BertholdHendel2013, author = {Berthold, Timo and Hendel, Gregor}, title = {Shift-And-Propagate}, issn = {1438-0064}, doi = {10.1007/s10732-014-9271-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17596}, year = {2013}, abstract = {For mixed integer programming, recent years have seen a growing interest in the design of general purpose primal heuristics for use inside complete solvers. Many of these heuristics rely on an optimal LP solution. Finding this may itself take a significant amount of time. The presented paper addresses this issue by the introduction of the Shift-And-Propagate heuristic. Shift-And-Propagate is a pre-root primal heuristic that does not require a previously found LP solution. It applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement of existing rounding and propagation heuristics.}, language = {en} } @misc{BertholdSalvagnin2013, author = {Berthold, Timo and Salvagnin, Domenico}, title = {Cloud branching}, issn = {1438-0064}, doi = {10.1007/978-3-642-38171-3_3}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17301}, year = {2013}, abstract = {Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud) of the current LP relaxation. These strategies naturally extend state-of-the-art methods like strong branching, pseudocost branching, and their hybrids. We show that by exploiting dual degeneracy, and thus multiple alternative optimal solutions, it is possible to enhance traditional methods. We present preliminary computational results, applying the newly proposed strategy to full strong branching, which is known to be the MIP branching rule leading to the fewest number of search nodes. It turns out that cloud branching can reduce the mean running time by up to 30\% on standard test sets.}, language = {en} } @misc{HeinzBeck2012, author = {Heinz, Stefan and Beck, J. Christopher}, title = {Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14660}, number = {12-05}, year = {2012}, abstract = {Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade. We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models, which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP are technologies that should be considered along with CP for solving scheduling problems.}, language = {en} } @misc{AchterbergBertholdHendel2011, author = {Achterberg, Tobias and Berthold, Timo and Hendel, Gregor}, title = {Rounding and Propagation Heuristics for Mixed Integer Programming}, doi = {10.1007/978-3-642-29210-1_12}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13255}, number = {11-29}, year = {2011}, abstract = {Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances.}, language = {en} } @misc{HeinzBeck2011, author = {Heinz, Stefan and Beck, J. Christopher}, title = {Solving Resource Allocation/Scheduling Problems with Constraint Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12691}, number = {11-14}, year = {2011}, abstract = {Constraint Integer Programming (CIP) is a generalization of mixed-integer programming (MIP) in the direction of constraint programming (CP) allowing the inference techniques that have traditionally been the core of \P to be integrated with the problem solving techniques that form the core of complete MIP solvers. In this paper, we investigate the application of CIP to scheduling problems that require resource and start-time assignments to satisfy resource capacities. The best current approach to such problems is logic-based Benders decomposition, a manual decomposition method. We present a CIP model and demonstrate that it achieves performance competitive to the decomposition while out-performing the standard MIP and CP formulations.}, language = {en} } @misc{SteffyWolter2011, author = {Steffy, Daniel and Wolter, Kati}, title = {Valid Linear Programming Bounds for Exact Mixed-Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12332}, number = {11-08}, year = {2011}, abstract = {Fast computation of valid linear programming (LP) bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for this application. The algorithm corrects approximate LP dual solutions to be exactly feasible, giving a valid bound. Solutions are repaired by performing a projection and a shift to ensure all constraints are satisfied; bound computations are accelerated by reusing structural information through the branch-and-bound tree. We demonstrate this method to be widely applicable and faster than solving a sequence of exact LPs. Several variations of the algorithm are described and computationally evaluated in an exact branch-and-bound algorithm within the mixed-integer programming framework SCIP.}, language = {en} } @misc{CookKochSteffyetal.2011, author = {Cook, William and Koch, Thorsten and Steffy, Daniel and Wolter, Kati}, title = {An Exact Rational Mixed-Integer Programming Solver}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12329}, number = {11-07}, year = {2011}, abstract = {We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann collections.}, language = {en} } @misc{ShinanoAchterbergBertholdetal.2010, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten}, title = {ParaSCIP - a parallel extension of SCIP}, doi = {10.1007/978-3-642-24025-6_12}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11921}, number = {10-27}, year = {2010}, abstract = {Mixed integer programming (MIP) has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branch-and-bound procedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN~II supercomputer.}, language = {en} } @misc{AchterbergRaack2009, author = {Achterberg, Tobias and Raack, Christian}, title = {The MCF-Separator -- Detecting and Exploiting Multi-Commodity Flow Structures in MIPs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11592}, number = {09-38}, year = {2009}, abstract = {Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity-flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems by a factor of two on average.}, language = {en} } @misc{AchterbergBertholdHeinzetal.2008, author = {Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Wolter, Kati}, title = {Constraint Integer Programming: Techniques and Applications}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10950}, number = {08-43}, year = {2008}, abstract = {This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.}, language = {en} } @misc{Kinder2008, type = {Master Thesis}, author = {Kinder, Mathias}, title = {Models for Periodic Timetabling}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10887}, school = {Zuse Institute Berlin (ZIB)}, year = {2008}, abstract = {We investigate the computation of periodic timetables for public transport by mixed integer programming. After introducing the problem, we describe two mathematical models for periodic timetabling, the PERIODIC EVENT SCHEDULING PROBLEM (PESP) and the QUADRATIC SEMI-ASSIGNMENT PROBLEM. Specifically, we give an overview of existing integer programming (IP) formulations for both models. An important contribution of our work are new IP formulations for the PESP based on time discretization. We provide an analytical comparison of these formulations and describe different techniques that allow a more efficient solution by mixed integer programming. In a preliminary computational study, on the basis of standard IP solvers, we compare different formulations for computing periodic timetables. Our results justify a further investigation of the time discretization approach. Typically the timetable is optimized for the current traffic situation. The main difficulty with this approach is that after introducing the new timetable the passengers' travel behavior may differ from that assumed for the computation. Motivated by this problem, we examine an iterative timetabling procedure that is a combination of timetable computation and passenger routing. We discuss the algorithmic issues of the passenger routing and study properties of the computed timetables. Finally, we confirm our theoretical results on the basis of an own implementation.}, language = {en} } @misc{AchterbergBertholdKochetal.2008, author = {Achterberg, Tobias and Berthold, Timo and Koch, Thorsten and Wolter, Kati}, title = {Constraint Integer Programming: a New Approach to Integrate CP and MIP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10520}, number = {08-01}, year = {2008}, abstract = {This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving. SCIP is available in source code and free for non-commercial use. We demonstrate the usefulness of CIP on two tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.}, language = {en} } @misc{Berthold2007, author = {Berthold, Timo}, title = {Heuristics of the Branch-Cut-and-Price-Framework SCIP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10280}, number = {07-30}, year = {2007}, abstract = {In this paper we give an overview of the heuristics which are integrated into the open source branch-cut-and-price-framework SCIP. We briefly describe the fundamental ideas of different categories of heuristics and present some computational results which demonstrate the impact of heuristics on the overall solving process of SCIP.}, language = {en} } @misc{Berthold2007, author = {Berthold, Timo}, title = {RENS - Relaxation Enforced Neighborhood Search}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4264}, number = {07-28}, year = {2007}, abstract = {In the recent years, a couple of quite successful large neighborhood search heuristics for mixed integer programs has been published. Up to our knowledge, all of them are improvement heuristics. We present a new start heuristic for general MIPs working in the spirit of large neighborhood search. It constructs a sub-MIP which represents the space of all feasible roundings of some fractional point - normally the optimum of the LP-relaxation of the original MIP. Thereby, one is able to determine whether a point can be rounded to a feasible solution and which is the best possible rounding. Furthermore, a slightly modified version of RENS proves to be a well-performing heuristic inside the branch-cut-and-price-framework SCIP.}, language = {en} } @misc{RaackKosterWessaely2007, author = {Raack, Christian and Koster, Arie M.C.A. and Wess{\"a}ly, Roland}, title = {On the strength of cut-based inequalities for capacitated network design polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9512}, number = {07-08}, year = {2007}, abstract = {In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show that facets of the resulting cutset polyhedra translate into facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Second, we provide an analysis of the facial structure of cutset polyhedra, elaborating the differences caused by the three different types of capacity constraints. We present flow-cutset inequalities for all three models and show under which conditions these are facet-defining. We also state a new class of facets for the bidirected and undirected case and it is shown how to handle multiple capacity modules by Mixed Integer Rounding (MIR).}, language = {en} } @misc{AchterbergBerthold2005, author = {Achterberg, Tobias and Berthold, Timo}, title = {Improving the Feasibility Pump}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8754}, number = {05-42}, year = {2005}, abstract = {The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump.}, language = {en} } @misc{Achterberg2005, author = {Achterberg, Tobias}, title = {Conflict Analysis in Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8537}, number = {05-19}, year = {2005}, abstract = {Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers to cope with large real-world instances. In contrast, it is common practice for today's mixed integer programming solvers to just discard infeasible subproblems and the information they reveal. In this paper we try to remedy this situation by generalizing the SAT infeasibility analysis to mixed integer programming. We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting cuts. We performed computational experiments which show the potential of our method: On feasible MIP instances, the number of required branching nodes was reduced by 50\\% in the geometric mean. However, the total solving time increased by 15\\%. on infeasible MIPs arising in the context of chip verification, the number of nodes was reduced by 90\\%, thereby reducing the solving time by 60\\%.}, language = {en} } @misc{EisenblaetterFuegenschuhKochetal.2002, author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Koch, Thorsten and Koster, Arie M.C.A. and Martin, Alexander and Pfender, Tobias and Wegel, Oliver and Wess{\"a}ly, Roland}, title = {Modelling Feasible Network Configurations for UMTS}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6837}, number = {02-16}, year = {2002}, abstract = {A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations.}, language = {en} } @misc{HoeselKosterLeenseletal.2000, author = {Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Leensel, Robert L.M.J. van de and Savelsbergh, Martin W.P.}, title = {Polyhedral Results for the Edge Capacity Polytope}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5907}, number = {00-22}, year = {2000}, abstract = {Network loading problems occur in the design of telecommunication networks, in many different settings. The polyhedral structure of this problem is important in developing solution methods for the problem. In this paper we investigate the polytope of the problem restricted to one edge of the network (the edge capacity problem). We describe classes of strong valid inequalities for the edge capacity polytope, and we derive conditions under which these constraints define facets. As the edge capacity problem is a relaxation of the network loading problem, their polytopes are intimately related. We, therefore, also give conditions under which the inequalities of the edge capacity polytope define facets of the network loading polytope. Furthermore, some structural properties are derived, such as the relation of the edge capacity polytope to the knapsack polytope. We conclude the theoretical part of this paper with some lifting theorems, where we show that this problem is polynomially solvable for most of our classes of valid inequalities. In a computational study the quality of the constraints is investigated. Here, we show that the valid inequalities of the edge capacity polytope are not only important for solving the edge capacity problem, but also for the network loading problem, showing that the edge capacity problem is an important subproblem.}, language = {en} }