TY - GEN A1 - Turner, Mark A1 - Chmiela, Antonia A1 - Koch, Thorsten A1 - Winkler, Michael T1 - PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programs N2 - A standard tool for modelling real-world optimisation problems is mixed-integer programming (MIP). However, for many of these problems there is either incomplete information describing variable relations, or the relations between variables are highly complex. To overcome both these hurdles, machine learning (ML) models are often used and embedded in the MIP as surrogate models to represent these relations. Due to the large amount of available ML frameworks, formulating ML models into MIPs is highly non-trivial. In this paper we propose a tool for the automatic MIP formulation of trained ML models, allowing easy integration of ML constraints into MIPs. In addition, we introduce a library of MIP instances with embedded ML constraints. The project is available at https://github.com/Opt-Mucca/PySCIPOpt-ML. T3 - ZIB-Report - 23-28 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-93095 SN - 1438-0064 ER - TY - GEN A1 - Kempke, Nils-Christian A1 - Koch, Thorsten T1 - Low-precision first-order method-based fix-and-propagate heuristics for large-scale mixed-integer linear optimization N2 - We investigate the use of low-precision first-order methods (FOMs) within a fix-and-propagate (FP) framework for solving mixed-integer programming problems (MIPs). FOMs, using only matrix-vector products instead of matrix factorizations, are well suited for GPU acceleration and have recently gained more attention for their application to large-scale linear programming problems (LPs). We employ PDLP, a variant of the Primal-Dual Hybrid Gradient (PDHG) method specialized to LP problems, to solve the LP-relaxation of our MIPs to low accuracy. This solution is used to motivate fixings within our fix-and-propagate framework. We implemented four different FP variants using primal and dual LP solution information. We evaluate the performance of our heuristics on MIPLIB 2017, showcasing that the low-accuracy LP solution produced by the FOM does not lead to a loss in quality of the FP heuristic solutions when compared to a high-accuracy interior-point method LP solution. Further, we use our FP framework to produce high-accuracy solutions for large-scale (up to 243 million non-zeros and 8 million decision variables) unit-commitment energy-system optimization models created with the modeling framework REMix. For the largest problems, we can generate solutions with under 2% primal-dual gap in less than 4 hours, whereas commercial solvers cannot generate feasible solutions within two days of runtime. This study represents the first successful application of FOMs in large-scale mixed-integer optimization, demonstrating their efficacy and establishing a foundation for future research in this domain. T3 - ZIB-Report - 25-04 KW - Integer programming KW - Large scale optimization KW - Linear Programming KW - Primal heuristics KW - OR in energy Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-99612 SN - 1438-0064 ER - TY - CHAP A1 - Kunt, Tim T1 - Solving the n-Queens Problem in Higher Dimensions T2 - Operations Research Proceedings 2024. OR 2024 N2 - How many mutually non-attacking queens can be placed on a d-dimensional chessboard of size n? The n-queens problem in higher dimensions is a generalization of the well-known n-queens problem. We present an integer programming formulation of the n-queens problem in higher dimensions and several strengthenings through additional valid inequalities. Compared to recent benchmarks, we achieve a speedup in computational time between 15–70x over all instances of the integer programs. Our computational results prove optimality of certificates for several large instances. Breaking additional, previously unsolved instances with the proposed methods is likely possible. On the primal side, we further discuss heuristic approaches to constructing solutions that turn out to be optimal when compared to the IP. KW - Integer Programming KW - Maximum Independent Set KW - n-Queens Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-92575-7_29 SP - 205 EP - 211 ER - TY - GEN A1 - Kempke, Nils-Christian A1 - Maher, Stephen John A1 - Rehfeldt, Daniel A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Uslu, Svenja T1 - Distributed Parallel Structure-Aware Presolving for Arrowhead Linear Programs N2 - We present a structure-aware parallel presolve framework specialized to arrowhead linear programs (AHLPs) and designed for high-performance computing (HPC) environments, integrated into the parallel interior point solver PIPS-IPM++. Large-scale LPs arising from automated model generation frequently contain redundancies and numerical pathologies that necessitate effective presolve, yet existing presolve techniques are primarily serial or structure-agnostic and can become time-consuming in parallel solution workflows. Within PIPS-IPM++, AHLPs are stored in distributed memory, and our presolve builds on this to apply a highly parallel, distributed presolve across compute nodes while keeping communication overhead low and preserving the underlying arrowhead structure. We demonstrate the scalability and effectiveness of our approach on a diverse set of AHLPs and compare it against state-of-the-art presolve implementations, including PaPILO and the presolve implemented within Gurobi. Even on a single machine, our presolve significantly outperforms PaPILO by a factor of 18 and Gurobi’s presolve by a factor of 6 in terms of shifted geometric mean runtime, while reducing the problems by a similar amount to PaPILO. Using a distributed compute environment, we outperform Gurobi's presolve by a factor of 13. T3 - ZIB-Report - 26-01 KW - Linear Programming KW - Presolving KW - Large-Scale Optimization KW - Distributed Parallel Computing KW - Arrowhead Y1 - 2026 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-103034 SN - 1438-0064 ER -