Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem

A fast heuristic implemented to run efficiently is often better in practice than a more complicated and slow heuristic, especially when the heuristic makes heavy use of random decisions. This can be seen from the results of programming competitions such as PACE (Parameterized Algorithms and Computational Experiments), where fast randomized local search has become the default heuristic strategy among the winning solvers [3, 11, 19]. We also use this approach for our BASELINE local search. First, it makes a small number of random changes in a local area of the current solution. Then, it applies greedy improvements in random order until a local optimum is found. Finally, if the new local optimum is worse than the previous, it backtracks the changes and repeats. Compared to more complicated heuristics, the main benefit of our BASELINE heuristic is that it is inherently local. Regardless of the graph size, one iteration of the search typically only touches vertices a few edges away from where the random alteration started. Backtracking to the best solution is also local, as long as queues are used to track changes. Using queues also differentiates the implementation of our BASELINE from other heuristics, such as HILS [26], that make a copy of the entire solution instead.

The high-level idea of CHILS is a new metaheuristic we call Concurrent Difference-Core Heuristic. Instead of only trying to improve one solution, we maintain several and update each one concurrently. When used sequentially, each solution is updated round-robin. At fixed intervals, the solutions are used to create a Difference-Core (D-Core) instance based on where the solutions differ. More specifically, if a vertex is part of all or none of the solutions, it is not part of the D-Core. A formal definition of the D-Core is presented in the preliminaries in Section 2. The intuition is that the intersection of the solutions is likely to be part of an optimal solution, and where the solutions differ indicates areas where further improvements could be made. Since there is no guarantee that the intersection of the solutions is part of an optimal solution, the Concurrent Difference-Core Heuristic alternates between looking for improvements on the original instance and the D-Core. The D-Core is always constructed according to the current set of solutions. While the general Concurrent Difference-Core Heuristic can work using any heuristic method, our CHILS heuristic uses the BASELINE iterated local search.

The outline of the BASELINE local search is shown in Algorithm 1. Each search iteration starts by picking a random vertex $u$ from the graph. If the vertex is already in the solution $u\in S$, or the tightness of $u$ is one, i.e. $|N(u)\cap S|=1$, then an alternating augmenting walk (AAW) is used to perturb the current solution. If $u$ is not currently in the solution, it is added along with a random number of additional changes in its close proximity. The vertices that see a change in their neighborhood are considered “close proximity” to $u$. These vertices are continuously queued up in a queue $Q$ to find greedy improvements more efficiently later. We also use the size of $Q$ to control the amount of random changes. We stop perturbing the solution once $|Q|$ exceeds $m_q$, where $m_q$ is a hyperparameter for the BASELINE heuristic. The benefit of using $Q$ and $m_q$ is that it stabilizes the computational cost for one iteration across different graph densities. For instance, the number of changes needed to fill $Q$ in a sparse area is higher than in a dense area.

After perturbing the current solution, greedy improvements are made to find a new local optimum. Having stored the candidate vertices in $Q$ speeds up the search for this new local optima in sparse graphs. We incorporate three greedy improvement operators for greedy in BASELINE described in the following.

We give an overview of our concurrent heuristic CHILS in Algorithm 2. First, we run BASELINE on $P$ different solutions for the full graph with a time limit of $t_G$ seconds. Each solution is assigned a different random seed and slightly modified max queue size ($m_q$) to increase their difference. We also assign each solutions an id and always keep track of the best solution found so far. Note that the id of the best solution can change during the execution of the algorithm. After improving the solutions on the full graph, i.e. after $P\times t_G$ seconds, we construct the D-Core instance. This is done by removing vertices that are part of all or none of the $P$ independent sets, see Figure 1 for an example.

On the D-Core, we again start our BASELINE local search $P$ times with a time limit of $t_C$ to generate new solutions. We extend an independent set on the D-Core to the full graph by also including the vertices that were in the intersection of all $P$ solutions. This independent set can replace the previous solution with the same id. However, for solutions with an even id as well as for the best solution found so far, replacements are only made if the new solution is of higher weight. Letting half of the solutions always accept the D-Core solution helps diversify the search.

