@inproceedings{BorndoerferSchwartzSurau2021, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Finding Minimum Balanced Separators - an Exact Approach}, booktitle = {Operations Research Proceedings 2021}, issn = {1438-0064}, doi = {https://doi.org/10.1007/978-3-031-08623-6_24}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83138}, pages = {154 -- 159}, year = {2021}, abstract = {Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances.}, language = {en} } @inproceedings{Kunt2025, author = {Kunt, Tim}, title = {Solving the n-Queens Problem in Higher Dimensions}, booktitle = {Operations Research Proceedings 2024. OR 2024}, doi = {10.1007/978-3-031-92575-7_29}, pages = {205 -- 211}, year = {2025}, abstract = {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.}, language = {en} }