.. _controlling-solution-search:

*******************************
Controlling the solution search
*******************************

In this chapter, you will be introduced to search control. It includes:

* a short description of the main principles ;
* a presentation of the default strategy for optimization ;
* the objects involved in search control.

Method description
==================

Search is made thanks to a tree search algorithm. At each node, propagation is made and if no solution exists, Artelys Kalis needs to split your problem in smaller subproblems covering (or not) all the initial problem. This partition is made following a branching scheme. Here is a figure (:numref:`fig6_TreeSearchAlgorithm`) explaining that:

.. _fig6_TreeSearchAlgorithm:
.. figure:: images/6_TreeSearchAlgorithm.png
   :align: center

   Tree search algorithm

Different types of branching schemes exist. For example, a classical way is to choose a variable which has not been instantiated so far and to build a sub-problem for each remaining value in the variable's domain, this sub-problem being the original problem where propagation the variable has been instantiated to this value. And then, you can continue the search with these new nodes.

Choosing the right branching schemes to be used with your particular problem could *greatly improve* the performance of the tree search. Artelys Kalis allows you to choose between many classical *branching schemes* provided with the library and to easily *program* yourself the more specialized branching schemes that you suppose to be useful with your own problems.

Here are classical branching schemes available in Artelys Kalis:

.. graphviz::
    :caption: Classical branching schemes
    :align: center

    digraph foo {
           subgraph cluster_KAssignAndForbid {
            label = "KAssignAndForbid";
            a -> b [label="X = v"];
              a -> c [label="X ≠ v"];
              a [label=""];
              b [label=""];
              c [label=""];
        }

        subgraph cluster_KSplitDomain {
            label = "KSplitDomain";
            d -> e [label="X ≤ v"];
              d -> f [label="X > v"];
              d [label=""];
              e [label=""];
              f [label=""];
        }

        subgraph cluster_KAssignVar {
            label = "KAssignVar";
            g -> h [label="X = x1"];
              g -> i [label="X = x2"];
              g -> j [label="X = x3"];
              g [label=""];
              h [label=""];
              i [label=""];
              j [label=""];
        }

        subgraph cluster_KSettleDisjunction {
            label = "KSettleDisjunction (C1 or C2)";
            k -> l;
              k -> m;
              k [label=""];
              l [label="C1"];
              m [label="C2"];
        }
    }

.. glossary::

    ``KAssignVar``
        As explained above, it chooses a variable X and creates one sub-problem for each possible value of X.

	.. _assign_and_forbid:

    ``KAssignAndForbid``
        In this case, it chooses a variable X and creates one node where X is equal to v (a value currently in X’s domain) and another node where X must be different from v.

    ``KSplitDomain``
        This branching scheme is mainly used in mixed-integer linear programming. It chooses a variable X and creates one node where X is lower or equal to a value v (not necessary in X’s domain but it must be between its lower and upper bound) and a second node where X is greater than v.

	.. _settle_disjunction:

    ``KSettleDisjunction``
        It is the only branching scheme not working on variables. It works on binary disjunctions between constraints (for example “C1 or C2”). Then it creates two nodes splitting domain in different possibilities for the status of C1 and C2.

Note that these branching schemes explore the left branch before the right one.

These ``KBranchingScheme`` often need to select an unassigned variable and choose a value. These two principles give two objects in Artelys Kalis: a ``KVariableSelector`` and a ``KValueSelector``. Some classes are inheriting from them in order to offer some usual behaviors but you may also add new ones easily.

Here are some examples of ``KVariableSelector``:

* ``KSmallestDomain``: looks for an unassigned variable having the smallest number of values in its domain.
* ``KSmallestMin``: looks for an unassigned variable having the smallest lower bound.
* ``KMaxDegree``: the degree is the static number of constraints in which a variable is involved. This selector looks for an unassigned variable having the biggest degree.

and some examples of ``KValueSelector``:

* ``KMinToMax``: returns the lower bound of a variable. It helps choosing variables in increasing order.
* ``KNearestValue``: returns the value currently in domain which is the nearest of a specific target value. It is useful for heuristics trying to be close to a wished solution.

The complete list is available in the Artelys Kalis Reference Manual.

In fact, when branching, you can distinguish 3 different objects:

* *branching scheme*: it explains how to create new nodes.
* *branching object*: the object which is involved in this branching: it can be a variable, a constraint (as seen before) but it could also be any type of object.
* *branching information*: it represents the information that must be kept while you are creating each node (it can be the last value which was given to a variable (the branching object)).

Artelys Kalis is based on these three concepts in order to help you creating many branching schemes. We will see how to do so in the following sections.

Controlling strategies used by a KSolver
========================================

Now that you have a better understanding ot the branching scheme, let’s us introduce them in our search. The control of the solution search is performed by telling the ``KSolver`` object how it must *branch* during all the tree search.

The branching schemes are represented by ``KBranchingScheme`` objects stored by the ``KSolver`` object used to solve the problem. These objects can be gathered to a ``KBranchingSchemeArray`` object. This object represents an ordered set of ``KBranchingScheme`` objects and can be declared this way:

