An Architecture for Composite Combinatorial Optimization Solvers

Reyes-Amaro et al. [21] proposed the Parallel-Oriented Solver Language (POSL), a framework for building interconnected meta-heuristic based solvers that work in parallel. POSL focuses on sharing not only information but also behaviors among solvers, allowing for solver modifications during runtime. While POSL shares similarities with our proposed solver architecture, our work emphasizes the use of a Domain Specific Language (DSL) and incorporates meta-learning algorithms for optimizing solver parameters and architecture.

Cahon et al. [7] introduced ParadisEO, a white-box object-oriented software framework dedicated to the flexible design of metaheuristic algorithms for combinatorial optimization. ParadisEO provides a broad range of metaheuristic components and encourages code reusability, allowing users to design their own solvers by assembling and customizing existing components. Our proposed architecture shares the idea of modularity and code reusability with ParadisEO but also emphasizes the use of a DSL to connect components and incorporates meta-learning algorithms for optimization.

Durillo and Nebro [10] developed jMetal, a Java-based framework for multi-objective optimization with metaheuristics. jMetal provides a rich set of components and tools for designing, experimenting with, and benchmarking metaheuristic algorithms. While jMetal focuses on multi-objective optimization, our proposed architecture is designed for general combinatorial optimization problems and emphasizes the use of a DSL and meta-learning algorithms for optimizing solver parameters and architecture.

In summary, several approaches have been proposed to facilitate the development of metaheuristic-based solvers for combinatorial optimization problems. Our proposed modular solver architecture builds upon existing work by providing a problem-independent architecture design, incorporating a Domain Specific Language for connecting components, with plans to incorporate meta-learning algorithms to automatically optimize solver parameters and architecture.

Within the solver, the processing of solution candidates follows defined pathways, formally represented as a directed graph $G=(V,E)$, where $V$ is the set of operators and $E$ represents the connections between them, which we call Configuration Streams. Each edge $e\in E$ corresponds to a Configuration Stream that transmits configurations (solution candidates) from one operator to another.

Operators are the functional components that transform configurations as they flow through the solver pipeline. Each operator implements a specific algorithmic behavior that forms part of the overall search process.

Next, we present the core operators within the architecture:

Init:

Responsible for setting up the problem domain, encoding the CSP model into a solver-compatible representation (which is then used by other components to generate and evaluate solution candidates), and defining the search space and the domain of the decision variables, the objective function, constraints, and other relevant information (meta-data).

Formally, the Init operator can be defined as:

${𝒪}_{\text{Init}}:\mathrm{\Theta }\to 𝒮$

(2)

It encodes the problem instance $\mathrm{\Theta }$ into a solver-compatible representation $𝒮$, which includes definitions for $V$ (Variables), $D$ (Domains), $f:𝒜\to ℝ$ (objective function), and the set of constraints $𝒞$ that implicitly define the solution space $\mathrm{\Omega }$. The Init operator can be parameterized with $r$ (random) or $h$ (heuristic) initialization strategies (illustrated in Figure 2).

Generate:

Responsible for instantiating the initial set of solution candidates within the defined search space. This operator transforms the abstract problem definition into concrete configuration instances that serve as the starting point for the optimization process. Formally, the generate operator can be defined as:

${𝒪}_{\text{Generate}}:𝒮\to 𝒫(𝒜)$

(3)

Where $𝒫(𝒜)$ denotes the set of configurations, allowing for the generation of either a singleton set (single configuration) or a population of configurations (multiple candidates). The operator’s behavior can be parameterized with:

• $\mathrm{■}$

  $n=|𝒫(𝒜)|$: number of generated configurations.

• $\mathrm{■}$

  $\sigma$: initialization strategy.

  • –

    ${\sigma }_r$: Random, assigns values to decision variables according to a uniform probability distribution over their respective domains.

  • –

    ${\sigma }_h$: Heuristic, employs problem-specific knowledge to generate configurations with potentially higher initial quality.

Neighbourhood:

Performs moves in the search space to generate neighboring solutions. It supports various move types including swap, shift, block moves or any other move that can be defined for the problem at hand.

