@misc{BorndoerferFerreiraMartin1997, author = {Bornd{\"o}rfer, Ralf and Ferreira, Carlos E. and Martin, Alexander}, title = {Decomposing Matrices into Blocks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2849}, number = {SC-97-15}, year = {1997}, abstract = {In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix \$A\$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.}, language = {en} } @misc{AscheuerJuengerReinelt1997, author = {Ascheuer, Norbert and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {A Branch \& Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3391}, number = {SC-97-70}, year = {1997}, abstract = {In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch\&-cut algorithm and give computational results on real world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch\&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time.}, language = {en} } @misc{BorndoerferGroetschelKlostermeieretal.1997, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Klostermeier, Fridolin and K{\"u}ttner, Christian}, title = {Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System}, doi = {10.1007/978-3-642-85970-0_19}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2925}, number = {SC-97-23}, year = {1997}, abstract = {{\em Telebus\/} is Berlin's dial-a-ride system for handicapped people that cannot use the public transportation system. The service is provided by a fleet of about 100 mini-busses and includes aid to get in and out of the vehicle. Telebus has between 1,000 and 1,500 transportation requests per day. The problem arises to schedule these requests into the vehicles such that punctual service is provided while operation costs should be minimum. Additional constraints include pre-rented vehicles, fixed bus driver shift lengths, obligatory breaks, and different vehicle capacities. We use a {\em set partitioning\/} approach for the solution of the bus scheduling problem that consists of two steps. The first {\em clustering\/} step identifies segments of possible bus tours (``orders'') such that more than one person is transported at a time; the aim in this step is to reduce the size of the problem and to make use of larger vehicle capacities. The problem to select a set of orders such that the traveling distance of the vehicles within the orders is minimal is a set partitioning problem that we can solve to optimality. In the second step the selected orders are {\em chained\/} to yield possible bus tours respecting all side constraints. The problem to select a set of such bus tours such that each order is serviced once and the total traveling distance of the vehicles is minimum is again a set partitioning problem that we solve approximately. We have developed a computer system for the solution of the bus scheduling problem that includes a branch-and-cut algorithm for the solution of the set partitioning problems. A version of this system is in operation at Telebus since July 1995. Its use made it possible that Telebus can service today about 30\\% more requests per day for the same amount of money than before.}, language = {en} } @misc{BorndoerferWeismantel1997, author = {Bornd{\"o}rfer, Ralf and Weismantel, Robert}, title = {Set Packing Relaxations of Some Integer Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2998}, number = {SC-97-30}, year = {1997}, abstract = {This paper is about {\em set packing relaxations\/} of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and vertex packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation.}, language = {en} } @misc{BorndoerferWeismantel1997, author = {Bornd{\"o}rfer, Ralf and Weismantel, Robert}, title = {Discrete Relaxations of Combinatorial Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3230}, number = {SC-97-54}, year = {1997}, abstract = {This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code.}, language = {en} } @misc{BorndoerferGroetschelKlostermeieretal.1997, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Klostermeier, Fridolin and K{\"u}ttner, Christian}, title = {Optimierung des Berliner Behindertenfahrdienstes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2799}, number = {SC-97-10}, year = {1997}, abstract = {In diesem Artikel geben wir einen {\"U}berblick {\"u}ber das Telebus-Projekt am Konrad-Zuse-Zentrum, Berlin, durch das der Behindertenfahrdienst in Berlin reorganisiert und optimiert wurde. Wir berichten kurz {\"u}ber die mathematischen Probleme und, etwas ausf{\"u}hrlicher, {\"u}ber die nicht-mathematischen Schwierigkeiten, die bei der Durchf{\"u}hrung dieses Projektes auftraten.}, language = {de} } @inproceedings{PrauseBorndoerfer2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {A Bayesian Rolling Horizon Approach for Rolling Stock Rotation Planning with Predictive Maintenance}, volume = {123}, booktitle = {24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)}, doi = {10.4230/OASIcs.ATMOS.2024.13}, pages = {13:1 -- 13:19}, year = {2024}, abstract = {We consider the rolling stock rotation planning problem with predictive maintenance (RSRP-PdM), where a timetable given by a set of trips must be operated by a fleet of vehicles. Here, the health states of the vehicles are assumed to be random variables, and their maintenance schedule should be planned based on their predicted failure probabilities. Utilizing the Bayesian update step of the Kalman filter, we develop a rolling horizon approach for RSRP-PdM, in which the predicted health state distributions are updated as new data become available. This approach reduces the uncertainty of the health states and thus improves the decision-making basis for maintenance planning. To solve the instances, we employ a local neighborhood search, which is a modification of a heuristic for RSRP-PdM, and demonstrate its effectiveness. Using this solution algorithm, the presented approach is compared with the results of common maintenance strategies on test instances derived from real-world timetables. The obtained results show the benefits of the rolling horizon approach.}, language = {en} } @article{BestuzhevaChmielaMuelleretal.2023, author = {Bestuzheva, Ksenia and Chmiela, Antonia and M{\"u}ller, Benjamin and Serrano, Felipe and Vigerske, Stefan and Wegscheider, Fabian}, title = {Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0}, journal = {Journal of Global Optimization}, doi = {10.1007/s10898-023-01345-1}, year = {2023}, abstract = {For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version 8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that are particular to MINLP solving in SCIP. Further, difficulties in benchmarking global MINLP solvers are discussed and a comparison with several state-of-the-art global MINLP solvers is provided.}, language = {en} } @inproceedings{ChmielaGleixnerLichockietal.2023, author = {Chmiela, Antonia and Gleixner, Ambros and Lichocki, Pawel and Pokutta, Sebastian}, title = {Online Learning for Scheduling MIP Heuristics}, volume = {13884}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, publisher = {Springer, Cham}, doi = {10.1007/978-3-031-33271-5_8}, pages = {114 -- 123}, year = {2023}, abstract = {Mixed Integer Programming (MIP) is NP-hard, and yet modern solvers often solve large real-world problems within minutes. This success can partially be attributed to heuristics. Since their behavior is highly instance-dependent, relying on hard-coded rules derived from empirical testing on a large heterogeneous corpora of benchmark instances might lead to sub-optimal performance. In this work, we propose an online learning approach that adapts the application of heuristics towards the single instance at hand. We replace the commonly used static heuristic handling with an adaptive framework exploiting past observations about the heuristic's behavior to make future decisions. In particular, we model the problem of controlling Large Neighborhood Search and Diving - two broad and complex classes of heuristics - as a multi-armed bandit problem. Going beyond existing work in the literature, we control two different classes of heuristics simultaneously by a single learning agent. We verify our approach numerically and show consistent node reductions over the MIPLIB 2017 Benchmark set. For harder instances that take at least 1000 seconds to solve, we observe a speedup of 4\%.}, language = {en} } @inproceedings{ChmielaMunozSerrano2023, author = {Chmiela, Antonia and Mu{\~n}oz, Gonzalo and Serrano, Felipe}, title = {Monoidal strengthening and unique lifting in MIQCPs}, volume = {13904}, booktitle = {Integer Programming and Combinatorial Optimization. IPCO 2023.}, doi = {10.1007/978-3-031-32726-1_7}, pages = {87 -- 99}, year = {2023}, abstract = {Using the recently proposed maximal quadratic-free sets and the well-known monoidal strengthening procedure, we show how to improve inter- section cuts for quadratically-constrained optimization problems by exploiting integrality requirements. We provide an explicit construction that allows an efficient implementation of the strengthened cuts along with computational results showing their improvements over the standard intersection cuts. We also show that, in our setting, there is unique lifting which implies that our strengthening procedure is generating the best possible cut coefficients for the integer variables.}, language = {en} } @article{GorgullaGarzaKapiletal.2025, author = {Gorgulla, Christoph and Garza, Alejandro J. and Kapil, Venkat and Fackeldey, Konstantin}, title = {QUASAR: A Flexible QM-MM Method for Biomolecular Systems based on Restraining Spheres}, volume = {320}, journal = {Computer Physics Communications}, issn = {0010-4655}, doi = {10.1016/j.cpc.2025.109949}, year = {2025}, abstract = {Quantum mechanical models of molecules theoretically offer unprecedented accuracy in predicting values associated with these systems, including the free energy of interaction between two molecules. However, high-accuracy quantum mechanical methods are computationally too expensive to be applied to larger systems, including most biomolecular systems such as proteins. To circumvent this challenge, the hybrid quantum mechanics/molecular mechanics (QM/MM) method was developed, allowing one to treat only the most important part of the system on the quantum mechanical level and the remaining part on the classical level. To date, QM/MM simulations for biomolecular systems have been carried out almost exclusively on the electronic structure level, neglecting nuclear quantum effects (NQEs). Yet NQEs can play a major role in biomolecular systems [1]. Here, we present i-QI, a QM/MM client for the path integral molecular dynamics (PIMD) software i-PI [2, 3, 4]. i-QI allows for carrying out QM/MM simulations simultaneously, allowing for the inclusion of electronic as well as nuclear quantum effects. i-QI implements a new QM/MM scheme based on constraining potentials called QUASAR, which allows handling diffusive systems, such as biomolecules solvated in water solvent. The QUASAR method is suitable in particular when the properties of interest are equilibrium properties, such as the free energy of binding. i-QI is freely available and open source, and we demonstrate it on a test system.}, language = {en} } @inproceedings{BortolettoLindner2025, author = {Bortoletto, Enrico and Lindner, Niels}, title = {Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times}, booktitle = {Operations Research Proceedings 2023}, editor = {Voigt, Guido and Fliedner, Malte and Haase, Knut and Br{\"u}ggemann, Wolfgang and Hoberg, Kai and Meissner, J{\"o}rn}, doi = {10.1007/978-3-031-58405-3_51}, pages = {397 -- 402}, year = {2025}, abstract = {The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.}, language = {en} } @misc{BestuzhevaChmielaMuelleretal.2023, author = {Bestuzheva, Ksenia and Chmiela, Antonia and M{\"u}ller, Benjamin and Serrano, Felipe and Vigerske, Stefan and Wegscheider, Fabian}, title = {Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89348}, year = {2023}, abstract = {For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version~8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that are particular to MINLP solving in SCIP. Further, difficulties in benchmarking global MINLP solvers are discussed and a comparison with several state-of-the-art global MINLP solvers is provided.}, language = {en} }