@misc{RalphsShinanoBertholdetal.2016, author = {Ralphs, Ted and Shinano, Yuji and Berthold, Timo and Koch, Thorsten}, title = {Parallel Solvers for Mixed Integer Linear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62239}, year = {2016}, abstract = {In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures.}, language = {en} } @misc{AchterbergBixbyGuetal.2016, author = {Achterberg, Tobias and Bixby, Robert E. and Gu, Zonghao and Rothberg, Edward and Weninger, Dieter}, title = {Presolve Reductions in Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60370}, year = {2016}, abstract = {Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. A critical component in the solution of these mixed-integer programs is a set of routines commonly referred to as presolve. Presolve can be viewed as a collection of preprocessing techniques that reduce the size of and, more importantly, improve the ``strength'' of the given model formulation, that is, the degree to which the constraints of the formulation accurately describe the underlying polyhedron of integer-feasible solutions. As our computational results will show, presolve is a key factor in the speed with which we can solve mixed-integer programs, and is often the difference between a model being intractable and solvable, in some cases easily solvable. In this paper we describe the presolve functionality in the Gurobi commercial mixed-integer programming code. This includes an overview, or taxonomy of the different methods that are employed, as well as more-detailed descriptions of several of the techniques, with some of them appearing, to our knowledge, for the first time in the literature.}, language = {en} } @misc{LeitnerLjubicSinnletal.2015, author = {Leitner, Markus and Ljubic, Ivana and Sinnl, Markus and Werner, Axel}, title = {Two algorithms for solving 3-objective k-ArchConFL and IPs in general}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56259}, year = {2015}, abstract = {We present two algorithms to solve a 3-objective optimization problem arising in telecommunications access network planning, the k-Architecture Connected Facility Location Problem. The methods can also be used to solve any 3-objective integer linear programming model and can be extended to the multiobjective case. We give some exemplary computations using small and medium-sized instances for our problem.}, language = {en} } @misc{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Metric Inequalities for Routings on Direct Connections with Application in Line Planning}, issn = {1438-0064}, doi = {10.1016/j.disopt.2015.07.004}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53507}, year = {2015}, abstract = {We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows. The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.}, language = {en} } @misc{BorndoerferSagnolSchlechteetal.2013, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar}, title = {Optimal Toll Enforcement - an Integration of Vehicle Routing and Duty Rostering}, issn = {1438-0064}, doi = {10.1007/s10479-016-2152-1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-45107}, year = {2013}, abstract = {We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method.}, language = {en} } @phdthesis{Raack2012, author = {Raack, Christian}, title = {Capacitated Network Design - Multi-Commodity Flow Formulations, Cutting Planes, and Demand Uncertainty}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:83-opus-36167}, school = {Technische Universit{\"a}t Berlin}, year = {2012}, abstract = {In this thesis, we develop methods in mathematical optimization to dimension networks at minimal cost. Given hardware and cost models, the challenge is to provide network topologies and efficient capacity plans that meet the demand for network traffic (data, passengers, freight). We incorporate crucial aspects of practical interest such as the discrete structure of available capacities as well as the uncertainty of demand forecasts. The considered planning problems typically arise in the strategic design of telecommunication or public transport networks and also in logistics. One of the essential aspects studied in this work is the use of cutting planes to enhance solution approaches based on multi-commodity flow formulations. Providing theoretical and computational evidence for the efficacy of inequalities based on network cuts, we extend existing theory and algorithmic work in different directions. First, we prove that special-purpose techniques, originally designed to solve capacitated network design problems, can be successfully integrated into general-purpose mixed integer programming (MIP) solvers. Our approach relies on an automatic detection of network structure within the constraint matrix of general mixed in teger programs. More precisely, we identify multi-commodity (MCF) network sub-matrices and resolve the isomorphisms of the commodity blocks as well as the original graph structure. In the subsequent separation framework, we guide the constraint aggregation of available cutting plane procedures (e. g. based on mixed integer rounding) to produce strong cutting planes that reflect the structure of the constructed network. The new MCF-separator integrates network design specific methodology into general optimization tools which is of particular importance for practitioners that tend to use MIP solvers as black boxes. Extensive computational tests show that our network detection procedure operates accurately and reliably. Moreover, due to the generated cutting planes, we achieve an average speed-up of a factor of two for pure network design problems with general MIP solvers. Many of these instances can only be solved to optimality in reasonable time if the new MCF-separator is active. In 9 \% of the instances of general MIP test sets we find consistent embedded networks and generate violated inequalities. In this case the computation time decreases by 18 \% on average with almost no degradation for unaffected instances. Second, we generalize concepts, models, and cutting planes from deterministic network design to robust network design, incorporating the uncertainty of traffic demands. We enhance and compare strategies that are able to handle a polyhedral set of different traffic scenarios. In particular, we consider two correlated solution methods, based on separating extreme demand scenarios and dualizing the linear description of the demand polytope, respectively. We consider robust network design as two-stage robust optimization with recourse. First stage capacity decisions are fixed for all scenarios while the second stage flow depends on the realized demands. In order to reroute the traffic as a function of the demand dynamics, we consider three alternative recourse actions, namely, static, affine, and dynamic routing. We analyze properties of the new affine routing and show that it combines advantages of the well-known static and dynamic models. Using the concept of robust cut-set polyhedra and the corresponding lifting theorems, we develop several classes of facet-defining inequalities based on network cuts that can be used to further accelerate solution strategies for robust network design. Among them are the well-known (flow) cut-set inequalities, which we generalize to general demand polytopes, but also new classes of potential cutting planes, so-called envelope inequalities. The practical importance of the developed cutting planes is revealed by a series of computational tests. Similar to the results for the MCF-separator we achieve speed-ups of two and more using the generalized classes of strong inequalities. To evaluate the robustness of solutions that are computed with our framework we use real-life measurements of traffic dynamics from different existing telecommunication networks, among them data from the German and the European research network. Our results indicate that traffic peaks do not necessarily occur all simultaneously with respect to different source-destination pairs, which is of practical importance for the design of uncertainty sets. It is, in particular, not necessary to dimension networks for a scenario that assumes all source-destination traffic is at its peak simultaneously. With our solutions we save up to 20 \% of the corresponding solution cost compared to this artificial scenario and achieve comparable levels of robustness.}, language = {en} } @misc{RaackRaymondWerneretal.2013, author = {Raack, Christian and Raymond, Annie and Werner, Axel and Schlechte, Thomas}, title = {Integer Programming and Sports Rankings}, issn = {1438-0064}, doi = {10.1515/jqas-2013-0111}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18068}, year = {2013}, abstract = {Sports rankings are obtained by applying a system of rules to evaluate the performance of the participants in a competition. We consider rankings that result from assigning an ordinal rank to each competitor according to their performance. We develop an integer programming model for rankings that allows us to calculate the number of points needed to guarantee a team the ith position, as well as the minimum number of points that could yield the ith place. The model is very general and can thus be applied to many types of sports. We discuss examples coming from football (soccer), ice hockey, and Formula~1. We answer various questions and debunk a few myths along the way. Are 40 points enough to avoid relegation in the Bundesliga? Do 95 points guarantee the participation of a team in the NHL playoffs? Moreover, in the season restructuration currently under consideration in the NHL, will it be easier or harder to access the playoffs? Is it possible to win the Formula~1 World Championship without winning at least one race or without even climbing once on the podium? Finally, we observe that the optimal solutions of the aforementioned model are associated to extreme situations which are unlikely to happen. Thus, to get closer to realistic scenarios, we enhance the model by adding some constraints inferred from the results of the previous years.}, language = {en} } @misc{BorndoerferKarbstein2012, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {A Direct Connection Approach to Integrated Line Planning and Passenger Routing}, volume = {25}, journal = {ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Delling, Daniel and Liberti, Leo}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, issn = {1438-0064}, doi = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2012.47}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15812}, pages = {47 -- 57}, year = {2012}, abstract = {The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.}, language = {en} } @misc{HeinzSchlechteStephanetal.2011, author = {Heinz, Stefan and Schlechte, Thomas and Stephan, R{\"u}diger and Winkler, Michael}, title = {Solving steel mill slab design problems}, issn = {1438-0064}, doi = {10.1007/s10601-011-9113-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14089}, number = {11-38}, year = {2011}, abstract = {The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results. Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality.}, language = {en} } @misc{BorndoerferNeumann2010, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika}, title = {Models for Line Planning with Transfers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11742}, number = {10-11}, year = {2010}, abstract = {We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by "connection capacities" into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results.}, language = {en} } @misc{BertholdFeydyStuckey2010, author = {Berthold, Timo and Feydy, Thibaut and Stuckey, Peter}, title = {Rapid Learning for Binary Programs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11663}, number = {10-04}, year = {2010}, abstract = {Learning during search allows solvers for discrete optimization problems to remember parts of the search that they have already performed and avoid revisiting redundant parts. Learning approaches pioneered by the SAT and CP communities have been successfully incorporated into the SCIP constraint integer programming platform. In this paper we show that performing a heuristic constraint programming search during root node processing of a binary program can rapidly learn useful nogoods, bound changes, primal solutions, and branching statistics that improve the remaining IP search.}, language = {en} } @misc{BorndoerferCardonha2009, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Set Partitioning Approach to Shunting}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11326}, number = {09-18}, year = {2009}, abstract = {The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems.}, language = {en} } @misc{HeinzStephanSchlechte2009, author = {Heinz, Stefan and Stephan, R{\"u}diger and Schlechte, Thomas}, title = {Solving Steel Mill Slab Problems with Branch and Price}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11260}, number = {09-14}, year = {2009}, abstract = {The steel mill slab design problem from the CSPLib is a binpacking problem that is motivated by an application of the steel industry and that has been widely studied in the constraint programming community. Recently, several people proposed new models and methods to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called multiple knapsack problem with color constraints, originated from the same industrial problem, were discussed in the integer programming community. In particular, a simple integer programming for this problem has been given by Forrest et al. [3]. The aim of this paper is to bring these different studies together. Moreover, we adopt the model of [3] for the steel mill slab problem. Using a state of the art integer program solver, this model is capable to solve all instances of the steel mill slab library, mostly in less than one second, to optimality. We improved, thereby, the solution value of 76 instances.}, language = {en} } @misc{BorndoerferGroetschelJaeger2009, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Jaeger, Ulrich}, title = {Planning Problems in Public Transit}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11252}, number = {09-13}, year = {2009}, abstract = {Every day, millions of people are transported by buses, trains, and airplanes in Germany. Public transit (PT) is of major importance for the quality of life of individuals as well as the productivity of entire regions. Quality and efficiency of PT systems depend on the political framework (state-run, market oriented) and the suitability of the infrastructure (railway tracks, airport locations), the existing level of service (timetable, flight schedule), the use of adequate technologies (information, control, and booking systems), and the best possible deployment of equipment and resources (energy, vehicles, crews). The decision, planning, and optimization problems arising in this context are often gigantic and "scream" for mathematical support because of their complexity. This article sketches the state and the relevance of mathematics in planning and operating public transit, describes today's challenges, and suggests a number of innovative actions. The current contribution of mathematics to public transit is — depending on the transportation mode — of varying depth. Air traffic is already well supported by mathematics. Bus traffic made significant advances in recent years, while rail traffic still bears significant opportunities for improvements. In all areas of public transit, the existing potentials are far from being exhausted. For some PT problems, such as vehicle and crew scheduling in bus and air traffic, excellent mathematical tools are not only available, but used in many places. In other areas, such as rolling stock rostering in rail traffic, the performance of the existing mathematical algorithms is not yet sufficient. Some topics are essentially untouched from a mathematical point of view; e.g., there are (except for air traffic) no network design or fare planning models of practical relevance. PT infrastructure construction is essentially devoid of mathematics, even though enormous capital investments are made in this area. These problems lead to questions that can only be tackled by engineers, economists, politicians, and mathematicians in a joint effort. Among other things, the authors propose to investigate two specific topics, which can be addressed at short notice, are of fundamental importance not only for the area of traffic planning, should lead to a significant improvement in the collaboration of all involved parties, and, if successful, will be of real value for companies and customers: • discrete optimal control: real-time re-planning of traffic systems in case of disruptions, • model integration: service design in bus and rail traffic. Work on these topics in interdisciplinary research projects could be funded by the German ministry of research and education (BMBF), the German ministry of economics (BMWi), or the German science foundation (DFG).}, language = {en} } @misc{BorndoerferCardonha2009, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Binary Quadratic Programming Approach to the Vehicle Positioning Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11242}, number = {09-12}, year = {2009}, abstract = {The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view.}, language = {en} } @misc{TorresTorresBorndoerferetal.2008, author = {Torres, Luis Miguel and Torres, Ramiro and Bornd{\"o}rfer, Ralf and Pfetsch, Marc}, title = {Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System (Extended Abstract)}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11076}, number = {08-53}, year = {2008}, abstract = {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.}, language = {en} } @misc{TorresTorresBorndoerferetal.2008, author = {Torres, Luis Miguel and Torres, Ramiro and Bornd{\"o}rfer, Ralf and Pfetsch, Marc}, title = {Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System}, organization = {ZIB}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10869}, number = {08-35}, year = {2008}, abstract = {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.}, language = {en} } @misc{BertholdPfetsch2008, author = {Berthold, Timo and Pfetsch, Marc}, title = {Detecting Orbitopal Symmetries}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10842}, number = {08-33}, year = {2008}, abstract = {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.}, language = {en} } @misc{BertholdHeinzPfetsch2008, author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc}, title = {Solving Pseudo-Boolean Problems with SCIP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10671}, number = {08-12}, year = {2008}, abstract = {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.}, language = {en} } @misc{AchterbergHeinzKoch2008, author = {Achterberg, Tobias and Heinz, Stefan and Koch, Thorsten}, title = {Counting solutions of integer programs using unrestricted subtree detection}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10632}, number = {08-09}, year = {2008}, abstract = {In the recent years there has been tremendous progress in the development of algorithms to find optimal solutions for integer programs. In many applications it is, however, desirable (or even necessary) to generate all feasible solutions. Examples arise in the areas of hardware and software verification and discrete geometry. In this paper, we investigate how to extend branch-and-cut integer programming frameworks to support the generation of all solutions. We propose a method to detect so-called unrestricted subtrees, which allows us to prune the integer program search tree and to collect several solutions simultaneously. We present computational results of this branch-and-count paradigm which show the potential of the unrestricted subtree detection.}, language = {en} }