PLSE Archive
Kazuya HARAGUCHI
dr.kazuya.haraguchi (at-mark) gmail.com
(last updated: Nov 5, 2020)
The page contains some materials of the PLSE (Partial Latin Square Extension) problem that I used in my previous papers:
- [CPAIOR2015] Kazuya Haraguchi. An Efficient Local Search for Partial Latin Square Extension Problem. Proceedings of CPAIOR 2015 (LNCS vol.9075), May 2015, pp.182--198.
- [JH2016] Kazuya Haraguchi. Iterated local search with Trellis-neighborhood for the partial Latin square extension problem. Journal of Heuristics, Vol.22-5, Oct 2016, pp.727--757.
local search tester [link]
/
benchmark instances [link]
What is PLSE problem?
PLSE is an abbreviation of Partial Latin Square Extension.
Let n be a natural number.
A partial Latin square (PLS)
is a partial assignment of integers from 1 to n
to an n by n square grid such that, in every row and in every column,
each integer should appear at most once.
The following figure shows an instance of a PLS with n=5.
The PLSE problem asks for a largest extension of a given PLS.
In other words, we are asked to fill so many empty cells as possible
without violating the underlined condition above.
The following figure shows an optimal solution of the above instance.
Obviously, if you can complete all the cells,
then you have an optimal solution.
But not all PLSs are completable.
The following PLS is an example of such a case.
(Solve it, and you will find that this PLS is not completable.)
The problem is NP-hard since the decision problem version
is NP-complete [Colbourn, 1984].
Local search tester
Currently unavailable.
Benchmark instances
(n: grid length, r: pre-assigned ratio)
Description
The above table has links to benchmark instances
and experimental results in my previous papers.
- A PLSE instance is given in terms of a partial Latin square.
It is parametrized by a grid length (n) and
a pre-assigned ratio (r).
For two instance types, that is QWH and QC, see here.
- In [CPAIOR2015], I conducted experiments for instances with n=40, 50 and 60,
where the timelimit is set to 30 seconds.
For these instances,
I open the objective values attained by my algorithms (CPAIOR2015 version)
and some competitors. See here for the algorithms.
- To prepare [JH2016],
I fixed drawbacks of my program to improve the efficiency,
some of which are mentioned in that paper.
In [JH2016],
I conducted experiments for instances with n=50, 60 and 70,
where the timelimit is set to 10 seconds.
The instances with n=50 and 60 are exactly same as those used in [CPAIOR2015].
Instance type
I generated instances by two well-known methods.
- QWH (quasigroup with holes).
It generates an instance by removing (1-r)n^2 integers randomly
from an arbitrary Latin square.
A QWH instance always admits a complete Latin square as an optimal solution.
- QC (quasigroup completion).
Starting with an empty assignment,
it repeats assigning an integer to an empty cell randomly so that the resulting assignment is a partial Latin square,
until rn^2 cells are assigned integers.
A QC instance DOES NOT always admit a complete Latin square as an optimal solution.
Algorithms
- G5. It is a constructive algorithm
for PLSE problem. It is a "look-ahead" minimum-degree greedy algorithm.
See [Alidaee et al., 2008] for detail.
The solutions constructed by G5 are
used as initial solutions of my algorithms and competitors below.
- My algorithms: 1-ILS, 2-ILS, Tr-ILS and 3-ILS, etc.
They are metaheuristic algorithms based on ILS (iterated local search).
They employ different types of neighborhoods from each other.
See the papers for detail.
- Competitors: CPLEX (IP and CP) and LocalSolver.
PLSE problem can be formulated by
IP (integer programming) or CP (constraint programming).
I solved the formulated models by IBM ILOG CPLEX (ver 12.6).
I also solved the problem by
LocalSolver (ver 4.5),
a general heuristic solver
based on local search.
The time limit is set to 30 seconds.
|