2026-03-13T18:05:27Z https://barrel.repo.nii.ac.jp/oai

oai:barrel.repo.nii.ac.jp:00005044 2023-05-15T15:51:51Z 1:536

An Efficient Local Search for Partial Latin Square Extension Problem Haraguchi, Kazuya The original publication is available at www.springerlink.com 007 partial Latin square extension problem maximum independent set problem metaheuristics local search A partial Latin square (PLS) is a partial assignment of nsymbols to an n×n grid such that, in each row and in each column, eachsymbol appears at most once. The partial Latin square extension problemis an NP-hard problem that asks for a largest extension of a givenPLS. In this paper we propose an efficient local search for this problem.We focus on the local search such that the neighborhood is defined by(p, q)-swap, i.e., removing exactly p symbols and then assigning symbolsto at most qempty cells. For p ∈ {1, 2, 3}, our neighborhood search algorithmfinds an improved solution or concludes that no such solutionexists in O(np+1) time. We also propose a novel swap operation,Trellisswap,which is a generalization of (1, q)-swap and (2, q)-swap. Our Trellisneighborhoodsearch algorithm takes O(n3.5) time to do the same thing.Using these neighborhood search algorithms, we design a prototype iteratedlocal search algorithm and show its effectiveness in comparisonwith state-of-the-artoptimization solvers such as IBM ILOG CPLEX and LocalSolver. Springer International Publishing 2015-04-16 eng journal article AM http://hdl.handle.net/10252/00005670 https://barrel.repo.nii.ac.jp/records/5044 10.1007/978-3-319-18008-3_13 https://link.springer.com/chapter/10.1007/978-3-319-18008-3_13 0302-9743 Lecture Notes in Computer Science 9075 182 198 https://barrel.repo.nii.ac.jp/record/5044/files/LNCS-2015-8496.pdf application/pdf 198.2 kB 2017-06-19