Using the D-Core helps concentrate the local search on the more difficult regions of the graph, where our $P$ solutions differ. However, since the areas where they agree are not necessarily part of an optimal solution, CHILS alternates between using the BASELINE on the original instance and the recomputed D-Core based on the current $P$ solutions.

If the number of vertices in the D-Core falls below some small constant value, it indicates that the $P$ solutions are all quite similar. Since this reduces the benefit of our approach, we perturb all solutions with an odd id, except for the best solution, and without backtracking in the case where the new local optima is worse. In Algorithm 2, this is shown as parallel_perturb on line 14, where perturbing one solution is done as described in lines 10-18 of Algorithm 1. As with accepting replacement solutions from the D-Core, perturbing only half the solutions here helps to diversify the search and escape local optima.

All the experiments were run on a machine with an Intel Xeon w5-3435X 16-core processor and 132 GB of memory, running Ubuntu 22.04.4 with Linux kernel 5.15.0-113. Both CHILS and BASELINE were implemented in C and compiled with GCC version 11.4.0 using the -O3 flag. OpenMP was used for the parallel implementations. The source code is openly available on GitHub³³3https://github.com/KennethLangedal/CHILS.

We evaluate eight instances in parallel for the sequential experiments. To ensure fairness between the algorithms, the instances start in the same order for each program, and only one program is evaluated at a time. We evaluate each heuristic once for each instance.

We compare our heuritsics BASELINE and CHILS to the state-of-the-art metaheuristic METAMIS by Dong et al. [9], and the Bregman-Sinkhorn algorithm BSA by Haller and Savchynskyy [16]. The source code for METAMIS is not publicly available, and therefore, we had to use the numbers reported in [9]. METAMIS was evaluated using the Amazon Web Service r3.4xlarge compute node running Intel Xeon Ivy Bridge Processors and was implemented in Java. The authors also ran their heuristic five times with different seeds and reported the best solution found. For the Bregman-Sinkhorn algorithm BSA, we use the variation that produces integer solutions only after reaching 0.1 % relative duality gap for the LP relaxation by recommendation from the authors [17]⁴⁴4The exact command the authors proposed and we used was mwis_json -l temp_cont -B 50 --initial-temperature 0.01 -g 50 -b 100000000 -t [seconds] [instance].