A Neighbourhood operator, defined as: ${𝒪}_{\text{Neighbourhood}}:𝒜\times ℳ\to 𝒫(𝒜)$
is a function that, given a configuration $c\in 𝒜$ and a move type $m\in ℳ$, computes the corresponding set of neighbours, denoted by $N(c,m)\in 𝒫(𝒜)$.

Where $N(c,m)$ is the set of neighbours of configuration $c$ generated using move type $m\in ℳ=\{\text{swap},\text{insert},\text{delete},\text{replace},\mathrm{\cdots }\}$. The specific neighbours generated depend on the implementation associated with the move type $m$.

When a stream delivers a set of configurations $C=\{c_1,c_2,\mathrm{\dots },c_k\}$ to this operator, the intended architectural behavior is that the operator is implicitly applied to each configuration in the set. This would conceptually produce a collection of neighbour sets $\{N(c_1,m),N(c_2,m),\mathrm{\dots },N(c_k,m)\}$.

Accept:

This operator determines whether to accept or reject a candidate configuration $c_{\text{candidate}}$ based on the current configuration $c_{\text{current}}$ and a chosen acceptance criterion $a$. Formally, it is a function ${𝒪}_{\text{Accept}}:𝒜\times 𝒜\times 𝒬\to 𝒜$ defined as:

(4)

where $a\in 𝒬$ represents the selected acceptance criterion from a set of possible strategies.

The acceptance criteria in $𝒬$ include (but not limited to):

Always:

The candidate is always accepted: $a_{\text{always}}(c_{\text{current}},c_{\text{candidate}})=\text{true}$.

Improvement:

Accepted only if it improves the current solution: .

Probabilistic:

Acceptance with a fixed probability $p$: Let $u\sim \text{Uniform}(0,1)$, then .

Temperature-based (Simulated Annealing):

Accepts improving solutions, or worsening ones with a probability dependent on a temperature parameter $T$. Let $\mathrm{\Delta }f=f(c_{\text{candidate}})-f(c_{\text{current}})$:

Loop:

This operator repeats the execution of an internal operator or sequence of operators until a specific termination condition is met.

Formally, it is represented as ${𝒪}_{\text{Loop}}:(𝒜\to 𝒜)\times 𝒯\times 𝒜\to 𝒜$.

Where $c^{(0)}=c_{\text{initial}}$, and $c^{(i)}=\text{Op}(c^{(i-1)})$ for $i\ge 1$.

The loop terminates after $k$ iterations, where $k$ is the smallest index for which the termination condition $\tau \in 𝒯$ is true (the condition’s evaluation may depend on the current iteration $k$, the current configuration $c^{(k)}$, elapsed time, solution history, etc.). The output of the Loop operator is the final configuration $c_{\text{final}}=c^{(k)}$.

The termination conditions $\tau$ supported are: iteration count (i.e. stopping after a fixed number of iterations ($i_{\text{max}}$)), exceeding a specific time limit ($t_{\text{max}}$), convergence (reaching a point where the solution quality has not significantly improved over a certain period, defined by a threshold $ϵ$), or achieving a desired target objective function value ($f_{\text{target}}$).

The connectors are the links between components that allow for a custom flow of data within the solver. They can be used to merge or split configuration streams (enabling parallelization of the search process [16]). Just like the loop operator (although fundamentally different), the connectors are not operators in the traditional sense, as they are not responsible for performing any transformation on configurations, but rather, only for controlling the execution flow within the solver.

There are two types of connectors:

• $\mathrm{■}$

  DEMUX: Split a single configuration stream into multiple streams, each of which can be processed separately. ${𝒪}_{\text{DEMUX}}:𝒜\times \mathbb{N}\times ℬ\to 𝒫(𝒜)$ is a function that’s defined as:

  ${𝒪}_{\text{DEMUX}}(c,n,p)=\{c_1,c_2,\mathrm{\dots },c_n\}$

  (5)

  Where:

  • –

    $c\in 𝒜$ is the input configuration

  • –

    $n\in \mathbb{N}$ is the number of output streams

  • –

    $p\in ℬ$ is a flag indicating whether the streams should be processed in parallel

  • –

    $c_i=c$ for all $1\le i\le n$ (the same configuration is sent to all output streams)

