Dependency-Curated Large Neighbourhood Search

Large neighbourhood search (LNS) [23, 19] is a method that combines systematic search with local search to improve the scalability of the former on constrained optimisation problems using heuristics of the latter. LNS starts from an incumbent solution that is iteratively improved by fixing a subset of the variables to their values in the incumbent solution and a value for each remaining variable is found and assigned via solving (such as constraint programming-style propagation and search). This method has been very successful on a wide variety of problems, such as vehicle routing [23, 2], bin packing [28], and scheduling [8, 24].

Traditionally, a modeller has to construct a problem-specific selection heuristic for the determination of the subset of variables to fix [8, 22]. However, there are now many variants of LNS that automatically determine that subset with good search performance, such as (but not limited to) (reverse) propagation guided LNS [18], cost impact guided LNS [12], explanation-based LNS [20], self-adaptive LNS [26], and variable-relationship guided LNS [24].

In most combinatorial optimisation solvers, such as for mixed integer linear programming, constraint programming (CP), Boolean satisfiability (SAT), and constraint-based local search (CBLS), when some variable $x$ becomes fixed, the values of some other variables can be found and assigned via search-free unique solving (via inference such as CP propagation, SAT unit propagation, and CBLS invariant propagation). Therefore, the relations between $x$ and the assigned variables are functional dependencies. In CBLS, these functional dependencies are fundamental and heavily studied [15, 16, 27, 10]. We have not found generic LNS selection heuristics or CP branching heuristics that automatically exploit these functional dependencies that are exploited in CBLS. However, they are often exploited manually by the modeller when for example creating a problem-specific CP branching heuristic that guides search.

Our contributions are:

• $\mathrm{■}$

  applying from CBLS to a CP context (and hence to CP-based LNS) the idea of a directed possibly cyclic graph that is induced by the functional dependencies between variables via the constraints of the model;

• $\mathrm{■}$

  designing a scheme that exploits the induced directed graph to remove variables from the LNS space that are functionally defined by others;

• $\mathrm{■}$

  describing how our scheme can be automated;

• $\mathrm{■}$

  showing that state-of-the-art generic LNS selection heuristics are easily extended to make use of our scheme;

• $\mathrm{■}$

  showing that our scheme often improves the overall performance when used with state-of-the-art generic selection heuristics; and

• $\mathrm{■}$

  showing that our scheme, when used with a naïve generic LNS selection heuristic that fixes a set of variables selected at random inside each LNS iteration, is competitive with more elaborate state-of-the-art generic LNS selection heuristics, even when they also use our scheme.

We first give related work from CBLS in Section 2, before we present how to apply it to a CP context (and hence to CP-based LNS) in Section 3. We then give an example of functional dependencies for a CP model in Section 4. We describe generic LNS selection heuristics from the literature in Section 5. We present our scheme in Section 6. We give our experiment setup in Section 7 and discuss the results in Section 8. Finally, we conclude in Section 9.

In constraint-based local search [15, 16, 27, 10] (CBLS), each constraint of the problem is either made to always implicitly hold via the initialisation and neighbourhood, or replaced by one or more invariants, where an invariant (also called a one-way constraint) defines a subset of the constrained variables, called its output variables, of the replaced constraint by the remaining variables, called its input variables. Invariants that replace a constraint of the problem are called violation invariants, where a violation invariant introduces and defines a violation variable, absent in the problem, which takes the value $0$ if the replaced constraint holds, else a positive value, usually proportional to the amount of violation. The replaced constraint is therefore softened, but only an assignment of the variables where all violation variables take the value $0$ is a solution, as it satisfies all the constraints of the problem.

The invariants and variables induce a directed graph, called the invariant graph, with the invariants and variables as vertices and the definitions of variables via invariants as arcs, where each variable has an outgoing arc to each invariant that it is an input variable to and an incoming arc from the invariant that defines it (if any). Note that in any CBLS model, any variable is defined by at most one invariant. All the possibly multiple (if not zero) source vertices and possibly multiple (if not zero) sink vertices are variables, where the source variables transitively define the remaining variables via the invariants.