For the comparison of different algorithms, we use performance profiles [7]. At a high level, performance profiles show the relationship between the solution size or running time of each algorithm and the corresponding result produced by the best or fastest solution given by any of the algorithms. The performance profile gives each algorithm a non-decreasing, piecewise constant function. In general, the y-axis represents the fraction of instances where the objective function is better than or equal to $\tau$ times the best objective function value. For our solution quality comparison the y-axis shows the fraction of instances $\mathrm{\#}\{\text{weight}\ge \tau \ast \text{best}\}/\mathrm{\#}G$. Here, weight refers to the independent set weight computed by an algorithm on an instance, and best corresponds to the best result among all the algorithms shown in the plot. #$G$ is the number of graphs in the dataset. The parameter $\tau$ is plotted on the x-axis. For maximization problems we have . In general, algorithms are considered to perform well if a high fraction of instances are solved within a factor of $\tau$ as close to 1 as possible, indicating that many instances are solved close to or better/faster than the optimum/fastest solution found by all competing algorithms.

Our set of instances consists of 37 vehicle routing instances introduced by Dong et al. [8], see Table 3 in the Appendix. Initial warm-start solutions derived from the application and clique information for the graphs are also provided for these instances. The clique information is a clique cover of the graph, i.e. a collection of potentially overlapping cliques that cover the entire graph. METAMIS [9] and BSA [16] use this clique information.

The vehicle routing instances are significantly harder than previously used datasets. The authors of METAMIS report results for HILS that are significantly worse than the new METAMIS heuristic on these instances [9]. The authors of BSA also make a similar observation [16]. Therefore, this experiment section only focuses on the two heurstics METAMIS and BSA, and only on these new vechicle routing instances. For an extended experiment section including comparisons with older heuristics and a wider variety of test instances, see the extended version [12].

In this section, we perform experiments to find good choices for the number of concurrent solutions $P$ and the time $t$ spent improving them in the sequential version of CHILS. We choose a subset of instances for parameter tuning. For the vehicle routing instances, we used three graphs with more than 500 000 vertices and three with less than 500 000 vertices. In addition to the vehicle routing instances, we also include six other instances that stood out as particularly challenging in previous works [10, 14]. These include 3d meshes derived from simulations using the finite element method (FE) [28], OpenStreetMap (OSM) instances [27], and graphs from the Stanford Large Network Dataset Repository (SNAP) [23]. The instances chosen for these experiments are marked with a $\star$ in Table 3.

We begin our experiments with the parameter defining the number of concurrent solutions $P\in \{8,16,32,48,64\}$. The second parameter, highly correlating with $P$, is the time spent per local search run. For this experiment we set $t=t_G=t_C$ and test all $t\in \{0.1,1,2.5,5,10,20,30\}$ seconds. Recall that $t_G$ is the time spent on the original graph and $t_C$ is the time spent on the D-Core. We present the geometric mean solution weight after one hour for the different configurations of these two parameters in Table 1.

In general, we can see that the best choice for $t$ gets lower as the number of solutions $P$ increase. Comparing the configurations with the most solutions, i.e. $P=64$, the solution quality is worse than using fewer concurrent local search runs for all $t$ values tested. The best configuration we found is $P=16$ and $t=10$ seconds, resulting in a geometric mean weight of $\mathrm{14\hspace{0.17em}132\hspace{0.17em}199.66}$. Note that these choices are only optimizing running CHILS sequentially with one hour time limit.

For the state-of-the-art comparison in this section we compare our heuristics with the results of METAMIS⁵⁵5The code is not publicly available, therefore, we could not rerun the experiments. [9] and BSA [16]. The other state-of-the-art heuristics are not designed or implemented for the vechicle routing instances and perform significantly worse. Furthermore, the vertex weights for these instances are very large, which leads to problems for other heuristics that only accept weights that can be represented with 32 bits. In the extended version of this paper we provide additional experiments comparing BASELINE and CHILS against these other heuristics evaluated on a larger set of commonly used test instances [12].

Due to the size of the weights, we only see small percentage improvements despite significant differences between the solutions. However, most of the solutions found by the sequential heuristics are still not optimal, evident by the significant uplift in solution quality we get using our parallel CHILS. It is also worth mentioning that even small improvements in solution quality, especially for the vehicle routing application, can result in substantial cost reductions [9].

We include a warm-start configuration for CHILS where we start with the provided initial solutions. The METAMIS numbers for cold and warm-starts are taken from [9]. In Figure 2, we present performance profiles to compare the solution quality achieved by the algorithms with different time limits. The first two show the state-of-the-art comparison of solution quality achieved with a 6 and 30 minutes time limit respectively. As expected, the configurations with the warm start perform best with the shortest time limit, see Figure 2(a). However, if no initial solution is known, our two variants, BASELINE and CHILS, significantly outperform all competitor configurations. Note that BASELINE is performing better than CHILS on around 80 % of the instances with the 6 minute time limit, since the configuration for CHILS is optimized for running for one hour, see Section 5.3. Compared to the second profile on the right, we can see that with more time, the CHILS solutions improve most, even surpassing the METAMIS-warm results on most instances. Within this time limit, CHILS-warm finds the best solutions on almost 60 % of the instances. Furthermore, both CHILS configurations compute solutions that are at most 0.3 % worse than the best-found solution. On the other hand, on more than 38 % of the instances, BSA and METAMIS-cold find solutions which are more than 1 % worse than the best solutions found on the respective instances.

In Figure 2(c), we present the state-of-the-art comparison where all algorithms have one hour time limit and run on the original instances. Here, we can see that CHILS – with and without the initial solutions – generally performs best. The results shown here are very similar to the results computed within the shorter limit of 30 minutes; see Figure 2(b).

For the profile in Figure 2(d), however, this changes. Here, the time limit is also one hour, but we added a configuration called CHILS-parallel, which utilizes the warm start solution and runs in parallel with the configuration of $P=64$ and $t=5$ seconds, using 16 parallel threads. Additionally, we include a configuration that uses reduction rules and run CHILS on the reduced instances. Note that Dong et al. already showed that the vehicle routing instances are not easy to reduce [9]. In the experiments here, we use a new reduction approach with an extended set of reductions introduced in [12]. However, our configuration with reductions, CHILS-reduced, cannot compete with the other configurations on most instances. This means that spending time to reduce these instances is not worthwhile compared to running local search. Note that we do not evaluate BSA on the reduced instances since the clique information after the reduction process is lost. Testing even the fast reduction rules on these graphs takes considerable time. However, on MR-W-FN or MW-D-01, for example, using reduction rules does help in finding better solutions, see Table 2. Considering all of our variants, we outperform all other schemes in all but two instances, as shown in Figure 2 and Table 2. Furthermore, compared to METAMIS, our approach does not depend as much on having good initial solutions. Nevertheless, using a warm start solution can improve the performance of CHILS further.

Observation 2.

For the parallel results shown in Figure 2(d), we used the same machine as the other heuristics to ensure fairness between each program with regard to solution quality. To gain more detailed insight into the parallel scalability of our approach, we utilize a larger machine with an AMD EPYC 9754 128-core processor for our scalability experiments. Furthermore, CHILS as defined in Section 4 relies on wall time to alternate between local search on the full graph and the D-Core. This introduces variance between runs and makes it difficult to conduct scalability experiments. Therefore, we change the implementation for this section to perform a fixed number of local search iterations instead, where one iteration refers to the while loop starting on Line 2 in Algorithm 1. We also set a fixed number of CHILS iterations, referring to the while loop starting on Line 2 in Algorithm 2. By removing the wall-clock measures and using the same random seed, we ensure that the parallel and sequential versions perform the exact same computations and reach the same solution in the end.

The configuration we use for these experiments consists of 1 000 local search iterations, 10 CHILS iterations, and $P=128$. Depending on the instance, this ratio of local search on the full graph and D-Core is reasonably close to the wall-clock version with $t_G=t_C=10$. Each run was repeated five times, and the best measurement is used. We use the best measurement because, in this configuration, there is no randomness between runs. Any difference we observe in execution time is solely due to factors outside our control, such as fluctuations in clock speed and other programs running on the machine. As such, the best measure is the closest to the true execution time.

The speedup numbers for each instance are shown in Figure 3. The best scaling instance reaches a speedup of 104, while the worst is still 28 times faster than the sequential program. Figure 3 also shows the amount of memory allocated for each instance. This includes the graph, which we store using the compressed sparse row format, and additional data structures required by the heuristic. All memory allocations are done up front before starting the heuristic, and the appropriate thread initializes any thread-local data. The CPU we use has a combined L3 cache of 256 MiB. There is a clear drop in speedup around the point when the data no longer fits in the cache. This indicates that the memory bandwidth is the main bottleneck for larger instances. In terms of load balancing, there could be variations in how much work it takes to perform 1 000 local search iterations for each solution. This is because each solution has a different random seed and $m_q$ parameter. Note that this is not an issue for the version presented in Section 4, since that version uses wall time instead of local search iterations. Table 3 in the Appendix gives detailed execution time, speedup, and the amount of memory used for each instance.