• $\mathrm{■}$

  MUX (Multiplexer/Selector): This component acts as a selection point, merging multiple candidate configuration streams and potentially comparing them to select a single output configuration. Formally, it can be represented as a function:

  ${𝒪}_{\text{MUX}}:𝒫(𝒜)\times \mathbb{N}\times 𝒮\to 𝒜$

  (6)

  Given a set of incoming candidate configurations $C_{\text{candidates}}=\{c_1^{\prime },c_2^{\prime },\mathrm{\dots },c_n^{\prime }\}\in 𝒫(𝒜)$, and a selection strategy $s\in 𝒮$, and an index $i\in \mathbb{N}$ the MUX outputs a single selected configuration $c_{\text{selected}}\in C_{\text{candidates}}$.

  Indexed Candidate ($i$):

  Select the candidate $c_i^{\prime }$ arriving from the $i$-th conceptual input stream (this refers to the stream source, not an ordering within the set $C_{\text{candidates}}$).

  Predicate based selection:

  Select the candidate $c_i^{\prime }$ where $s(c_i^{\prime })=\text{true}$ for $1\le i\le n$. The set $𝒮$ of selection strategies includes, but is not limited to:

  • –

    Best: $s_{\text{best}}(c_i)=f(c_i)={\min }_{1\le j\le n}f(c_j)$ for minimization

  • –

    Random: $s_{\text{random}}(c_i)=\text{true}$ with probability $\frac{1}{n}$

Leashed solvers are composite entities within the framework that encapsulate a set of operators to act as a singular unit. Think of a leashed solver as a complete, potentially complex, solver (i.e. a local search algorithm [13], or even another metaheuristic) that is embedded within a larger solver architecture but operates under strict external control - it’s kept ”on a leash” by the primary solver framework. The key aspects of this concept are:

• $\mathrm{■}$

  Encapsulation: A leashed solver bundles a complete metaheuristic solver, either external or a composite of of MoSCO operators (might also include its own loops, state, and logic) into a single reusable entity.

• $\mathrm{■}$

  Externally Controlled execution: This is the crucial “leash” part. The enclosing solver dictates when the leashed solver is executed, what input it receives (e.g., a specific configuration to improve), and how long or under what condition it runs.

• $\mathrm{■}$

  Limited autonomy & resources: It doesn’t run indefinitely or consume unbounded resources. Its execution is typically bounded by parameters like iteration count, time limit, or convergence criteria.

• $\mathrm{■}$

  Stateful interaction: Given that the operators are stateless transformations, a leashed solver is expected to maintain its own internal state during execution, but this state might be reset or initialized each time it’s called by the main solver.

• $\mathrm{■}$

  Dictated purpose: The primary solver uses the leashed solver strategically as a sub-routine for a specific purpose, and not just a generic step (e.g. intensification, diversification, neighbourhood exploration). A leashed solver acts as a stateful and controllable ”sub-routine” within the pipeline, offering more complexity than a simple operator, but less independence than running a completely separate solver process.

In essence, leashed solvers allow for arbitrarily complex operations to be bundled and utilized as if they were a singular component. The driving idea is to use existing solver strategies but cap their ability to work towards a solution (hence the “leash” analogy.) Moreover, this design provides a mechanism for modularity and encourages the integration of existing specialized solvers.

The DSL grammar can be formally defined as a 4-tuple $G=(N,T,P,S)$ where:

• $\mathrm{■}$

  $N$ is the set of non-terminal symbols:

  $N=\{\text{Solver},\text{Expression},\text{Operator},\text{Sequence},\text{Loop},\text{Parallel}\}$

  (7)

• $\mathrm{■}$

  $T$ is the set of terminal symbols, consisting of operator names, parameters, and syntactic delimiters:

  • –

    Operator names: init, gen, neighbourhood, accept, …

  • –

    Syntactic delimiters: |, *, (, ), [, ], =, →, …

• $\mathrm{■}$

  $P$ is the set of production rules, with Solver as the start symbol:

  	Solver	$\to \text{Expression}$		(8)
  	Expression	$\to \text{Operator}\mid \text{Sequence}\mid \text{Loop}\mid \text{Parallel}$		(9)
  	Operator	$\to \text{OperatorName}\mid \text{OperatorName(Parameters)}$		(10)
  	Sequence	$\to \text{Expression }|\text{ Expression}$		(11)
  	Loop	$\to \text{(Expression)*}\mid \text{(Expression)*(Condition)}$		(12)
  	Parallel	$\to \text{[Expression, Expression, …]}$		(13)

