AI summaryⓘ
The authors developed a way to make a complex algorithm run faster by splitting the work into parallel parts. They used this improved process to help sort and classify special mathematical objects called orthogonal arrays. Their method worked well, speeding up the classification for some previously studied arrays and allowed them to classify new, larger ones for the first time. This shows their approach improved the efficiency of a kind of mathematical search.
branch-and-boundisomorphism pruningorthogonal arraysparallel computingclassificationsymmetryoptimizationdiscrete mathematicscombinatoricsnon-OD-equivalent
Abstract
We provide a method for parallelizing the branch-and-bound with isomorphism pruning algorithm developed by Margot [Symmetric ILP: Coloring and small integers, Discrete Optimization (4) (2007), 40-62]. We apply our method to classify orthogonal arrays. For classifying all non-OD- equivalent OA(128, 9, 2, 4) and OA(144, 9, 2, 4) our method results in linear speedups. Finally, our method enables classifying all non-OD-equivalent OA(192, k, 2, 4) for k = 9, 10, 11 for the first time.