@inproceedings{MacDonaldBesanconPokutta2022, author = {MacDonald, Jan and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{TsujiTanakaPokutta2022, author = {Tsuji, Kazuma and Tanaka, Ken'ichiro and Pokutta, Sebastian}, title = {Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{WaeldchenHuberPokutta2022, author = {W{\"a}ldchen, Stephan and Huber, Felix and Pokutta, Sebastian}, title = {Training Characteristic Functions with Reinforcement Learning: XAI-methods Play Connect Four}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{SharmaHendrychBesanconetal.2024, author = {Sharma, Kartikey and Hendrych, Deborah and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Network Design for the Traffic Assignment Problem with Mixed-Integer Frank-Wolfe}, booktitle = {Proceedings of INFORMS Optimization Society Conference}, year = {2024}, language = {en} } @inproceedings{MexiShamsiBesanconetal.2024, author = {Mexi, Gioni and Shamsi, Somayeh and Besan{\c{c}}on, Mathieu and Bodic, Pierre}, title = {Probabilistic Lookahead Strong Branching via a Stochastic Abstract Branching Model}, volume = {14743}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024}, doi = {10.1007/978-3-031-60599-4_4}, year = {2024}, abstract = {Strong Branching (SB) is a cornerstone of all modern branching rules used in the Branch-and-Bound (BnB) algorithm, which is at the center of Mixed-Integer Programming solvers. In its full form, SB evaluates all variables to branch on and then selects the one producing the best relaxation, leading to small trees, but high runtimes. State-of-the-art branching rules therefore use SB with working limits to achieve both small enough trees and short run times. So far, these working limits have been established empirically. In this paper, we introduce a theoretical approach to guide how much SB to use at each node within the BnB. We first define an abstract stochastic tree model of the BnB algorithm where the geometric mean dual gains of all variables follow a given probability distribution. This model allows us to relate expected dual gains to tree sizes and explicitly compare the cost of sampling an additional SB candidate with the reward in expected tree size reduction. We then leverage the insight from the abstract model to design a new stopping criterion for SB, which fits a distribution to the dual gains and, at each node, dynamically continues or interrupts SB. This algorithm, which we refer to as Probabilistic Lookahead Strong Branching, improves both the tree size and runtime over MIPLIB instances, providing evidence that the method not only changes the amount of SB, but allocates it better.}, language = {en} } @article{EiflerGleixner2024, author = {Eifler, Leon and Gleixner, Ambros}, title = {Safe and verified Gomory mixed integer cuts in a rational MIP framework}, volume = {34}, journal = {SIAM Journal on Optimization}, number = {1}, doi = {10.1137/23M156046X}, year = {2024}, abstract = {This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009 [INFORMS J. Comput., 21 (2009), pp. 641-649]. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5\% more instances to exact optimality and reduce solving times by 26.8\% on the MIPLIB 2017 benchmark test set.}, language = {en} } @inproceedings{GhannamGleixner2023, author = {Ghannam, Mohammed and Gleixner, Ambros}, title = {Hybrid genetic search for dynamic vehicle routing with time windows}, booktitle = {Proceedings of Conference of the Society for Operations Research in Germany}, year = {2023}, language = {en} } @inproceedings{HoenOertelGleixneretal.2024, author = {Hoen, Alexander and Oertel, Andy and Gleixner, Ambros and Nordstr{\"o}m, Jakob}, title = {Certifying MIP-based presolve reductions for 0-1 integer linear programs}, volume = {14742}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024}, doi = {10.1007/978-3-031-60597-0_20}, year = {2024}, abstract = {It is well known that reformulating the original problem can be crucial for the performance of mixed-integer programming (MIP) solvers. To ensure correctness, all transformations must preserve the feasibility status and optimal value of the problem, but there is currently no established methodology to express and verify the equivalence of two mixed-integer programs. In this work, we take a first step in this direction by showing how the correctness of MIP presolve reductions on - integer linear programs can be certified by using (and suitably extending) the VeriPB tool for pseudo-Boolean proof logging. Our experimental evaluation on both decision and optimization instances demonstrates the computational viability of the approach and leads to suggestions for future revisions of the proof format that will help to reduce the verbosity of the certificates and to accelerate the certification and verification process further.}, language = {en} } @misc{IommazzoD'AmbrosioFrangionietal.2022, author = {Iommazzo, Gabriele and D'Ambrosio, Claudia and Frangioni, Antonio and Liberti, Leo}, title = {Algorithm configuration problem}, journal = {Encyclopedia of Optimization}, year = {2022}, language = {en} } @article{CombettesWoodstock2022, author = {Combettes, P. L. and Woodstock, Zev}, title = {a variational inequality model for the construction of signals from inconsistent nonlinear equations}, journal = {SIAM Journal on Imaging Sciences}, year = {2022}, language = {en} } @article{BraunGuzmanPokutta2024, author = {Braun, G{\´a}bor and Guzm{\´a}n, Crist{\´o}bal and Pokutta, Sebastian}, title = {Corrections to "Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory"}, volume = {70}, journal = {IEEE Transactions on Information Theory}, number = {7}, doi = {10.1109/TIT.2024.3357200}, pages = {5408 -- 5409}, year = {2024}, abstract = {This note closes a gap in the proof of Theorem VI.3 from the article "Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory" (2017).}, language = {en} } @article{EiflerGleixner2023, author = {Eifler, Leon and Gleixner, Ambros}, title = {A computational status update for exact rational mixed integer programming}, volume = {197}, journal = {Mathematical Programming}, doi = {10.1007/s10107-021-01749-5}, pages = {793 -- 812}, year = {2023}, abstract = {The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours.}, language = {en} } @article{LibertiIommazzoLavoretal.2023, author = {Liberti, Leo and Iommazzo, Gabriele and Lavor, Carlile and Maculan, Nelson}, title = {Cycle-based formulations in distance geometry}, volume = {4}, journal = {Open Journal of Mathematical Optimization}, doi = {10.5802/ojmo.18}, year = {2023}, abstract = {The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension , where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision variables that determine the position of the vertices in the given Euclidean space. Solution algorithms are generally constructed using local or global nonlinear optimization techniques. We present a new modelling technique for this problem where, instead of deciding vertex positions, the formulations decide the length of the segments representing the edges in each cycle in the graph, projected in every dimension. We propose an exact formulation and a relaxation based on a Eulerian cycle. We then compare computational results from protein conformation instances obtained with stochastic global optimization techniques on the new cycle-based formulation and on the existing edge-based formulation. While edge-based formulations take less time to reach termination, cycle-based formulations are generally better on solution quality measures.}, language = {en} } @inproceedings{CriscitielloMartinezRubioBoumal2023, author = {Criscitiello, Christopher and Mart{\´i}nez-Rubio, David and Boumal, Nicolas}, title = {Open problem: polynomial linearly-convergent method for g-convex optimization?}, volume = {195}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory, PMLR}, pages = {5950 -- 5956}, year = {2023}, language = {en} } @article{DesignolleIommazzoBesanconetal.2023, author = {Designolle, S{\´e}bastien and Iommazzo, Gabriele and Besan{\c{c}}on, Mathieu and Knebel, Sebastian and Gelß, Patrick and Pokutta, Sebastian}, title = {Improved local models and new Bell inequalities via Frank-Wolfe algorithms}, volume = {5}, journal = {Physical Review Research}, doi = {10.1103/PhysRevResearch.5.043059}, pages = {043059}, year = {2023}, abstract = {In Bell scenarios with two outcomes per party, we algorithmically consider the two sides of the membership problem for the local polytope: Constructing local models and deriving separating hyperplanes, that is, Bell inequalities. We take advantage of the recent developments in so-called Frank-Wolfe algorithms to significantly increase the convergence rate of existing methods. First, we study the threshold value for the nonlocality of two-qubit Werner states under projective measurements. Here, we improve on both the upper and lower bounds present in the literature. Importantly, our bounds are entirely analytical; moreover, they yield refined bounds on the value of the Grothendieck constant of order three: 1.4367⩽KG(3)⩽1.4546. Second, we demonstrate the efficiency of our approach in multipartite Bell scenarios, and present local models for all projective measurements with visibilities noticeably higher than the entanglement threshold. We make our entire code accessible as a julia library called BellPolytopes.jl.}, language = {en} } @article{BesanconGarciaLegatetal.2023, author = {Besan{\c{c}}on, Mathieu and Garcia, Joaquim Dias and Legat, Beno{\^i}t and Sharma, Akshay}, title = {Flexible Differentiable Optimization via Model Transformations}, volume = {36}, journal = {INFORMS Journal on Computing}, number = {2}, doi = {10.1287/ijoc.2022.0283}, pages = {456 -- 478}, year = {2023}, abstract = {We introduce DiffOpt.jl, a Julia library to differentiate through the solution of optimization problems with respect to arbitrary parameters present in the objective and/or constraints. The library builds upon MathOptInterface, thus leveraging the rich ecosystem of solvers and composing well with modeling languages like JuMP. DiffOpt offers both forward and reverse differentiation modes, enabling multiple use cases from hyperparameter optimization to backpropagation and sensitivity analysis, bridging constrained optimization with end-to-end differentiable programming. DiffOpt is built on two known rules for differentiating quadratic programming and conic programming standard forms. However, thanks to its ability to differentiate through model transformations, the user is not limited to these forms and can differentiate with respect to the parameters of any model that can be reformulated into these standard forms. This notably includes programs mixing affine conic constraints and convex quadratic constraints or objective function.}, language = {en} } @misc{GahururuHintermuellerStengletal.2022, author = {Gahururu, Deborah and Hinterm{\"u}ller, Michael and Stengl, Steven-Marian and Surowiec, Thomas M.}, title = {Generalized Nash equilibrium problems with partial differential operators: theory, algorithms, and risk aversion}, journal = {Non-smooth and Complementarity-based Distributed Parameter Systems: Simulation and Hierarchical Optimization}, year = {2022}, language = {en} } @article{KreimeierPokuttaWaltheretal., author = {Kreimeier, Timo and Pokutta, Sebastian and Walther, Andrea and Woodstock, Zev}, title = {On a Frank-Wolfe approach for abs-smooth functions}, journal = {Optimization Methods and Software}, doi = {10.1080/10556788.2023.2296985}, language = {en} } @article{HunkenschroederPokuttaWeismantel2022, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cube}, journal = {SIAM Journal on Optimization}, year = {2022}, language = {en} } @inproceedings{ThuerckSofranacPfetschetal.2023, author = {Thuerck, Daniel and Sofranac, Boro and Pfetsch, Marc and Pokutta, Sebastian}, title = {Learning cuts via enumeration oracles}, booktitle = {Proceedings of Conference on Neural Information Processing Systems}, year = {2023}, language = {en} } @inproceedings{MartinezRubioPokutta2022, author = {Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Accelerated Riemannian optimization: Handling constraints with a prox to bound geometric penalties}, booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2022)}, year = {2022}, language = {en} } @inproceedings{MartinezRubioRouxCriscitielloetal.2023, author = {Mart{\´i}nez-Rubio, David and Roux, Christophe and Criscitiello, Christopher and Pokutta, Sebastian}, title = {Accelerated Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties}, booktitle = {Proceedings of Optimization for Machine Learning (NeurIPS Workshop OPT 2023)}, year = {2023}, language = {en} } @article{DesignolleVertesiPokutta2024, author = {Designolle, S{\´e}bastien and V{\´e}rtesi, Tam{\´a}s and Pokutta, Sebastian}, title = {Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms}, volume = {109}, journal = {Physics Review A}, number = {2}, doi = {10.1103/PhysRevA.109.022205}, year = {2024}, abstract = {In multipartite Bell scenarios, we study the nonlocality robustness of the Greenberger-Horne-Zeilinger (GHZ) state. When each party performs planar measurements forming a regular polygon, we exploit the symmetry of the resulting correlation tensor to drastically accelerate the computation of (i) a Bell inequality via Frank-Wolfe algorithms and (ii) the corresponding local bound. The Bell inequalities obtained are facets of the symmetrized local polytope and they give the best-known upper bounds on the nonlocality robustness of the GHZ state for three to ten parties. Moreover, for four measurements per party, we generalize our facets and hence show, for any number of parties, an improvement on Mermin's inequality in terms of noise robustness. We also compute the detection efficiency of our inequalities and show that some give rise to the activation of nonlocality in star networks, a property that was only shown with an infinite number of measurements.}, language = {en} } @article{BinkowskiKulligBetzetal.2024, author = {Binkowski, Felix and Kullig, Julius and Betz, Fridtjof and Zschiedrich, Lin and Walther, Andrea and Wiersig, Jan and Burger, Sven}, title = {Computing eigenfrequency sensitivities near exceptional points}, volume = {6}, journal = {Phys. Rev. Research}, arxiv = {http://arxiv.org/abs/2402.17648}, doi = {10.1103/PhysRevResearch.6.023148}, pages = {023148}, year = {2024}, language = {en} } @misc{BinkowskiKulligBetzetal.2024, author = {Binkowski, Felix and Kullig, Julius and Betz, Fridtjof and Zschiedrich, Lin and Walther, Andrea and Wiersig, Jan and Burger, Sven}, title = {Source code and simulation results: Computing eigenfrequency sensitivities near exceptional points}, journal = {Zenodo}, doi = {10.5281/zenodo.10715639}, pages = {doi: 10.5281/zenodo.10715639}, year = {2024}, language = {en} } @article{BonamiGleixnerLinderothetal.2018, author = {Bonami, Pierre and Gleixner, Ambros and Linderoth, Jeff and Misener, Ruth}, title = {Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization (Dagstuhl Seminar 18081)}, volume = {8}, journal = {Dagstuhl Reports}, number = {2}, doi = {10.4230/DagRep.8.2.64}, pages = {64 -- 87}, year = {2018}, abstract = {Mathematical models for optimal decisions often require both nonlinear and discrete components. These mixed-integer nonlinear programs (MINLP) may be used to optimize the energy use of large industrial plants, integrate renewable sources into energy networks, design biological and biomedical systems, and address numerous other applications of societal importance. The first MINLP algorithms and software were designed by application engineers. While these efforts initially proved useful, scientists, engineers, and practitioners have realized that a transformational shift in technology will be required for MINLP to achieve its full potential. MINLP has transitioned to a forefront position in computer science, with researchers actively developing MINLP theory, algorithms, and implementations. Even with their concerted effort, algorithms and available software are often unable to solve practically-sized instances of these important models. Current obstacles include characterizing the computability boundary, effectively exploiting known optimization technologies for specialized classes of MINLP, and effectively using logical formulas holistically throughout algorithms.}, language = {en} } @inproceedings{BreuerBussieckCaoetal.2020, author = {Breuer, Thomas and Bussieck, Michael and Cao, Karl-Kien and Fiand, Fred and Gils, Hans-Christian and Gleixner, Ambros and Khabi, Dmitry and Kempke, Nils and Koch, Thorsten and Rehfeldt, Daniel and Wetzel, Manuel}, title = {BEAM-ME: Accelerating Linear Energy Systems Models by a Massively Parallel Interior Point Method}, volume = {50}, booktitle = {NIC Symposium 2020}, pages = {345 -- 352}, year = {2020}, language = {en} } @article{MuellerMunozGasseetal.2022, author = {M{\"u}ller, Benjamin and Mu{\~n}oz, Gonzalo and Gasse, Maxime and Gleixner, Ambros and Lodi, Andrea and Serrano, Felipe}, title = {On generalized surrogate duality in mixed-integer nonlinear programming}, volume = {192}, journal = {Mathematical Programming}, number = {1}, doi = {10.1007/s10107-021-01691-6}, pages = {89 -- 118}, year = {2022}, abstract = {The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global ϵ-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments.}, language = {en} } @misc{EbertMasingLindneretal.2024, author = {Ebert, Patricia and Masing, Berenike and Lindner, Niels and Gleixner, Ambros}, title = {Sorting Criteria for Line-based Periodic Timetabling Heuristics}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-97826}, year = {2024}, abstract = {It is well-known that optimal solutions are notoriously hard to find for the Periodic Event Scheduling Problem (PESP), which is the standard mathematical formulation to optimize periodic timetables in public transport. We consider a class of incremental heuristics that have been demonstrated to be effective by Lindner and Liebchen (2023), however, for only one fixed sorting strategy of lines along which a solution is constructed. Thus, in this paper, we examine a variety of sortings based on the number, weight, weighted span, and lower bound of arcs, and test for each setting various combinations of the driving, dwelling, and transfer arcs of lines. Additionally, we assess the impact on the incremental extension of the event-activity network by minimizing resp. maximizing a connectivity measure between subsets of lines. We compare our 27 sortings on the railway instances of the benchmarking library PESPlib within the ConcurrentPESP solver framework. We are able to find five new incumbent solutions, resulting in improvements of up to 2\%.}, language = {en} } @misc{PrauseBorndoerferGrimmetal.2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating the RSRP with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89531}, year = {2023}, abstract = {We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.}, language = {en} } @misc{Prause2023, author = {Prause, Felix}, title = {A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-93133}, year = {2023}, abstract = {We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subse- quently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables.}, language = {en} } @article{PrauseBorndoerfer2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {An Iterative Refinement Approach for the Rolling Stock Rotation Problem with Predictive Maintenance}, arxiv = {http://arxiv.org/abs/2404.08367}, year = {2024}, abstract = {The rolling stock rotation problem with predictive maintenance (RSRP-PdM) involves the assignment of trips to a fleet of vehicles with integrated maintenance scheduling based on the predicted failure probability of the vehicles. These probabilities are determined by the health states of the vehicles, which are considered to be random variables distributed by a parameterized family of probability distribution functions. During the operation of the trips, the corresponding parameters get updated. In this article, we present a dual solution approach for RSRP-PdM and generalize a linear programming based lower bound for this problem to families of probability distribution functions with more than one parameter. For this purpose, we define a rounding function that allows for a consistent underestimation of the parameters and model the problem by a state-expanded event-graph in which the possible states are restricted to a discrete set. This induces a flow problem that is solved by an integer linear program. We show that the iterative refinement of the underlying discretization leads to solutions that converge from below to an optimal solution of the original instance. Thus, the linear relaxation of the considered integer linear program results in a lower bound for RSRP-PdM. Finally, we report on the results of computational experiments conducted on a library of test instances.}, language = {en} } @inproceedings{Prause2024, author = {Prause, Felix}, title = {A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance}, booktitle = {Proceedings of the 11th International Network Optimization Conference (INOC), Dublin, Ireland, March 11-23, 2024}, doi = {10.48786/inoc.2024.11}, pages = {58 -- 63}, year = {2024}, abstract = {We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subsequently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables.}, language = {en} } @article{PrauseBorndoerferGrimmetal.2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating rolling stock rotations with integrated predictive maintenance}, volume = {30}, journal = {Journal of Rail Transport Planning \& Management}, doi = {10.1016/j.jrtpm.2024.100434}, pages = {100434}, year = {2024}, abstract = {We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for six instances derived from real-world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.}, language = {en} } @misc{PrauseBorndoerfer2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91734}, year = {2023}, abstract = {We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM.}, language = {en} } @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} } @misc{BestuzhevaBesanconChenetal.2021, author = {Bestuzheva, Ksenia and Besan{\c{c}}on, Mathieu and Chen, Wei-Kun and Chmiela, Antonia and Donkiewicz, Tim and van Doornmalen, Jasper and Eifler, Leon and Gaul, Oliver and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Leona and Graczyk, Christoph and Halbig, Katrin and Hoen, Alexander and Hojny, Christopher and van der Hulst, Rolf and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Matter, Frederic and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc E. and Rehfeldt, Daniel and Schlein, Steffan and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Sofranac, Boro and Turner, Mark and Vigerske, Stefan and Wegscheider, Fabian and Wellner, Philipp and Weninger, Dieter and Witzig, Jakob}, title = {The SCIP Optimization Suite 8.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-85309}, year = {2021}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack.}, language = {en} } @misc{BolusaniBesanconBestuzhevaetal.2024, author = {Bolusani, Suresh and Besan{\c{c}}on, Mathieu and Bestuzheva, Ksenia and Chmiela, Antonia and Dion{\´i}sio, Jo{\~a}o and Donkiewicz, Tim and van Doornmalen, Jasper and Eifler, Leon and Ghannam, Mohammed and Gleixner, Ambros and Graczyk, Christoph and Halbig, Katrin and Hedtke, Ivo and Hoen, Alexander and Hojny, Christopher and van der Hulst, Rolf and Kamp, Dominik and Koch, Thorsten and Kofler, Kevin and Lentz, Jurgen and Manns, Julian and Mexi, Gioni and M{\"u}hmer, Erik and E. Pfetsch, Marc and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Turner, Mark and Vigerske, Stefan and Weninger, Dieter and Xu, Liding}, title = {The SCIP Optimization Suite 9.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-95528}, year = {2024}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver.}, language = {en} } @article{BestuzhevaBesanconChenetal.2023, author = {Bestuzheva, Ksenia and Besan{\c{c}}on, Mathieu and Chen, Wei-Kun and Chmiela, Antonia and Donkiewicz, Tim and Doornmalen, Jasper and Eifler, Leon and Gaul, Oliver and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Leona and Graczyk, Christoph and Halbig, Katrin and Hoen, Alexander and Hojny, Christopher and Hulst, Rolf and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Matter, Frederic and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc and Rehfeldt, Daniel and Schlein, Steffan and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Sofranac, Boro and Turner, Mark and Vigerske, Stefan and Wegscheider, Fabian and Wellner, Philipp and Weninger, Dieter and Witzig, Jakob}, title = {Enabling research through the SCIP optimization suite 8.0}, volume = {49}, journal = {ACM Transactions on Mathematical Software}, number = {2}, doi = {10.1145/3585516}, pages = {1 -- 21}, year = {2023}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP's main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP's application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP.}, 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} } @article{ChmielaMunozSerrano2025, author = {Chmiela, Antonia and Mu{\~n}oz, Gonzalo and Serrano, Felipe}, title = {Monoidal strengthening and unique lifting in MIQCPs}, volume = {210}, journal = {Mathematical Programming B}, doi = {10.1007/s10107-024-02112-0}, pages = {189 -- 222}, year = {2025}, language = {en} } @article{ChmielaMunozSerrano2023, author = {Chmiela, Antonia and Mu{\~n}oz, Gonzalo and Serrano, Felipe}, title = {On the implementation and strengthening of intersection cuts for QCQPs}, volume = {197}, journal = {Mathematical Programming B}, doi = {10.1007/s10107-022-01808-5}, pages = {549 -- 586}, year = {2023}, language = {en} } @inproceedings{ChmielaKhalilGleixneretal.2021, author = {Chmiela, Antonia and Khalil, Elias B. and Gleixner, Ambros and Lodi, Andrea and Pokutta, Sebastian}, title = {Learning to Schedule Heuristics in Branch and Bound}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, arxiv = {http://arxiv.org/abs/2103.10294}, year = {2021}, abstract = {Primal heuristics play a crucial role in exact solvers for Mixed Integer Programming (MIP). While solvers are guaranteed to find optimal solutions given sufficient time, real-world applications typically require finding good solutions early on in the search to enable fast decision-making. While much of MIP research focuses on designing effective heuristics, the question of how to manage multiple MIP heuristics in a solver has not received equal attention. Generally, solvers follow hard-coded rules derived from empirical testing on broad sets of instances. Since the performance of heuristics is instance-dependent, using these general rules for a particular problem might not yield the best performance. In this work, we propose the first data-driven framework for scheduling heuristics in an exact MIP solver. By learning from data describing the performance of primal heuristics, we obtain a problem-specific schedule of heuristics that collectively find many solutions at minimal cost. We provide a formal description of the problem and propose an efficient algorithm for computing such a schedule. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49\% on a class of challenging instances.}, 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{GasseBowlyCappartetal.2022, author = {Gasse, Maxime and Bowly, Simon and Cappart, Quentin and Charfreitag, Jonas and Charlin, Laurent and Ch{\´e}telat, Didier and Chmiela, Antonia and Dumouchelle, Justin and Gleixner, Ambros and Kazachkov, Aleksandr M. and Khalil, Elias and Lichocki, Pawel and Lodi, Andrea and Lubin, Miles and Maddison, Chris J. and Christopher, Morris and Papageorgiou, Dimitri J. and Parjadis, Augustin and Pokutta, Sebastian and Prouvost, Antoine and Scavuzzo, Lara and Zarpellon, Giulia and Yang, Linxin and Lai, Sha and Wang, Akang and Luo, Xiaodong and Zhou, Xiang and Huang, Haohan and Shao, Shengcheng and Zhu, Yuanming and Zhang, Dong and Quan, Tao and Cao, Zixuan and Xu, Yang and Huang, Zhewei and Zhou, Shuchang and Binbin, Chen and Minggui, He and Hao, Hao and Zhiyu, Zhang and Zhiwu, An and Kun, Mao}, title = {The Machine Learning for Combinatorial Optimization Competition (ML4CO): results and insights}, booktitle = {Proceedings of Conference on Neural Information Processing Systems}, year = {2022}, 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} } @inproceedings{ChmielaMunozSerrano2021, author = {Chmiela, Antonia and Mu{\~n}oz, Gonzalo and Serrano, Felipe}, title = {On the implementation and strengthening of intersection cuts for QCQPs}, volume = {22}, booktitle = {Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021}, doi = {10.1007/978-3-030-73879-2_10}, pages = {134 -- 147}, year = {2021}, abstract = {The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm - a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations by simply plugging-in parameters associated to an arbitrary quadratic inequality being violated by a vertex of an LP relaxation. Additionally, we implement a cut-strengthening procedure that dates back to Glover and evaluate these techniques with extensive computational experiments.}, 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} } @article{CardereraPokuttaSchuetteetal.2025, author = {Carderera, Alejandro and Pokutta, Sebastian and Sch{\"u}tte, Christof and Weiser, Martin}, title = {An efficient first-order conditional gradient algorithm in data-driven sparse identification of nonlinear dynamics to solve sparse recovery problems under noise}, volume = {470}, journal = {Journal of Computational and Applied Mathematics}, doi = {10.1016/j.cam.2025.116675}, year = {2025}, abstract = {Governing equations are essential to the study of nonlinear dynamics, often enabling the prediction of previously unseen behaviors as well as the inclusion into control strategies. The discovery of governing equations from data thus has the potential to transform data-rich fields where well-established dynamical models remain unknown. This work contributes to the recent trend in data-driven sparse identification of nonlinear dynamics of finding the best sparse fit to observational data in a large library of potential nonlinear models. We propose an efficient first-order Conditional Gradient algorithm for solving the underlying optimization problem. In comparison to the most prominent alternative framework, the new framework shows significantly improved performance on several essential issues like sparsity-induction, structure-preservation, noise robustness, and sample efficiency. We demonstrate these advantages on several dynamics from the field of synchronization, particle dynamics, and enzyme chemistry.}, language = {en} } @inproceedings{SchummelTeichmannGonnermannMueller2025, author = {Schummel, Philip and Teichmann, Malte and Gonnermann-M{\"u}ller, Jana}, title = {Specifying ten roles of using chatgpt in secondary education: a teacher´s perspective}, booktitle = {Proceedings of the European Conference on Information Systems}, year = {2025}, abstract = {ChatGPT can benefit education; however, challenges arise that demand competent and responsible usage. Competence development needs to start in schools, with the teacher being the gatekeeper for integrating it into the teaching process. Existing research suggests that schoolteachers lack specific guidance on integrating ChatGPT into teaching, as current discussions remain high-level and omit specific use cases throughout the entire teaching process. To guide an informed usage, this paper presents the results of a systematic literature review, analyzing 38 selected papers on investigating ChatGPT in schools. This selection is based on rigorously defined criteria, adhering to the PRISMA guidelines, initially screening 1075 papers. The central value of this paper is to aggregate research into ten roles for secondary teachers on using ChatGPT in schools, presenting corresponding use cases throughout the teaching process. Future research validates the ten roles, conducting interviews with teachers to present an exhaustive framework for integrating ChatGPT in schoolteacher practice.}, language = {en} }