A Collection of Efficient Local Searches for Partial Latin Square Extension Problem and Its Variants

• Item type: SIG Technical Reports(1)
• 公開日: 2015-06-05
• タイトル: A Collection of Efficient Local Searches for Partial Latin Square Extension Problem and Its Variants
• タイトル / 言語: en
• タイトル: A Collection of Efficient Local Searches for Partial Latin Square Extension Problem and Its Variants
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Faculty of Commerce, Otaru University of Commerce
• 著者所属(英): en
• 著者所属(英): Faculty of Commerce, Otaru University of Commerce
• 著者名: Kazuya, Haraguchi
• 著者名(英): Kazuya, Haraguchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The partial Latin square (PLS) extension problem asks for a largest extension of a given PLS. The problem is NP-hard and among fundamental problems in constraint optimization. Recently we proposed a collection of efficient local searches for the problem. The local search is based on conventional swap neighborhoods and on a novel type of neighborhood, Trellis-neighborhood. The iterated local searches with these neighborhoods outperform state-of-the-art optimization solvers by a wide margin. In this paper, we review this technique and extend it to variant problems such as Sudoku completion and finding orthogonal Latin squares.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The partial Latin square (PLS) extension problem asks for a largest extension of a given PLS. The problem is NP-hard and among fundamental problems in constraint optimization. Recently we proposed a collection of efficient local searches for the problem. The local search is based on conventional swap neighborhoods and on a novel type of neighborhood, Trellis-neighborhood. The iterated local searches with these neighborhoods outperform state-of-the-art optimization solvers by a wide margin. In this paper, we review this technique and extend it to variant problems such as Sudoku completion and finding orthogonal Latin squares.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2015-AL-153, 号 4, p. 1-8, 発行日 2015-06-05
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会