.. _tuning-slitherlink:

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.

.. code:: python
    :number-lines:

    # Slitherlink random generator
    import sys
    import random

    from mazelib import Maze
    from mazelib.generate.Prims import Prims
    from mazelib.solve.BacktrackingSolver import BacktrackingSolver

    max_horiz = int(sys.argv[1])
    max_verti = int(sys.argv[2])
    percent_number = int(sys.argv[3])
    percent_number /= 100
    seed = int(sys.argv[4])
    random.seed(seed)

    horiz = max_horiz
    verti = max_verti

    m = Maze(seed)
    m.solver = BacktrackingSolver()
    m.generator = Prims(horiz, verti)
    m.generate()

    grid = [list(row) for row in m.grid]

    verti = len(grid)
    horiz = len(grid[0])
    while True:
        start_i = random.randint(1, horiz - 1)
        start_j = 1
        if grid[start_j + 1][start_i] == 0:
            grid[start_j][start_i] = 0
            break

    def count_different(i, j, cell):
        around = [
            (i + 1, j),
            (i, j + 1),
            (i - 1, j),
            (i, j - 1),
        ]
        counter = 0
        for pi, pj in around:
            if 0 <= pi < horiz and 0 <= pj < verti:
                if grid[pj][pi] != cell:
                    counter += 1
        return counter

    for j, row in enumerate(grid):
        for i, cell in enumerate(row):
            if percent_number > random.random():
                print(count_different(i, j, cell), end='')
            else:
                print('-', end='')
        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 :ref:`this code <slither-solve-ac>`. Additionally, we will also configure whether the removal of unconstrained subcyles is active or not (which can impact the performance of the solving process).

.. _slither-solve-ac:

.. code:: python
    :number-lines:

    from optilog.tuning import CfgCls, ac, Bool as BoolParam

    @ac
    def solve_slitherlink(instance, seed, remove_unconstr_subcycles: BoolParam(True), Solver: CfgCls(Cadical)):
        sl = SlitherLink(instance)
        cnf = encode_slitherlink(sl)
        s = Solver()
        s.set("seed", seed)
        s.add_clauses(cnf.clauses)
        (...)

Notice that introducing this change to the function signature does not produce any change to how this function was called before [#1]_ . 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 :ref:`here <ac-scenario>`. In this example, we will use the ``GGAScenario`` class to generate the scenario files for PyDGGA :cite:p:`AMAI2021,sat21pydgga`.
The following configuration describes a GGA scenario with a PAR10 score [#2]_ , 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 :ref:`Tuning module <tuning-module>`. Finally, we generate the scenario at the directory ``gga_scenario``.

.. _ac-scenario:

.. code:: python
    :number-lines:

    from optilog.blackbox import ExecutionConstraints, RunSolver
    from optilog.tuning.configurators import GGAScenario
    from slitherlink import solve_slitherlink

    if __name__ == "__main__":
        time_limit = 300
        configurator = GGAScenario(
            solve_slitherlink,
            input_data="instances/training/*.txt",
            run_obj="runtime",
            data_kwarg="instance",
            seed_kwarg="seed",
            seed=1,
            cost_min=0,
            cost_max=10 * time_limit,
            tuner_rt_limit=60 * 60 * 4,
            instances_min=10,
            instances_gen_max=-10,
            constraints=ExecutionConstraints(
                s_real_memory="6G", s_wall_time=time_limit, enforcer=RunSolver()
            ),
        )

        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.

.. _ac-parsing:

.. code:: python
    :number-lines:

    from optilog.tuning.configurators.utils import GGAParser

    parser = GGAParser("<GGA output log>")
    parser.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.

.. [#1] Although we added a new parameter, *CfgCls* will automatically add a default value.
.. [#2] PAR10 score for a given time limit T is a hybrid measure, defined as the average of the runtimes for solved instances and of 10 × T for unsolved instances.