Tuning the Slitherlink Problem
Now that we have concluded the modelling and solving part for the Slitherlink problem, we can try to improve its performance by tuning our algorithm. In particular, we found that the Cadical SAT solver has a total of 146 discrete finite domain parameters that would be of interest to configure. In order to do so, we will use OptiLog’s Tuning module.
First of all, we will generate 100 random instances of size 101 x 101 using the generator that we show below. When transformed to CNF, these instances have an average of 149937 boolean variables, 308721 clauses for the first encoded formula and 395253 for the last one. The instances that we solve require an average of 120 iterations.
1# Slitherlink random generator
2import sys
3import random
4
5from mazelib import Maze
6from mazelib.generate.Prims import Prims
7from mazelib.solve.BacktrackingSolver import BacktrackingSolver
8
9max_horiz = int(sys.argv[1])
10max_verti = int(sys.argv[2])
11percent_number = int(sys.argv[3])
12percent_number /= 100
13seed = int(sys.argv[4])
14random.seed(seed)
15
16horiz = max_horiz
17verti = max_verti
18
19m = Maze(seed)
20m.solver = BacktrackingSolver()
21m.generator = Prims(horiz, verti)
22m.generate()
23
24grid = [list(row) for row in m.grid]
25
26verti = len(grid)
27horiz = len(grid[0])
28while True:
29 start_i = random.randint(1, horiz - 1)
30 start_j = 1
31 if grid[start_j + 1][start_i] == 0:
32 grid[start_j][start_i] = 0
33 break
34
35def count_different(i, j, cell):
36 around = [
37 (i + 1, j),
38 (i, j + 1),
39 (i - 1, j),
40 (i, j - 1),
41 ]
42 counter = 0
43 for pi, pj in around:
44 if 0 <= pi < horiz and 0 <= pj < verti:
45 if grid[pj][pi] != cell:
46 counter += 1
47 return counter
48
49for j, row in enumerate(grid):
50 for i, cell in enumerate(row):
51 if percent_number > random.random():
52 print(count_different(i, j, cell), end='')
53 else:
54 print('-', end='')
55 print()
We need to do is to update the solve_slitherlink
function to receive a Cadical SAT solver with its parameters already set, which we achieve by using CfgCls from the Tuning module, as shown in line 4 of this code. Additionally, we will also configure whether the removal of unconstrained subcyles is active or not (which can impact the performance of the solving process).
1from optilog.tuning import CfgCls, ac, Bool as BoolParam
2
3@ac
4def solve_slitherlink(instance, seed, remove_unconstr_subcycles: BoolParam(True), Solver: CfgCls(Cadical)):
5 sl = SlitherLink(instance)
6 cnf = encode_slitherlink(sl)
7 s = Solver()
8 s.set("seed", seed)
9 s.add_clauses(cnf.clauses)
10 (...)
Notice that introducing this change to the function signature does not produce any change to how this function was called before 3 . Therefore, the user will not need to modify any of the calls to solve_slitherlink
.
Then, we can proceed to create an automatic configuration scenario as shown here. In this example, we will use the GGAScenario
class to generate the scenario files for PyDGGA [AnsoteguiPS21, AnsoteguiPST21].
The following configuration describes a GGA scenario with a PAR10 score 4 , with a memory limit and time limit for execution of 6GB and 300s respectively, and a total time limit of 4 hours (for more information about the different parameters of GGAScenario
see the Tuning module. Finally, we generate the scenario at the directory gga_scenario
.
1from optilog.blackbox import ExecutionConstraints, RunSolver
2from optilog.tuning.configurators import GGAScenario
3from slitherlink import solve_slitherlink
4
5if __name__ == "__main__":
6 time_limit = 300
7 configurator = GGAScenario(
8 solve_slitherlink,
9 input_data="instances/training/*.txt",
10 run_obj="runtime",
11 data_kwarg="instance",
12 seed_kwarg="seed",
13 seed=1,
14 cost_min=0,
15 cost_max=10 * time_limit,
16 tuner_rt_limit=60 * 60 * 4,
17 instances_min=10,
18 instances_gen_max=-10,
19 constraints=ExecutionConstraints(
20 s_real_memory="6G", s_wall_time=time_limit, enforcer=RunSolver()
21 ),
22 )
23
24 configurator.generate_scenario("./gga_scenario")
We configured Cadical with PyDGGA 1.6.0 on a computer cluster with Intel Xeon Silver 4110 CPUs at 2.1GHz cores with 4 parallel processes each.
Once the automatic configuration process has finished, we can automatically extract the best configuration found by GGA by using the GGAParser
functionality of OptiLog’s Tuner module as shown below.
1from optilog.tuning.configurators.utils import GGAParser
2
3parser = GGAParser("<GGA output log>")
4parser.save_configs("./configs", "./gga_scenario", name="best-conf")
This function extracts the best configuration found by GGA and creates the executable ./configs/best-conf.sh
with the function solve_slitherlink
properly set to the best configuration.
With this final step we have all the required pieces to evaluate and compare the final performance of our approach by using the OptiLog’s Running module.