.. tabs::
    
    .. code-tab:: c++

        KBranchingSchemeArray myBranchingArray;

    .. code-tab:: py

        myBranchingArray = KBranchingSchemeArray()

    .. code-tab:: java

        KBranchingSchemeArray myBranchingArray = new KBranchingSchemeArray();

For example, we can put into :cpp:var:`myBranchingArray` an object of the ``KAssignVar`` class: this class is a subclass of ``KBranchingScheme`` provided with Artelys Kalis. Here is how it can be done:

.. tabs::
    
    .. code-tab:: c++

        myBranchingArray += KAssignVar();

    .. code-tab:: py

        myBranchingArray += KAssignVar()

    .. code-tab:: java

        myBranchingArray.add(new KAssignVar());

Here we have built a ``KAssignVar`` object using the default constructor and put it in :cpp:var:`myBranchingArray` using the overloaded :cpp:any:`operator+=`. Assuming that we have already declared a ``KProblem`` object :cpp:var:`myProblem`, the code declaring the solver which will use our ``KAssignVar`` branching scheme:

.. tabs::
    
    .. code-tab:: c++

        KSolver mySolver(myProblem, myBranchingArray);

    .. code-tab:: py

        mySolver = KSolver(myProblem, myBranchingArray)

    .. code-tab:: java

        KSolver mySolver = new KSolver(myProblem,myBranchingArray);

Here we have used a new constructor of the ``KSolver`` class, which takes a ``KBranchingSchemeArray`` parameter in addition to the first ``KProblem`` parameter.

If your array contains more than one branching schemes, the solver will use them in the same order as in the ``KBranchingSchemeArray``. It means that at each node, the ``KSolver`` will try to branch thanks to the first branching scheme and if it is not possible, he will try with the second one and the third one, ... until it is able to make new branches. For example, you may start with ``KAssignVar`` working on a small list of variables at first and then ``KAssignVar`` on all other variables. This could be done by creating two ``KAssignVar`` objects, each of them with their specific list of variables as argument, and adding them to the ``KBranchingSchemeArray`` given to the ``KSolver``. It is really useful when your problem is bilevel: investment and scheduling, rest or type of work, ...

Here is the code:

.. tabs::
    
    .. code-tab:: c++

        KIntVarArray mainVar(myProblem, nbMainVar, 0, 1, "MainVar");
        KIntVarArray otherVar(myProblem, nbOtherVar, 0, 10, "OtherVar");
        
        KBranchingSchemeArray branchingArr;
        
        branchingArr += KAssignVar(KSmallestDomain(), KMinToMax(), mainVar);
        branchingArr += KAssignVar(KSmallestDomain(), KMinToMax(), otherVar);
        
        KSolver mySolver(myProblem, branchingArr);

    .. code-tab:: py

        mainVar = KIntVarArray(myProblem, nbMainVar, 0, 1, "MainVar")
        otherVar = KIntVarArray(myProblem, nbOtherVar, 0, 10, "OtherVar")
        
        branchingArr = KBranchingSchemeArray()
        
        branchingArr += KAssignVar(KSmallestDomain(), KMinToMax(), mainVar)
        branchingArr += KAssignVar(KSmallestDomain(), KMinToMax(), otherVar)
        
        mySolver = KSolver(myProblem, branchingArr)

    .. code-tab:: java

        KIntVarArray mainVar = new KIntVarArray(myProblem, nbMainVar, 0, 1, "MainVar");
        KIntVarArray otherVar = new KIntVarArray(myProblem, nbOtherVar, 0, 10, "OtherVar");
        
        KBranchingSchemeArray branchingArr = new KBranchingSchemeArray();
        
        branchingArr.add(new KAssignVar(new KSmallestDomain(), new KMinToMax(), mainVar));
        branchingArr.add(new KAssignVar(new KSmallestDomain(), new KMinToMax(), otherVar));
        
        KSolver mySolver = new KSolver(myProblem, branchingArr);

Here you can also see that ``KAssignVar`` has different constructors and that one of them is using a ``KVariableSelector``, a ``KValueSelector`` and a list of variables.

The default strategy
====================

In order to prevent Artelys Kalis to stop in a non-final state at one node (it means that some variables are not instantiated) for which current branching schemes given to the solver cannot provide new branching objects (in fact new nodes), or the user to specify branching schemes to be used, a default branching scheme will always be applied after the one given to the ``KSolver``. This is a ``KAssignVar``: in the particular context of the default scheme, it will
choose among all the variables the one with the smallest domain and assign it the Largest possible value first.

.. note::

    For some branching schemes, there is *always* at least one branching object to work on. That is for example the case with a ``KAssignVar`` working with all variables: either a given node is a solution of the problem and no more branching has to be performed, or there is at least one non instantiated variable. In the latter case, the ``KAssignVar`` can choose the non instantiated variable to build new nodes. The outcome of this is that if you put a branching scheme like a ``KAssignVar`` working with all variables at the top of your branching schemes array, *the other branching schemes will never be used*.