Exploring Classical and Learned Local Search Heuristics for Combinatorial Optimization

Authors: (1) Ankur Nath, Department of Computer Science and Engineering, Texas A&M University; (2) Alan Kuhnle, Department of Computer Science and Engineering, Texas A&M University. 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. This paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Ankur Nath, Department of Computer Science and Engineering, Texas A&M University; (2) Alan Kuhnle, Department of Computer Science and Engineering, Texas A&M University. Authors: Authors: (1) Ankur Nath, Department of Computer Science and Engineering, Texas A&M University; (2) Alan Kuhnle, Department of Computer Science and Engineering, Texas A&M University. Table of Links Abstract & Introduction Abstract & Introduction Related work Related work Evaluation for Max-Cut Evaluation for Max-Cut Evaluation for SAT Evaluation for SAT Summary and Outlook, References Summary and Outlook, References Supplementary Materials 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. This paper is available on arxiv under CC 4.0 DEED license. This paper is available on arxiv under CC 4.0 DEED license.