2026-03-11T10:20:27Z https://barrel.repo.nii.ac.jp/oai

oai:barrel.repo.nii.ac.jp:00005189 2025-03-17T00:38:51Z 1:536 4

Iterated Local Search with Trellis-Neighborhood for the Partial Latin Square Extension Problem Haraguchi, Kazuya https://doi.org/10.1007/s10732-016-9317-6 007 情報学 数学 A partial Latin square (PLS) is a partial assignment of n symbols to an n x n grid such that, in each row and in each column, each symbol appears at most once. The partial Latin square extension problem is an NP-hard problem that asks for a largest extension of a given PLS. We consider the local search such that the neighborhood is defined by (p, q)-swap, i.e.,the operation of dropping exactly p symbols and then assigning symbols to at most q empty cells. As a fundamental result, we provide an efficient (p,∞)-neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for p ∈ {1, 2, 3}. The runnin time of the algorithm is O(nP+1). We then propose a novel swap operation, Trellisswap,which is a generalization of (p, q)-swap with p≤2. The proposed Trellis-neighborhood search algorithm runs in O(n3·5) time. The iterated local search (ILS) algorithm with Trellisneighborhood is more likely to deliver a high-quality solution than not only ILSs with (p, ∞)neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LOCALSOLVER. Springer US 2016-10 eng journal article AM http://hdl.handle.net/10252/00005804 https://barrel.repo.nii.ac.jp/records/5189 https://doi.org/10.1007/s10732-016-9317-6 AA12120967 1381-1231 Journal of Heuristics 22 5 727 757 https://barrel.repo.nii.ac.jp/record/5189/files/Journal of Heuristics_22_5_ pp 727–757.pdf application/pdf 1.3 MB 2018-07-04