As an example of an invariant graph, consider the subset-sum constraint satisfaction problem, where given a set of $n$ integers $v_i$ and an integer $t$, a subset of the set is to be found that sums to exactly $t$. A corresponding invariant graph contains $n$ integer variables, where each variable $x_i$ takes the value $v_i$ if $v_i$ is in the subset and $0$ otherwise; one invariant with as inputs the variables $x_i$ and as output the integer variable $s$, which takes as value the sum of the integers in the subset; and one violation invariant with as input $s$ and as output the violation variable $v$, which is to be minimised and takes as value the absolute difference between $s$ and $t$. This amounts to softening the constraint ${\sum }_{i=1}^n{x}_i=t$. The source variables are the variables $x_i$, and they transitively define the other variables via the two invariants. Any assignment of the variables $x_i$ where $s$ takes the value $t$ is a solution, as $v=0$ then, which is minimal. The invariant graph is shown in Figure 1, where circled vertices are variables and boxed vertices are invariants.

During a CBLS-style search, only the values of the source variables are changed, while the values of the remaining variables are found via CBLS-style invariant propagation.

In CBLS, the variables and constraints induce the invariant graph of definitions of variables, whether this is done by the CBLS modeller or by automated analysis of, say, a MiniZinc [17] model [4]. In the sequel, we apply the idea of the induced invariant graph to CP models to find functional definitions of variables, which can be exploited during LNS.

In a CP model, some constraints are dependency constraints, where a dependency constraint $c$ on the variables $𝒳=ℐ\cup 𝒪$ determines the values of the variables in $𝒪$ when the variables in $ℐ$ become fixed. We can view $c$ as a function that determines the values of output variables $𝒪$ when the input variables $ℐ$ become fixed. We say that $c$ is a dependency constraint and that $ℐ$ functionally defines $𝒪$ via $c$, denoted by $ℐ\stackrel{c}{⟹}𝒪$, or simply that $ℐ$ functionally defines $𝒪$.

For example, consider the integer variables $y$ and $i$, the array $𝒫$ of integers, and the constraint $\text{Element}(𝒫,i,y)$, which constrains $y$ to be equal to the integer in $𝒫$ at index $i$. When $i$ becomes fixed to some value $v$, the value of $y$ becomes assigned to the integer in $𝒫$ at index $v$. The constraint is a dependency constraint, via which $i$ functionally defines $y$.

As another example, consider the Boolean variable $b$, the array of Boolean variables $ℬ$, and the constraint $\text{Exists}(ℬ,b)$, which constrains $b$ to take the value True if any of the variables in $ℬ$ takes the value True, else $b$ takes the value False. The constraint is a dependency constraint, via which $ℬ$ functionally defines $b$.

Some constraints are not dependency constraints. For example, consider the integer variables $x$ and $y$, and the constraint $\text{LessEqual}(x,y)$, which enforces that $x$ is smaller than or equal to $y$. This constraint is not a dependency constraint as neither $x$ nor $y$ can be defined via it by the other variable.

For a CP model, the dependency constraints and the variables induce a directed graph, called the dependency graph [13], where for each set $ℐ$ of variables that functionally defines a set $𝒪$ of variables via some dependency constraint $c$, there is a vertex $d$, an arc $x\to d$ for each vertex $x\in ℐ$, and an arc $d\to y$ for each vertex $y\in 𝒪$. Note that the dependency graph is possibly cyclic: we will see an example of an acyclic dependency graph in Figure 2 in Section 4, and an example of a cyclic dependency graph in Figure 3 in Section 7.2.3. Also note that all the variables and all the dependency constraints are in the dependency graph, while the other (non-dependency) constraints are not.

A dependency graph differs from an invariant graph as follows:

• $\mathrm{■}$

  in a dependency graph, a variable can have any number of incoming arcs, while it can have at most one in an invariant graph;

• $\mathrm{■}$

  a dependency graph does not contain non-dependency constraints, while in an invariant graph, all constraints that are not made to implicitly hold are encoded (as invariants); and

• $\mathrm{■}$

  an invariant graph is required when performing CBLS-style invariant propagation, while a dependency graph is not required when performing CP-style solving (neither in search nor in CP-style propagation).

For any acyclic dependency graph, the source variables transitively functionally define all remaining variables. Therefore, for any acyclic dependency graph, the minimum-cardinality set of such variables is the set of source variables. However, this does not always hold for a cyclic dependency graph (as we will see for the dependency graph shown in Figure 3 in Section 7.2.3). In Section 6, we present a greedy scheme that, given a CP model (inducing a cyclic or acyclic dependency graph), finds a low-cardinality set of such variables, which can be exploited to guide LNS.

