Draft:Construct, Merge, Solve and Adapt

Construct Merge Solve and Adapt (CMSA) is a Metaheuristic for Combinatorial optimization introduced by Blum et al. in 2016. It employs an exact solver, which is used at each iteration for solving a sub-instance of the problem instance under consideration. This sub-instance is modified throughout the execution of the algorithm, with the objective of eventually having high-quality solutions contained in it, which can be found by the exact solver. An iteration of the algorithm can be split into four steps, which give the name of the algorithm: Construct, Merge, Solve and Adapt.

To apply CMSA to a combinatorial optimization problem, a set $C=\{c_{1},c_{2},\dots ,c_{n}\}$ of solution components needs to be defined so that every valid solution can be expressed as a subset of $C$. For example, in the case of the well-known Travelling Salesman Problem, the set of solution components could be the set of edges of the input graph, as every valid solution can be expressed as a collection of edges.

Description

For the following description of the algorithm we assume a set of solution components $C$ for the problem under consideration.

The sub-instance kept by the algorithm is a subset $C'\subseteq C$. Moreover, a value ${\text{age}}_{c}$ is also kept for each solution component $c\in C$. These keep track of how many iterations have passed since each solution component last appeared in the solution given by the exact solver. They are used in the Adapt step for deciding which solution components to erase from the sub-instance.

After initializing the sub-instance $C'$ as empty and the best solution so far $S_{\text{bsf}}$ to null, the main loop of the algorithm is entered. Hereby, the four CMSA steps are applied in order until a stopping condition, usually a time limit, is reached. The Construct step consists of probabilistically generating a number of $n_{a}$ valid solutions, which is generally done by employing a greedy probabilistic method tailored to the problem at hand. In the Merge step, the solution components of such solutions that are not already in the sub-instance $C'$ are added to it and their age is set to zero. Then, in the Solve step, the exact solver is applied restricted to sub-instance $C'$, for a time limit $t_{\text{ILP}}$. Finally, the solution obtained $S_{\text{opt}}$ and the age values are used in the Adapt step for modifying the sub-instance. The age of the solution components in $S_{\text{opt}}$ is set to zero and the age of the solution components in $C'$ not appearing in $S_{\text{opt}}$ is increased by one. Then, the solution components with an age greater than $age_{\max }$ are erased from the subinstance $C'$. Note that $n_{a}$, $t_{\text{ILP}}$ and $age_{\max }$ are the three parameters of the algorithm.

Pseudocode

The following pseudocode describes the algorithm.

Input 1: Set $C$ of solution components for the combinatorial optimization problem under consideration 
Input 2: Values for parameters $n_{a}$, $t_{\text{ILP}}$ and $age_{\max }$
$S_{\text{bsf}}={\text{null}},\ C'=\varnothing$
while CPU time limit not reached do
    for $i=1,\dots ,n_{a}$ do
        $S={\text{probabillistic}}\_{\text{solution}}\_{\text{generation}}(C)$
        for $c\in S$ and $c\not \in C'$ do
            $age[c]=0$
            $C'=C'\cup \{c\}$
        end for
    end for
    $S_{\text{opt}}={\text{apply}}\_{\text{exact}}\_{\text{solver}}(C')$
    if $S_{\text{opt}}$ is better than $S_{\text{bsf}}$ then $S_{\text{bsf}}=S_{\text{opt}}$
    ${\text{adapt}}(C',S_{\text{opt}},age_{\max })$
end while
return $S_{\text{bsf}}$

Example

Hereby, an example on how CMSA can be applied to a particular combinatorial optimization is presented. In particular, CMSA is applied to the Minimum Dominating Set problem, a classical NP-Hard combinatorial optimization problem.

Given an undirected graph $G=(V,E)$, the Minimum Dominating Set problem aims at finding a dominating set of $G$ of minimal size. Note that, a dominating set of an undirected graph $G=(V,E)$ is a subset of nodes $V'\subseteq V$ which satisfies that for every node $v\in V$ either (1) $v\in V'$ or (2) $(v',v)\in E$ for some $v'\in V'$. A node that satisfies (1) or (2) is denoted as covered by $V'$.

The only problem dependent parts of CMSA consist of the description of the set of solution components $C$, the method employed for probabilistically constructing solutions in the Construct step and the exact solver used in the Solve step, for obtaining solutions restricted to the sub-instance $C'$.

Set of solution components

As solutions to the Minimum Dominating Set problem consist of subsets of nodes, a valid set of solution components is the set of nodes of the graph. That is, $C=V$.

Method for probabilistically constructing solutions

The following notation is required for the proposed method of generating solutions. Given $v\in V$ and a subset $S\subseteq C=V$, we denote by $N[v\ |\ S]$ the set of uncovered nodes by $S$ from the closed neighborhood $N[v]=\{v'\ |\ (v',v)\in E\}\cup \{v\}$ of $v$.

An example of a method for probabilistically constructing solutions to the Minimum Dominating Set problem consists of the following probabilistic greedy approach.

Input 1: Graph $G=(V,E)$ under consideration
Input 2: Values for parameters $dr$, $l_{\text{size}}$
$S={\text{null}}$
while $S$ is not a dominating set do
    with probability $dr$ do
        add ${\text{arg max}}_{v'\in C_{\text{opt}}}\{|N[v'\ |\ s]|\}$ to $S$
    otherwise
        consider a subset $L\subseteq C_{\text{opt}}$ of size $\min\{|C_{\text{opt}}|,l_{\text{size}}\}$ such that 
        ${\big |}N[v\ |\ S]{\big |}\geq {\big |}N[v'\ |S]{\big |}$ for all $v\in L$, $v'\in C_{\text{opt}}\setminus L$
        add a node selected uniformly at random from $C_{\text{opt}}$ to $S$ 
end while

It starts with an empty solution to which it iteratively adds a node, until it forms a valid solution, that is: a dominating set. A higher probability of selection is given to nodes with a higher amount of uncovered elements by the partial solution under construction in their closed neighborhoods.

Note that this procedure depends on two parameters $dr\in [0,1]$ and $l_{\text{size}}\in \{1,2,\dots ,|V|\}$, which control the diversity of the solutions generated.

Exact solver

The following simple ILP model, together with a commercial ILP solver, can be employed as the exact solver used in the Solve step of CMSA.

$\min \sum _{v_{i}\in V}x_{i},\quad {\text{subject to}}\sum _{v_{j}\in N(v_{i})}x_{j}+x_{i}\geq 1,\ {\text{for}}\ v_{i}\in V$

Notably, the Solve step applies the exact solver to the sub-instance $C'$, hence the following constraint has to be added: $x_{i}=0$ for all $v_{i}\in C\setminus C'$.

With these three components, CMSA can be straightforwardly applied to the MDS problem.