Massively parallel hybrid search for the partial Latin square extension problem. (arXiv:2103.10453v1 [cs.AI])

The partial Latin square extension problem is to fill as many as possible
empty cells of a partially filled Latin square. This problem is a useful model
for a wide range of relevant applications in diverse domains. This paper
presents the first massively parallel hybrid search algorithm for this
computationally challenging problem based on a transformation of the problem to
partial graph coloring. The algorithm features the following original elements.
Based on a very large population (with more than $10^4$ individuals) and modern
graphical processing units, the algorithm performs many local searches in
parallel to ensure an intensified exploitation of the search space. It employs
a dedicated crossover with a specific parent matching strategy to create a
large number of diversified and information-preserving offspring at each
generation. Extensive experiments on 1800 benchmark instances show a high
competitiveness of the algorithm compared with the current best performing
methods. Competitive results are also reported on the related Latin square
completion problem. Analyses are performed to shed lights on the understanding
of the main algorithmic components. The code of the algorithm will be made
publicly available.



Related post