WEKO3
アイテム
Iterated Local Search with Trellis-Neighborhood for the Partial Latin Square Extension Problem
http://hdl.handle.net/10252/00005804
http://hdl.handle.net/10252/0000580490aed977-1162-42d0-9ebd-124775163d23
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
Journal of Heuristics_22_5_ pp 727–757 (1.3 MB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2018-07-04 | |||||
| タイトル | ||||||
| タイトル | Iterated Local Search with Trellis-Neighborhood for the Partial Latin Square Extension Problem | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 著者 |
Haraguchi, Kazuya
× Haraguchi, Kazuya |
|||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 32472 | |||||
| 姓名 | 原口, 和也 | |||||
| 言語 | ja | |||||
| 書誌情報 |
en : Journal of Heuristics 巻 22, 号 5, p. 727-757, 発行日 2016-10 |
|||||
| 出版者 | ||||||
| 出版者 | Springer US | |||||
| 言語 | en | |||||
| ISSN / EISSN | ||||||
| 収録物識別子タイプ | PISSN | |||||
| 収録物識別子 | 1381-1231 | |||||
| DOI | ||||||
| 関連タイプ | isVersionOf | |||||
| 識別子タイプ | DOI | |||||
| 関連識別子 | https://doi.org/10.1007/s10732-016-9317-6 | |||||
| 書誌ID（NCID） | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AA12120967 | |||||
| 出版社版URI | ||||||
| 言語 | ja | |||||
| 権利情報 | https://doi.org/10.1007/s10732-016-9317-6 | |||||
| テキストバージョン | ||||||
| 出版タイプ | AM | |||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
| 日本十進分類法 | ||||||
| 言語 | ja | |||||
| 主題Scheme | NDC | |||||
| 主題 | 007 | |||||
| NIIサブジェクト | ||||||
| 言語 | ja | |||||
| 主題Scheme | Other | |||||
| 主題 | 情報学 | |||||
| NIIサブジェクト | ||||||
| 言語 | ja | |||||
| 主題Scheme | Other | |||||
| 主題 | 数学 | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | 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. | |||||
| 言語 | en | |||||
