AN EFFICIENT LOCAL SEARCH FOR THE CONSTRAINED SYMMETRIC LATIN SQUARE CONSTRUCTION PROBLEM

DOI Web Site Web Site 参考文献23件

この論文をさがす

抄録

<p>A Latin square is a complete assignment of [n]={1,...,n} to an n × n grid such that, in each row and in each column, each value in [n] appears exactly once. A symmetric Latin square (SLS) is a Latin square that is symmetric in the matrix sense. In what we call the constrained SLS construction (CSLSC) problem, we are given a subset F of [n]3 and are asked to construct an SLS so that, whenever (i,j,k)∈ F, the symbol k is not assigned to the cell (i,j). This paper has two contributions for this problem. One is proposal of an efficient local search algorithm for the maximization version of the problem. The maximization problem asks to fill as many cells with symbols as possible under the constraint on F. In our local search, the neighborhood is defined by p-swap, i.e., dropping exactly p symbols and then assigning any number of symbols to empty cells. For p∈{1,2}, our neighborhood search algorithm finds an improved solution or concludes that no such solution exists in O(np+1) time. The other contribution is to show its practical value for the CSLSC problem. For randomly generated instances, our iterated local search algorithm frequently constructs a larger partial SLS than state-of-the-art solvers such as IBM ILOG CPLEX, LocalSolver and WCSP.</p>

収録刊行物

参考文献 (23)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