We now give an example to show how the dependency graph is constructed from a CP model. The car sequencing (constraint satisfaction) problem [5] has a set of car classes, each class with a set of mandatory features (called options in [5]), each feature with a capacity on how many cars of that feature can be produced in a subsequence of given size, and an order stating how many cars of each class to produce. The problem is to find a production sequence for all ordered cars, such that the capacity restrictions on features are satisfied and all ordered cars are produced. Since LNS can only be performed on constrained optimisation problems, we transform the problem into one by relaxing it into the relaxed car sequencing (RCS) problem by $(i)$ including an additional dummy class of car that has no features; $(ii)$ relaxing the constraint that all ordered cars are to be produced by replacing it by a constraint that each car is to be produced at most once; and $(iii)$ introducing an objective variable that is to be minimised and is the number of dummy cars that are produced. Note that for any solution to the relaxed problem, if the objective variable takes the value $0$, then the solution satisfies the constraints of the original problem, as all cars are produced.

A model for RCS in the solver-independent MiniZinc language [17] is in Listing 1.

Lines 2–8 declare the set of cars to be produced, the set of features, the set of car classes, the array of the sizes of the feature subsequences, the array of the maximum capacities for the feature subsequences, the array of the numbers of ordered cars for each class, and the two-dimensional matrix of the features that the car classes use respectively. The sets of cars to be produced, features, and car classes are required to be intervals. Lines 9–13 declare the dummy car class, the set of car classes including the dummy car class, and the two-dimensional matrix of the features that the car classes and dummy class use, respectively. On line 14, the array class of variables is declared, where class[c] denotes the class of car c. On lines 15–17, the two-dimensional matrix carHasFeature of variables is declared and is functionally defined by class, where carHasFeature[c,f] denotes if feature f is to be installed on car c. On lines 18–19, the array numProduced of variables is declared and is functionally defined by class, where numProduced[c] denotes the number of cars of class c that are actually produced. Line 20 enforces that no car class is overproduced. Lines 21–23 enforce that the feature capacity is not violated for any subsequence. Finally, Line 24 declares that the number of dummy cars is to be minimised.

This model was retrieved from the MiniZinc Benchmark repository and relaxed from a constraint satisfaction model into a constrained optimisation model as well as rewritten by renaming parameters and variables and replacing each constraint predicate with the corresponding constraint function where possible.²²2The MiniZinc Benchmark repository: https://github.com/MiniZinc/minizinc-benchmarks

The acyclic dependency graph for RCS with three cars to produce, two features, and two car classes induced by the MiniZinc model in Listing 1 is shown in Figure 2, where circled vertices are variables and boxed vertices are dependency constraints.

LNS [23, 19] is an iterative method for optimisation problems, starting from an incumbent feasible solution that is improved during search. In every iteration, first a subset of the variables, called the freeze set, is selected and the values of these variables are kept from the incumbent solution, then search (for example CP-style branch and bound search) is performed until some stopping criterion is met, and finally, if a better solution was found, then the incumbent solution is replaced by it and a constraint that all future solutions must be better than the new incumbent solution is added. The selection of a freeze set is done via a selection heuristic, which can be either problem-specific or generic. Typically, problem-specific selection heuristics (such as [8, 22]) cannot easily be reused between problems.

In Section 5.1 we give a naïve generic selection heuristic that selects the freeze set at random, and in Sections 5.2 to 5.4 we give more elaborate generic selection heuristics from the literature.

In the selection heuristics of PG-LNS, RPG-LNS, and VRG-LNS, the freeze set is gradually updated inside each LNS iteration to include variables such that many other variables are assigned values via CP-style propagation [18, 24]. For these selection heuristics, such variables are found either experimentally or heuristically during search. We now show such variables can also be found by exploiting the dependency graph before search starts and how they can be used by any LNS selection heuristic.

We call any set of variables that transitively functionally define all remaining variables a set of search variables, as only their values must be found via search.

Consider a CP model with the set $𝒱$ of variables. Finding a set $𝒮\subseteq 𝒱$ of search variables is trivial as $𝒱$ itself is a set of search variables, though of maximum cardinality. Our idea is that the smaller the set $𝒮$ is, the more CP-style propagation will occur, as the value of each variable in $𝒱\setminus 𝒮$ is found and assigned via only propagation (as $𝒮$ transitively functionally defines $𝒱\setminus 𝒮$). Additionally, for any (generic or problem-specific) selection heuristic, if the freeze set is forced to become a subset of $𝒮$, then the LNS space is reduced, no data has to be stored, and no operations have to be performed on any variable in $𝒱\setminus 𝒮$ by the selection heuristic, potentially improving its memory footprint and running time.

