TY - CHAP A1 - Borndörfer, Ralf A1 - Schwartz, Stephan A1 - Surau, William T1 - Finding Minimum Balanced Separators - an Exact Approach T2 - Operations Research Proceedings 2021 N2 - 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. T3 - ZIB-Report - 21-25 Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-83138 SN - 1438-0064 SP - 154 EP - 159 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 -