Iterated local search with Trellis-neighborhood for the partial Latin square extension problem

Kazuya Haraguchi ()
Additional contact information
Kazuya Haraguchi: Otaru University of Commerce

Journal of Heuristics, 2016, vol. 22, issue 5, No 4, 727-757

Abstract: Abstract A partial Latin square (PLS) is a partial assignment of n symbols to an $$n\times n$$ n × n grid such that, in each row and in each column, each symbol appears at most once. The PLS 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,\infty )$$ ( p , ∞ ) -neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for $$p\in \{1,2,3\}$$ p ∈ { 1 , 2 , 3 } . The running time of the algorithm is $$O(n^{p+1})$$ O ( n p + 1 ) . We then propose a novel swap operation, Trellis-swap, which is a generalization of (p, q)-swap with $$p\le 2$$ p ≤ 2 . The proposed Trellis-neighborhood search algorithm runs in $$O(n^{3.5})$$ O ( n 3.5 ) time. The iterated local search (ILS) algorithm with Trellis-neighborhood is more likely to deliver a high-quality solution than not only ILSs with $$(p,\infty )$$ ( p , ∞ ) -neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LocalSolver.

Keywords: Partial Latin square extension problem; Maximum independent set problem; Metaheuristics; Local search (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-016-9317-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:22:y:2016:i:5:d:10.1007_s10732-016-9317-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-016-9317-6

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().