• $\mathrm{■}$

  $S$ is the start symbol:

  $S=\text{Solver}$

  (14)

For future versions, we plan to implement Conditional Processing, selecting one of multiple paths based on a condition

This feature will enable more dynamic solver behavior based on runtime conditions but is not yet implemented in the current version.

Here we illustrate how common metaheuristic algorithms can be expressed using the DSL.

• $\mathrm{■}$

  Parallel Solver Branches

    solver = init | gen | DEMUX | [
      neighbourhood | accept(criterion=improvement),
      neighbourhood(move_type=swap) | accept
      ] | MUX(strategy=best)
    
  

  This solver creates two parallel search paths with different neighborhood and acceptance strategies and combines results by selecting the best solution found in either branch.

• $\mathrm{■}$

  Stochastic Local Search

    solver = init | gen(n=1) | loop(
      neighbourhood(move_type=swap) |
      accept(criterion=probability, alpha=0.5)
      )*(it=1000)
    
  

  This representation captures the essence of Stochastic Local Search:

  1. 1.

     Initialize the problem.

  2. 2.

     Generate a single starting solution.

  3. 3.

     Generate a neighbouring solution using the swap move.

  4. 4.

     Accept the neighbour if it is better than the current solution, otherwise accept with a certain probability (alpha).

  5. 5.

     repeat for 1000 iterations.

• $\mathrm{■}$

  Simulated Annealing

    solver = init | gen(n=1) | loop(
      neighbourhood(move_type=swap) |
      accept(criterion=temperature, T0=100, alpha=0.95)
      )*(it=1000)
    
  

  This specifies:

  1. 1.

     Initialize the problem.

  2. 2.

     Generate a single starting solution.

  3. 3.

     Generate a neighbouring solution using the swap move.

  4. 4.

     Accept the neighbour based on a temperature schedule (with intial temperature t0 and cooling factor alpha).

  5. 5.

     repeat for 1000 iterations.

• $\mathrm{■}$

  Tabu Search

    solver = init | gen(n=1) | loop(
      neighbourhood(move_type=swap) |
      accept(criterion=tabu)
      )*(it=1000)
    
  

  The structure of this solver is the same as the previous examples, with the difference that the accept operator uses the tabu criterion, which translates to a tabu search solver.

  $▶$ Note.

  When operators do not have parameters explicitly specified, they use their default values. In this case, the accept(criterion=tabu) operator uses a default tabu list size of 7.

• $\mathrm{■}$

  Iterated Local Search[17]

    solver = init | gen(n=1) > current_best;
    loop (
        current_best >
            perturbation_operator >
            perturbed_sol;
        perturbed_sol >
            local_search_procedure >
            new_solution;
        new_solution >
            accept(criterion=ils) >
            current_best
    ) * (iterations=1000)
    
  

  In this example, we used the variable binding notation, as well as a leashed solver to encapsulate the local search procedure. perturbation_operator and local_search_procedure are leashed solvers, created from a sequence of basic operators.

The DSL can be visually represented as a directed graph $G_V=(V,E,\lambda )$ where:

• $\mathrm{■}$

  $V$ represents the set of nodes corresponding to operators and connectors

• $\mathrm{■}$

  $E\subseteq V\times V$ represents the set of directed edges corresponding to configuration streams

• $\mathrm{■}$

  $\lambda :V\to \mathrm{\Omega }$ is a labeling function that maps nodes to their operational semantics

The mapping between DSL constructs and graphical elements follows the principles expressed in Table 1.

The simplest solver follows a linear pipeline from initialization to solution output, as shown in figure 8.

The graphical representation provides an intuitive visualization of flow of configurations and execution within the solver, making it easier to understand complex solver architectures. This complements the textual DSL by providing a clear mapping between syntactic constructs and their semantic interpretation in terms of computation and data flow. Figures 8, 9, and 10 provide examples of different solver configurations using the graphical notation.