Exploring Classical and Learned Local Search Heuristics for Combinatorial Optimization

Table of Links

Abstract & Introduction

Related work

Evaluation for Max-Cut

Evaluation for SAT

Summary and Outlook, References

Supplementary Materials

2 RELATED WORK

As stated before, we will limit our discussion to local search heuristics. For future reference, we will specifically refer to local search heuristics when discussing heuristics.

2.1 Classical Heuristics

In this subsection, we explore works that can solve diverse CO problems without polynomial time reduction. In their influential work, Khalil et al. (2017) introduced Structure-to-Vector GNN trained

with Deep Q-Networks (DQN) to address various CO problems. The resulting S2V-DQN algorithm showcased strong performance across diverse CO problems by effectively generalizing across graphs of varying sizes and topologies. Building on the work of Khalil et al. (2017) , Manchanda et al. (2019) initially trained an embedding Graph Convolution Network (GCN) in a supervised manner. Subsequently, they trained a Qnetwork using reinforcement learning (RL) to predict action values for each vertex. Their method employed GCN embeddings to prune nodes unlikely to be part of the solution set, significantly enhancing scalability compared to S2V-DQN. However, it is not applicable to problems where nodes cannot be pruned, including fundamental CO problems like the Max-Cut problem.

2.2 Generalized Learned Heuristics

Barrett et al. (2020) proposed ECO-DQN, a SOTA RL algorithm for Max-Cut. ECO-DQN improves the initial solution by navigating between the local optimal points. However, ECO-DQN uses a costly GNN at each decision step, resulting in worse scalability than S2V-DQN. To address scalability challenges in ECODQN, Barrett et al. (2022) proposed ECORD. This approach limited the costly GNN to a pre-processing step and introduced a recurrent unit for fast-action selection.

2.3 Learned Heuristics for SAT

In the domain of Boolean Satisfiability, the application of machine learning to solving SAT problems is not a new idea (Battiti and Protasi, 1997; Haim and Walsh, 2009; Flint and Blaschko, 2012; Grozea and Popescu, 2014; Ganesh et al., 2009; Liang et al., 2016). In recent years, there has been a trend in integrating GNNs with SAT solvers(Yolcu and P´oczos, 2019; Lederman et al., 2019; Kurin et al., 2020; Jaszczur et al., 2020), aiming to improve search heuristics by leveraging predictions from GNNs.