Exploring Classical and Learned Local Search Heuristics for Combinatorial Optimizationby@heuristicsearch

Exploring Classical and Learned Local Search Heuristics for Combinatorial Optimization

tldt arrow

Too Long; Didn't Read

This section delves into the realm of local search heuristics in combinatorial optimization, covering classical heuristics and advanced learned heuristics like ECO-DQN and GNN-SAT. It highlights the evolution of machine learning integration in solving CO problems, showcasing the advancements in algorithmic approaches.
featured image - Exploring Classical and Learned Local Search Heuristics for Combinatorial Optimization
Aiding in the focused exploration of potential solutions. HackerNoon profile picture


(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.

Abstract & Introduction

Related work

Evaluation for Max-Cut

Evaluation for SAT

Summary and Outlook, References

Supplementary Materials

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.