Note that if the dependency graph is acyclic, then the minimum-cardinality set of search variables is the set of source variables. Otherwise, the dependency graph contains at least one strongly connected component (SCC) with two or more vertices, and finding a low-cardinality set of search variables is a subtle issue, as discussed next.

As the variables and dependency constraints are known up-front, a low-cardinality set of search variables can be constructed before search starts. A (generic or problem-specific) selection heuristic can use the constructed set of search variables throughout search by forcing the freeze set to be a subset of that set.

Our scheme, called the dependency curation scheme (DCS), finds a low-cardinality set of search variables given the variables, vertices, and arcs of a dependency graph. It is shown in greedy Algorithm 1, where:

• $\mathrm{■}$

  function $\text{stronglyConnectedComponents}(𝒩,𝒜)$ returns an ordered list of SCCs for vertices $𝒩$ and arcs $𝒜$, such that each SCC is before all other SCCs that are reachable from it, like [25] but where the returned list is reversed (as the graph is explored in depth-first order);

• $\mathrm{■}$

  function $\text{in}(𝒜,v)$ returns all incoming arcs to vertex $v$ in the set $𝒜$ of arcs;

• $\mathrm{■}$

  function $\text{out}(𝒜,v)$ returns all outgoing arcs from vertex $v$ in the set $𝒜$ of arcs;

• $\mathrm{■}$

  function $\text{stack}()$ returns an empty stack;

• $\mathrm{■}$

  function $\text{empty}(𝒵)$ returns True if the stack $𝒵$ contains no elements, else False;

• $\mathrm{■}$

  function $\text{pop}(𝒵)$ removes the top-most element from the stack $𝒵$ and returns it; and

• $\mathrm{■}$

  procedure $\text{push}(𝒵,v)$ pushes element $v$ onto stack $𝒵$.

First, the sets $𝒲$ of visited vertices and $𝒮$ of search variables are initialised, lines 2–3. Each SCC of the dependency graph is iterated over, where SCC $𝒳$ is iterated over before all other SCCs that are reachable from $𝒳$ are iterated over, line 4. While there are unvisited variables in $𝒳$, line 5, a variable $x$ with the lexicographically lowest priority is retrieved from the unvisited variables in $𝒳$, where the priority of a variable $y$ is $(i)$ the in-degree of $y$ and $(ii)$ the opposite of the out-degree of $y$, line 6. Variable $x$ is added to the set $𝒮$ of search variables, line 7, and to the set $𝒲$ of visited vertices, line 8. The empty stack $𝒵$ is created, line 9, before $x$ is added as the top-most element to $𝒵$, line 10. While $𝒵$ is not empty, line 11, its top-most element $u$ is removed, line 12. The outgoing arcs ${𝒜}_u$ from $u$ are retrieved, line 13, and removed from $𝒜$, line 14. For each arc $(u,v)\in {𝒜}_u$, where $v$ has not been visited and either $(i)$ is a variable or $(ii)$ has no incoming arcs in $𝒜$, line 15, vertex $v$ is added to the set $𝒲$ of visited vertices, line 16; its incoming arcs are removed from $𝒜$, line 17; and $v$ is added as the top-most element to $𝒵$, line 18. Finally, the found set $𝒮$ of search variables is returned, line 19.

Note that Algorithm 1 is greedy as the selection of a search variable $x$, line 6, potentially makes the set $𝒮$ not a minimal-cardinality set of search variables.

For example, consider the car sequencing problem given in Section 4 with three cars, two features, and two car classes; its MiniZinc model in Listing 1; and its dependency graph in Figure 2. The dependency graph contains 16 SCCs: one for each vertex. Algorithm 1 first creates the initially empty sets of search variables and visited vertices, lines 2–3. The sets $\left\{c_1\right\}$, $\left\{c_2\right\}$, and $\left\{c_3\right\}$ of vertices are the first three SCCs that are iterated over, as $c_1$, $c_2$, and $c_3$ are the only vertices without incoming arcs, line 4. The remaining lines then explore the dependency graph in a fashion similar to depth-first search, starting from these source variables, where traversed outgoing arcs are removed and outgoing arcs from any non-variable vertex are only traversed if all its incoming arcs have been traversed and removed. The dependency graph is acyclic, and therefore the variables $c_1$, $c_2$, and $c_3$ transitively functionally define the remaining variables and actually form (in this case) a minimum-cardinality set of search variables.

