A massively parallel evolutionary algorithm for the partial Latin square extension problem

DOI10.1016/J.COR.2023.106284MaRDI QIDQ6106593zbMATH OpenFDO

Authors Olivier Goudet, Jin-Kao Hao

Publication date 3 July 2023

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.10453

zbMATH Keywords

combinatorial optimizationevolutionary searchheuristicsLatin square problemsparallel searchpartial graph coloring

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Abstract: 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 applications in diverse domains. This paper presents the first massively parallel evolutionary algorithm 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 intensive exploitation of the search space. The algorithm 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 to 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 roles of the main algorithmic components. The code of the algorithm will be made publicly available.

Recommendations

• An efficient local search for partial Latin square extension problem
• On Completing Latin Squares
• Iterated local search with Trellis-neighborhood for the partial Latin square extension problem
• An improved approximation algorithm for the partial Latin square extension problem.
• Approximating latin square extensions

Cites work

• A graph coloring heuristic using partial solutions and a reactive tabu scheme
• A memetic algorithm for graph coloring
• A metaheuristic approach for the vertex coloring problem
• Adaptive feasible and infeasible tabu search for weighted vertex coloring
• An efficient algorithm for computing the distance between close partitions
• An improved approximation algorithm for the partial Latin square extension problem.
• Characterization of polynomially complete quasigroups based on Latin squares for cryptographic transformations.
• Embedding Incomplete Latin Squares
• scientific article; zbMATH DE number 6473829 (Why is no real title available?)
• scientific article; zbMATH DE number 1556753 (Why is no real title available?)
• scientific article; zbMATH DE number 6288955 (Why is no real title available?)
• Hybrid evolutionary algorithms for graph coloring
• Iterated local search with Trellis-neighborhood for the partial Latin square extension problem
• Quasigroup Identities and Mendelsohn Designs
• The complexity of completing partial Latin squares
• Using tabu search techniques for graph coloring

This page was built for publication: A massively parallel evolutionary algorithm for the partial Latin square extension problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6106593)