@misc{KempkeKoch2025, author = {Kempke, Nils-Christian and Koch, Thorsten}, title = {A GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-100554}, year = {2025}, abstract = {The market split problem (MSP), introduced by Cornu{\´e}jols and Dawande (1998), is a challenging binary optimization problem that performs poorly on state-of-the-art linear programming-based branch-and-cut solvers. We present a novel algorithm for solving the feasibility version of this problem, derived from Schroeppel-Shamir's algorithm for the one-dimensional subset sum problem. Our approach is based on exhaustively enumerating one-dimensional solutions of MSP and utilizing GPUs to evaluate candidate solutions across the entire problem. The resulting hybrid CPU-GPU implementation efficiently solves instances with up to 10 constraints and 90 variables. We demonstrate the algorithm's performance on benchmark problems, solving instances of size (9, 80) in less than fifteen minutes and (10, 90) in up to one day.}, language = {en} } @misc{KempkeRehfeldtKoch2024, author = {Kempke, Nils-Christian and Rehfeldt, Daniel and Koch, Thorsten}, title = {A Massively Parallel Interior-Point-Method for Arrowhead Linear Programs}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2412.07731}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98829}, year = {2024}, abstract = {In practice, non-specialized interior point algorithms often cannot utilize the massively parallel compute resources offered by modern many- and multi-core compute platforms. However, efficient distributed solution techniques are required, especially for large-scale linear programs. This article describes a new decomposition technique for systems of linear equations implemented in the parallel interior-point solver PIPS-IPM++. The algorithm exploits a matrix structure commonly found in optimization problems: a doubly-bordered block-diagonal or arrowhead structure. This structure is preserved in the linear KKT systems solved during each iteration of the interior-point method. We present a hierarchical Schur complement decomposition that distributes and solves the linear optimization problem; it is designed for high-performance architectures and scales well with the availability of additional computing resources. The decomposition approach uses the border constraints' locality to decouple the factorization process. Our approach is motivated by large-scale unit-commitment problems. We demonstrate the performance of our method on a set of mid-to large-scale instances, some of which have more than 10^9 nonzeros in their constraint matrix.}, language = {en} } @inproceedings{GleixnerKempkeKochetal.2020, author = {Gleixner, Ambros and Kempke, Nils-Christian and Koch, Thorsten and Rehfeldt, Daniel and Uslu, Svenja}, title = {First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method}, booktitle = {Operations Research Proceedings 2019}, edition = {1}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-030-48439-2_13}, pages = {105 -- 111}, year = {2020}, abstract = {In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.}, language = {en} } @misc{GleixnerKempkeKochetal.2019, author = {Gleixner, Ambros and Kempke, Nils-Christian and Koch, Thorsten and Rehfeldt, Daniel and Uslu, Svenja}, title = {First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method}, issn = {1438-0064}, doi = {10.1007/978-3-030-48439-2_13}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74084}, year = {2019}, abstract = {In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.}, language = {en} } @article{KempkeRehfeldtKoch2025, author = {Kempke, Nils-Christian and Rehfeldt, Daniel and Koch, Thorsten}, title = {A Massively Parallel Interior-Point-Method for Arrowhead Linear Programs}, journal = {SIAM Journal on Scientific Computing}, arxiv = {http://arxiv.org/abs/2412.07731}, year = {2025}, language = {en} } @misc{KempkeKoch2025, author = {Kempke, Nils-Christian and Koch, Thorsten}, title = {Low-precision first-order method-based fix-and-propagate heuristics for large-scale mixed-integer linear optimization}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2503.10344}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99612}, year = {2025}, abstract = {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.}, language = {en} } @misc{KempkeKuntKatamishetal.2025, author = {Kempke, Nils-Christian and Kunt, Tim and Katamish, Bassel and Vanaret, Charlie and Sasanpour, Shima and Clarner, Jan-Patrick and Koch, Thorsten}, title = {Developing heuristic solution techniques for large-scale unit commitment models}, issn = {1438-0064}, arxiv = {http://arxiv.org/abs/2502.19012}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99555}, year = {2025}, abstract = {Shifting towards renewable energy sources and reducing carbon emissions necessitate sophisticated energy system planning, optimization, and extension. Energy systems optimization models (ESOMs) often form the basis for political and operational decision-making. ESOMs are frequently formulated as linear (LPs) and mixed-integer linear (MIP) problems. MIPs allow continuous and discrete decision variables. Consequently, they are substantially more expressive than LPs but also more challenging to solve. The ever-growing size and complexity of ESOMs take a toll on the computational time of state-of-the-art commercial solvers. Indeed, for large-scale ESOMs, solving the LP relaxation -- the basis of modern MIP solution algorithms -- can be very costly. These time requirements can render ESOM MIPs impractical for real-world applications. This article considers a set of large-scale decarbonization-focused unit commitment models with expansion decisions based on the REMix framework (up to 83 million variables and 900,000 discrete decision variables). For these particular instances, the solution to the LP relaxation and the MIP optimum lie close. Based on this observation, we investigate the application of relaxation-enforced neighborhood search (RENS), machine learning guided rounding, and a fix-and-propagate (FP) heuristic as a standalone solution method. Our approach generated feasible solutions 20 to 100 times faster than GUROBI, achieving comparable solution quality with primal-dual gaps as low as 1\% and up to 35\%. This enabled us to solve numerous scenarios without lowering the quality of our models. For some instances that Gurobi could not solve within two days, our FP method provided feasible solutions in under one hour.}, language = {en} } @inproceedings{KochKempkeLindneretal.2026, author = {Koch, Thorsten and Kempke, Nils-Christian and Lindner, Niels and Mehl, Lukas and Wetzel, Manuel and Zittel, Janina}, title = {High-Performance Robust Energy System Planning with Storage: A Single-LP Approach}, booktitle = {Proceedings of URBSENSE 2026 - 1st International Workshop on URBan SENSEmaking and Intelligence for Safer Cities}, year = {2026}, language = {en} }