If each strongly connected component only has a single vertex, then the dependency graph is acyclic and the algorithm can be bypassed, as the minimum-cardinality set of search variables is the set of source variables.

For a CP model, DCS finds a low-cardinality set of search variables that can be used with any (generic or problem-specific) selection heuristic by forcing its freeze set to be a subset of that set of search variables. Note that DCS itself is not a selection heuristic and must be used together with one, such as any of the generic selection heuristics in Sections 5.1 to 5.4.

VRG-LNS (Section 5.4) [24] is similar to DCS as both find the information of relations on variables via constraints before LNS iterations. However, they differ from each other, as VRG-LNS uses both dependency and non-dependency constraints that each pair of variables share, while DCS uses the functional definitions of variables via only dependency constraints.

In Section 7.1, we give the details of our extensions to the solver that was used for the experiments. In Section 7.2, we describe how we selected the problems and for each problem, its specification and how its initial incumbent solutions are generated.

We ran our experiments on a desktop computer with an ASUS PRIME Z590-P motherboard, a $3.5$ GHz Intel Core i9 11900K processor, and four $16$ GB $3200$ MT/s DDR4 memories, running Ubuntu $\mathrm{22.04.4}$ LTS with GCC (the GNU Compiler Collection) 11.

For each selection heuristic, both with DCS and without DCS, and each problem instance, we ran $10$ independent runs, each under a timeout of $3$ minutes from the same initial incumbent solution.

We used the scoring function $100\cdot (o-b)÷i$ proposed in [1] and used in [24], where for each instance, the mean objective value over the $10$ independent runs is denoted by $o$, the best found objective value over any run for the instance is denoted by $b$, and the objective value of the initial incumbent solution is denoted by $i$. Therefore, the scores range over the closed continuous interval $[0,100]$, where a low score is better than a high one.

The results are shown in Table 1 and Figure 4.

For all generic selection heuristics, using DCS improves performance for RCS, SMSD, and TSPTW, but worsens performance for JSP. These results support our conjectures that using DCS improves performance for RCS and SMSD, but does not improve performance for JSP. For JSP and each generic selection heuristic except VRG-LNS, using DCS has significantly worse performance than not using it. For JSP and VRG-LNS, using DCS has similar performance to not using it. However, there are a few JSP instances where using DCS with VRG-LNS, PG-LNS, and RPG-LNS has significantly better performance than when not using it. For RCS and each selection heuristic, the performance of using DCS is significantly better than when not using it. For both SMSD and TSPTW and each selection heuristic, the performance of using DCS is better than when not using it. Additionally, for RCS, SMSD, and TSPTW, using DCS makes the naïve randomised LNS competitive with the remaining more elaborate generic selection heuristics, even when they use DCS.

We have presented our dependency curation scheme (DCS), which can be used with any (generic or problem-specific) LNS selection heuristic. We have compared the performance of a naïve generic randomised selection heuristic and more elaborate state-of-the-art generic selection heuristics from the literature both with and without DCS, revealing overall improved performance when using DCS. Our experiments show that the performance of using DCS with the naïve randomised selection heuristic is competitive with the more elaborate state-of-the-art generic selection heuristics, even when they use DCS.

In future work, we intend to implement for our extension of the Gecode-based portfolio solver [11] our dependency curation scheme, so that the solver works without the modeller needing to provide (a generator that finds) a set of search variables. Once our scheme is implemented, we intend to compare the performance of the generic selection heuristics, both with and without DCS, on all optimisation problems in the MiniZinc [17] benchmark repository, to verify the results of this paper and to compare our extended Gecode-based portfolio solver with other state-of-the-art optimisation solvers. Additionally, we intend to extend the (non-portfolio) Gecode [6] CP solver by implementing our scheme and a naïve randomised generic LNS selection heuristic, thereby allowing a modeller to easily use competitive LNS for any MiniZinc constrained optimisation model.

Also, for VRG-LNS, a variable is selected for exclusion from the freeze set if it shares a constraint with a previously excluded variable $x$. When used with DCS, each variable $y$ that does not share a constraint with $x$ but that transitively functionally defines a variable that does so should be eligible for selection. Our idea is to make this modification to VRG-LNS and empirically test if it improves performance when used with DCS.

Finally, we intend to create a generic branching heuristic for CP-style tree search, where the variables that are selected to be branched over must be a subset of the low-cardinality set of search variables found by DCS.