Learning Combinatorial Optimization Algorithms over Graphs

Elias Boutros KhalilH. DaiYuyu ZhangB. DilkinaLe Song

article2017NeurIPS1,791 citations

Develops a framework combining reinforcement learning and graph embeddings to automatically learn greedy heuristic algorithms for classic NP-hard problems, including Minimum Vertex Cover, Max-Cut, and the Traveling Salesman Problem.

Listen

Many critical industrial applications—including delivery vehicle routing, telecommunications scheduling, and targeted network marketing—rely on solving complex graph optimization problems. Although organizations routinely solve these problems under similar operational conditions, traditional approaches require either hand-crafted heuristic rules developed through trial and error or exact commercial solvers that become impractically slow as network sizes grow. The article demonstrates an automated framework that learns greedy heuristic algorithms by combining graph neural network embeddings with deep reinforcement learning.

The framework operates by converting a network's topology into rich node-level feature representations, which a reinforcement learning policy uses to iteratively select the most beneficial node for a solution. The researchers tested this method on synthetic networks generated from standard random graph models as well as real-world benchmark datasets from physics, social diffusion, and transportation. They benchmarked the approach against specialized traditional heuristics, sequential deep learning models, and commercial mathematical programming solvers across several problem classes, including the Minimum Vertex Cover, Maximum Cut, and Traveling Salesperson problems.

The findings show that the proposed approach reliably generates near-optimal solutions, achieving solution quality within a fraction of a percent of optimal on vertex cover benchmarks and outperforming established heuristic baselines on realistic datasets. In addition, the learned models demonstrated strong generalization, maintaining high solution quality on networks up to 1,200 nodes even when trained only on small graphs of 50 to 100 nodes. Computationally, the framework proved highly scalable, constructing solutions for 1,200-node instances in approximately 11 seconds on a single graphics processor and discovering sophisticated strategies, such as preserving network connectivity during selection.

These results demonstrate that organizations with recurring, time-sensitive optimization needs can invest in upfront model training to achieve faster, higher-quality automated decisions during real-time operations. Technical leaders should evaluate this framework for recurring logistics, routing, and network management workflows where conventional solvers cause latency bottlenecks. However, stakeholders should note limitations: the models require graphics hardware for fast execution, dense networks may necessitate edge sampling to manage computation, and reward mechanisms must be carefully tailored for new problem types. Conducting pilot comparisons on representative internal datasets is recommended prior to production deployment.

Ant Group Georgia Institute of Technology approximation algorithms combinatorial optimization graph embeddings combinatorial optimization algorithms graph optimization greedy heuristics

arXiv: 1704.01665 Hanjun-Dai/graph_comb_opt

Paper: Neural Combinatorial Optimization with Reinforcement Learning, Irwan Bello et al. (2016). This paper establishes the foundational paradigm of using reinforcement learning to solve combinatorial optimization problems without supervised optimal labels, which the source directly builds upon by incorporating graph representations.
Paper: Pointer networks, Oriol Vinyals et al. (2015). This work introduces neural architectures for sequence-based combinatorial optimization over variable-sized inputs, providing the core neural baseline and motivation for the source's graph-based greedy policy.
Paper: The Graph Neural Network Model, Franco Scarselli et al. (2009). This seminal paper defines the Graph Neural Network architecture and recursive state-update mechanism that underpins the graph embedding networks utilized in the source.
Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). This work formulates localized, scalable convolutional message-passing operations on graphs that inform the graph representation learning components used to encode optimization states.
Paper: Geometric Deep Learning: Going beyond Euclidean data, Michael M. Bronstein et al. (2016). This foundational survey details the spatial and spectral principles of deep learning on non-Euclidean graph domains essential for understanding the graph embedding networks in the source.
Paper: Learning to learn by gradient descent by gradient descent, Marcin Andrychowicz et al. (2016). This paper introduces the 'learning to learn' meta-algorithmic optimization framework that inspires the source's learned greedy constructive heuristic.
Paper: Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping, Andrew Y. Ng et al. (1999). This work provides the theoretical foundation for potential-based reward shaping, ensuring policy invariance when constructing step-by-step reinforcement learning rewards for incremental graph heuristics.

Paper: Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon, Yoshua Bengio et al. (2018). This comprehensive methodological survey categorizes and contextualizes reinforcement learning and graph embedding approaches for combinatorial optimization, directly reviewing the paradigm established by the source.
Paper: Relational inductive biases, deep learning, and graph networks, Peter W. Battaglia et al. (2018). This paper unifies relational inductive biases and graph networks for combinatorial generalization, providing a generalized structural framework that builds on graph-based decision making.
Paper: Link Prediction Based on Graph Neural Networks, Muhan Zhang et al. (2018). This work demonstrates how graph neural networks learn heuristic link predictions from local subgraphs, extending graph representation learning to discrete relational structure tasks.
Paper: Simple and Deep Graph Convolutional Networks, Ming Chen et al. (2020). This work develops deep graph convolutional architectures that overcome over-smoothing, enabling deeper structural feature propagation on complex graphs.
Paper: Graph Contrastive Learning with Augmentations, Yuning You et al. (2020). This work extends graph representation learning through self-supervised contrastive learning, enhancing graph neural network pre-training without task-specific optimization labels.

Cover for Learning Combinatorial Optimization Algorithms over Graphs

Abstract

The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. In this paper, we propose a unique combination of reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution. We show that our framework can be applied to a diverse range of optimization problems over graphs, and learns effective algorithms for the Minimum Vertex Cover, Maximum Cut and Traveling Salesman problems.

Topics

approximation algorithms combinatorial optimization graph embeddings optimization problems reinforcement learning combinatorial problems bipartite graphs adaptive algorithms

Keywords

combinatorial optimization algorithms graph optimization greedy heuristics Vertex Cover approximation algorithms random graphs

1 Introduction
2 Common Formulation for Greedy Algorithms on Graphs
3 Representation: Graph Embedding
3.1 Structure2Vec
3.2 Parameterizing Q^(h(S),v,Θ)\widehat{Q}(h({S}),v;\Theta)
4 Training: Q-learning
4.1 Reinforcement learning formulation
4.2 Learning algorithm
5 Experimental Evaluation
5.1 Comparison of solution quality
5.2 Generalization to larger instances
5.3 Scalability & Trade-off between running time and approximation ratio
5.4 Experiments on real-world datasets
5.5 Discovery of interesting new algorithms
6 Conclusions
References
A Related Work
B Set Covering Problem
C Experimental Results on Realistic Data
C.1 Minimum Vertex Cover
C.2 Maximum Cut
C.3 Traveling Salesman Problem
C.4 Set Covering Problem
D Experiment Details
D.1 Problem instance generation
D.1.1 Minimum Vertex Cover
D.1.2 Maximum Cut
D.1.3 Traveling Salesman Problem
D.1.4 Set Covering Problem
D.2 Full results on solution quality
D.3 Full results on generalization
D.4 Experiment Configuration of S2V-DQN
D.5 Stabilizing the training of S2V-DQN
D.6 Convergence of S2V-DQN
D.7 Complete time v/s approximation ratio plots
D.8 Additional analysis of the trade-off between time and approx. ratio
D.9 Visualization of solutions
D.10 Detailed visualization of learned MVC strategy
D.11 Experiment Configuration of PN-AC

Knowls

Knowl 1 — Greedy Combinatorial Optimization Meta-Algorithm Formulation over Graphs
model/method
The construction of solutions for combinatorial optimization problems over weighted graphs $G(V, E, w)$ with positive edge weights $w: E \to \mathbb{R}^+$ is formulated as a greedy node selection meta-algorithm:
1. Instance Sampling: An instance graph $G(V, E, w)$ is drawn from a problem instance distribution $\mathcal{D}$ .
2. Partial Solution State: An ordered list $S = (v_1, v_2, \dots, v_{|S|})$ , where $v_i \in V$ , represents the sequence of selected vertices. The set $\bar{S} = V \setminus S$ denotes the unselected candidate vertices. Each vertex $v \in V$ has an indicator variable $x_v \in \{0, 1\}$ , where $x_v = 1$ if $v \in S$ and $x_v = 0$ otherwise.
3. Helper / Maintenance Function: A problem-specific procedure $h(S)$ maps the sequence $S$ into a combinatorial structure that satisfies problem-specific constraints.
4. Objective / Cost Function: The quality of a partial solution $S$ is evaluated as $c(h(S), G)$ on the structure $h(S)$ .
5. Greedy Extension: Given an evaluation function $\hat{Q}(h(S), v; \Theta) \in \mathbb{R}$ , the algorithm iteratively selects vertex $v^* \in \bar{S}$ satisfying: $v^* = \arg\max_{v \in \bar{S}} \hat{Q}(h(S), v; \Theta)$ and appends it to the sequence $S \leftarrow (S, v^*)$ , updating $x_{v^*} = 1$ . This selection is repeated until a problem-specific termination criterion $t(h(S))$ is satisfied.
Knowl 2 — Reinforcement Learning MDP Formulation for Graph Combinatorial Optimization
model/method
The sequential greedy construction of solutions on a graph $G(V, E, w)$ is formalized as a Markov Decision Process (MDP):
- States: The state at step $t$ , $S_t$ , is the ordered sequence of selected vertices. It is represented by a pooled graph embedding vector $\sum_{v \in V} \mu_v \in \mathbb{R}^p$ , making the state representation invariant to graph size.
- Actions: An action is the selection of a vertex $v \in \bar{S}_t = V \setminus S_t$ , represented by its node embedding $\mu_v \in \mathbb{R}^p$ .
- Transitions: State transitions are deterministic; selecting vertex $v$ produces state $S_{t+1} = (S_t, v)$ and sets the node feature $x_v = 1$ .
- Rewards: The immediate reward $r(S, v)$ upon choosing vertex $v$ from state $S$ to form $S' = (S, v)$ is defined as the change in objective value: $r(S, v) = c(h(S'), G) - c(h(S), G)$ with $c(h(\emptyset), G) = 0$ . Consequently, the cumulative reward of a terminal state $\hat{S}$ is equal to the total solution objective: $R(\hat{S}) = \sum_{i=1}^{|\hat{S}|} r(S_i, v_i) = c(h(\hat{S}), G)$
- Policy: A deterministic greedy policy $\pi(v|S) = \arg\max_{v' \in \bar{S}} \hat{Q}(h(S), v'; \Theta)$ selects actions by maximizing the parameterization of the optimal action-value function $Q^*$ .
Knowl 3 — Problem Instantiations: Minimum Vertex Cover, Maximum Cut, Traveling Salesman, and Set Covering
definition
The greedy reinforcement learning framework is instantiated for four combinatorial optimization problems on graphs $G(V, E, w)$ (or bipartite graphs $G(U \cup C, E)$ for Set Covering):
1. Minimum Vertex Cover (MVC):
  - Objective: Find a minimum cardinality subset $S \subseteq V$ covering all edges in $E$ .
  - Helper Procedure $h(S)$ : Identity (no transformation required).
  - Cost $c(h(S), G)$ : $-|S|$ .
  - Reward $r(S, v)$ : $-1$ .
  - Termination $t(h(S))$ : All edges $e \in E$ have at least one incident node in $S$ .
2. Maximum Cut (MAXCUT):
  - Objective: Find a subset $S \subseteq V$ maximizing the cut-set weight $\sum_{(u, v) \in C} w(u, v)$ where $C = \{(u, v) \in E \mid u \in S, v \in V \setminus S\}$ .
  - Helper Procedure $h(S)$ : Partitions $V$ into $S$ and $\bar{S} = V \setminus S$ , maintaining cut-set $C$ .
  - Cost $c(h(S), G)$ : $\sum_{(u, v) \in C} w(u, v)$ .
  - Reward $r(S, v)$ : Difference in cut-set weight resulting from adding $v$ to $S$ .
  - Termination $t(h(S))$ : Cut-set weight cannot be increased by adding any unselected node.
3. Traveling Salesman Problem (TSP):
  - Objective: Find a Hamiltonian cycle of minimum length on a complete Euclidean graph.
  - Helper Procedure $h(S)$ : Maintains a tour by inserting candidate node $v$ into the position in $S$ that yields the minimal increase in tour length.
  - Cost $c(h(S), G)$ : $-\left(\sum_{i=1}^{|S|-1} w(S(i), S(i+1)) + w(S(|S|), S(1))\right)$ .
  - Reward $r(S, v)$ : Change in negative tour cost from inserting $v$ .
  - Termination $t(h(S))$ : All vertices are visited ( $S = V$ ).
4. Set Covering Problem (SCP):
  - Objective: Given bipartite graph $G(U \cup C, E)$ where edge $(u, s)$ indicates element $u \in U$ is covered by subset $s \in C$ , find a minimum size subset $S \subseteq C$ covering all $U$ .
  - Helper Procedure $h(S)$ : Identity.
  - Cost $c(h(S), G)$ : $-|S|$ .
  - Reward $r(S, v)$ : $-1$ .
  - Termination $t(h(S))$ : All elements in $U$ are covered.
Knowl 4 — Structure2Vec Graph Embedding Architecture for Action-Value Parameterization
model/method
The evaluation function $\hat{Q}(h(S), v; \Theta)$ is parameterized using the Structure2Vec deep graph embedding network.

1. Synchronous Node Embedding Updates: Each node $v \in V$ initializes its $p$ -dimensional embedding as $\mu_v^{(0)} = \mathbf{0} \in \mathbb{R}^p$ . Over $T$ iterations ( $t = 0, \dots, T-1$ ), embeddings update synchronously according to graph connectivity: $\mu_v^{(t+1)} \leftarrow \text{relu}\left(\theta_1 x_v + \theta_2 \sum_{u \in \mathcal{N}(v)} \mu_u^{(t)} + \theta_3 \sum_{u \in \mathcal{N}(v)} \text{relu}(\theta_4 w(v, u))\right)$ where:
- $\mathcal{N}(v)$ is the neighborhood of vertex $v$ in $G$ ;
- $x_v$ is the node feature/tag vector (such as the binary indicator $x_v \in \{0, 1\}$ indicating inclusion in $S$ );
- $w(v, u)$ is the edge weight between $v$ and $u$ ;
- $\text{relu}(z) = \max(0, z)$ is applied elementwise;
- $\theta_1, \theta_4 \in \mathbb{R}^p$ and $\theta_2, \theta_3 \in \mathbb{R}^{p \times p}$ are learnable weight matrices/vectors.
2. Evaluation Function Computation: After $T$ iterations, the state-action value $\hat{Q}(h(S), v; \Theta)$ is computed from the pooled graph representation $\sum_{u \in V} \mu_u^{(T)}$ and the candidate node embedding $\mu_v^{(T)}$ : $\hat{Q}(h(S), v; \Theta) = \theta_5^\top \text{relu}\left(\left[\theta_6 \sum_{u \in V} \mu_u^{(T)}, \, \theta_7 \mu_v^{(T)}\right]\right)$ where $[\cdot, \cdot]$ denotes vector concatenation, $\theta_5 \in \mathbb{R}^{2p}$ , and $\theta_6, \theta_7 \in \mathbb{R}^{p \times p}$ . The complete parameter set is $\Theta = \{\theta_1, \theta_2, \theta_3, \theta_4, \theta_5, \theta_6, \theta_7\}$ .
Knowl 5 — Fitted n-Step Q-Learning for Graph Greedy Policy (S2V-DQN)
algorithm
The parameters $\Theta$ of the Structure2Vec evaluation function $\hat{Q}(h(S), v; \Theta)$ are trained end-to-end via an $n$ -step Q-learning algorithm combined with experience replay:
Input: Distribution $\mathcal{D}$ , replay buffer capacity $N$ , mini-batch size $B$ , episode count $L$ , step horizon $T_{max}$ , lookahead horizon $n$ , discount factor $\gamma$ , exploration schedule $\epsilon$ .
Output: Optimized model parameters $\Theta$ .
Initialize experience replay memory $\mathcal{M}$ to capacity $N$
Initialize network parameters $\Theta$
for episode $e = 1$ to $L$ do
    Sample graph $G \sim \mathcal{D}$
    Initialize state sequence $S_1 = ()$
    for step $t = 1$ to $T_{max}$ (until termination) do
        With probability $\epsilon$ , select random node $v_t \in \bar{S}_t$
        Otherwise, select $v_t = \arg\max_{v \in \bar{S}_t} \hat{Q}(h(S_t), v; \Theta)$
        Execute action $v_t$ , observe reward $r_t = r(S_t, v_t)$ , and form $S_{t+1} = (S_t, v_t)$
        if $t \ge n$ then
             $R_{t-n, t} = \sum_{i=0}^{n-1} r_{t-n+i}$
            Add tuple $(S_{t-n}, v_{t-n}, R_{t-n, t}, S_t)$ to replay memory $\mathcal{M}$
            Sample random batch $\mathcal{B} \sim \mathcal{M}$ of size $B$
            For each tuple $(S, v, R, S') \in \mathcal{B}$ :
                Compute target $y = R + \gamma \max_{v' \in \bar{S}'} \hat{Q}(h(S'), v'; \Theta)$ if $S'$ non-terminal, else $y = R$
            Update $\Theta$ via stochastic gradient descent minimizing $\frac{1}{B} \sum_{\mathcal{B}} (y - \hat{Q}(h(S), v; \Theta))^2$
        end if
    end for
end for
return $\Theta$
Knowl 6 — Computational Time Complexity of S2V-DQN Solution Construction
theoretical result
Given a test graph $G(V, E)$ with $|V|$ vertices and $|E|$ edges, constructing a solution using the trained S2V-DQN greedy policy requires: $\mathcal{O}(k |E|)$ time, where $k \le |V|$ is the total number of greedy steps until termination. In each step, the Structure2Vec embedding performs $T$ message-passing iterations over graph edges (where $T \in \{3, 4, 5\}$ is a fixed constant), incurring $\mathcal{O}(T |E|) = \mathcal{O}(|E|)$ operations per node addition.

Knowl 7 — Generalization Across Graph Sizes with Small-Graph Training

empirical result

Because Structure2Vec utilizes neighborhood aggregations that do not depend on fixed graph dimensions, models trained on small graphs (50–100 nodes) generalize directly to test graphs of up to 1000–1200 nodes without retraining. The average approximation ratio is defined as $R(S, G) = \max\left(\frac{OPT(G)}{c(h(S))}, \frac{c(h(S))}{OPT(G)}\right)$ , where $OPT(G)$ is the best solution found by CPLEX or Concorde within a 1-hour cutoff:

Test Size	50–100	100–200	200–300	300–400	400–500	500–600	1000–1200
MVC (BA)	1.0033	1.0041	1.0045	1.0040	1.0045	1.0048	1.0062
MAXCUT (BA)	1.0150	1.0181	1.0202	1.0188	1.0123	1.0177	1.0038
TSP (clustered)	1.0730	1.0895	1.0869	1.0918	1.0944	1.0975	1.1065

For MVC on Barabási-Albert (BA) graphs, the approximation ratio degrades only from 1.0033 on 50–100 node graphs to 1.0062 on 1000–1200 node graphs.

Knowl 8 — Empirical Performance on Realistic and Real-World Benchmark Datasets

data/table

S2V-DQN was evaluated on real-world datasets and established benchmarks against standard approximation algorithms and heuristics:

MVC & SCP (MemeTracker): A news/blog phrase diffusion network with 960 nodes and 5000 edges.
MAXCUT (Physics): 10 Ising spin glass problem instances from the Optsicom library, each having 125 nodes, 375 edges, and weights $\in \{-1, 0, 1\}$ .
TSP (TSPLIB): 38 benchmark instances ranging from 51 to 318 nodes evaluated in active search mode.

Problem	Dataset	S2V-DQN	Best Competitor	2nd Best Competitor
MVC	MemeTracker	1.0021	1.2220 (MVCApprox-Greedy)	1.4080 (MVCApprox)
MAXCUT	Physics (Ising)	1.0223	1.2825 (MaxcutApprox)	1.8996 (SDP)
TSP	TSPLIB	1.0475	1.0800 (Farthest)	1.0947 (2-opt)
SCP	MemeTracker	1.0010	1.0009 (LP)	1.0300 (Greedy)

On the full MemeTracker network for MVC, an optimal cover has 473 nodes; S2V-DQN achieves 474 nodes (ratio 1.002), compared to 578 nodes (ratio 1.222) for MVCApprox-Greedy and 666 nodes (ratio 1.408) for MVCApprox.

Knowl 9 — Experimental Setup and Training Hyperparameters for S2V-DQN

experimental setup

The hyperparameters and model configurations for S2V-DQN across the target optimization tasks are:

Problem	Node Tag / Features	Edge Feature	Embedding Dim $p$	Iterations $T$	Batch Size	$n$ -step
MVC	Binary $x_v \in \{0, 1\}$	None	64	5	128	5
MAXCUT	Binary $x_v \in \{0, 1\}$	Edge weight, end node tag	64	3	64	1
TSP	Coords $(x, y)$ , tag, start/end	Length, end node tag	64	4	64	1
SCP	Binary $x_v \in \{0, 1\}$	None	64	5	64	2

Graph Distributions: Erdős-Rényi (ER) graphs with edge probability $0.15$ ; Barabási-Albert (BA) graphs with average degree 4; TSP instances generated on $[10^6, 10^6]$ 2D grids (uniform random or clustered into $n/100$ clusters) with 10-nearest neighbor graph pruning ( $K = 10$ ).
Optimization: Adam optimizer with initial learning rate $10^{-3}$ decayed exponentially by factor $0.95$ . Exploration parameter $\epsilon$ is linearly annealed from $1.0$ to $0.05$ .
Discount Factor: $\gamma = 1.0$ for MVC, MAXCUT, and SCP; $\gamma = 0.1$ for TSP.

Knowl 10 — Structural Policy Discovery in Learned S2V-DQN Greedy Heuristics
empirical result
Inspection of the node selection trajectories discovered by S2V-DQN reveals interpretable, non-myopic structural heuristics:
- Minimum Vertex Cover: Rather than purely maximizing immediate edge coverage by selecting the maximum-degree node, S2V-DQN learns to trade off instantaneous degree with the preservation of graph connectivity, avoiding fracturing the residual graph into disconnected components early in the process.
- Maximum Cut: S2V-DQN avoids picking nodes that provide large immediate cut additions if those choices would cancel out existing cut-edges in future iterations.

Coverage note — None was omitted; all main contributions, including the meta-algorithm formulation, RL framework, Structure2Vec Q-parameterization, training algorithm, theoretical complexity, benchmark evaluations, generalization tables, and policy discovery observations are fully covered.

References

1.Albert, Reka and Barabasi, Albert-Laszlo. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
2.Andrychowicz, Marcin, Denil, Misha, Gomez, Sergio, Hoffman, Matthew W, Pfau, David, Schaul, Tom, and de Freitas, Nando. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, pp. 3981–3989, 2016.
3.Applegate, David, Bixby, Robert, Chvatal, Vasek, and Cook, William. Concorde TSP solver, 2006.
4.Applegate, David L, Bixby, Robert E, Chvatal, Vasek, and Cook, William J. The traveling salesman problem: a computational study. Princeton university press, 2011.
5.Balas, Egon and Ho, Andrew. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. Combinatorial Optimization, pp. 37–60, 1980.
6.Bello, Irwan, Pham, Hieu, Le, Quoc V, Norouzi, Mohammad, and Bengio, Samy. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016.
7.Boyan, Justin and Moore, Andrew W. Learning evaluation functions to improve optimization by local search. Journal of Machine Learning Research, 1(Nov):77–112, 2000.
8.Chen, Yutian, Hoffman, Matthew W, Colmenarejo, Sergio Gomez, Denil, Misha, Lillicrap, Timothy P, and de Freitas, Nando. Learning to learn for global optimization of black box functions. arXiv preprint arXiv:1611.03824, 2016.
9.Dai, Hanjun, Dai, Bo, and Song, Le. Discriminative embeddings of latent variable models for structured data. In ICML, 2016.
10.Du, Nan, Song, Le, Gomez-Rodriguez, Manuel, and Zha, Hongyuan. Scalable influence estimation in continuous-time diffusion networks. In NIPS, 2013.
11.Erdos, Paul and Renyi, A. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17–61, 1960.
12.Goemans, M.X. and Williamson, D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6): 1115–1145, 1995.
13.Gomez-Rodriguez, Manuel, Leskovec, Jure, and Krause, Andreas. Inferring networks of diffusion and influence. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1019–1028. ACM, 2010.
14.Graves, Alex, Wayne, Greg, Reynolds, Malcolm, Harley, Tim, Danihelka, Ivo, Grabska-Barwinska, Agnieszka, Colmenarejo, Sergio Gomez, Grefenstette, Edward, Ramalho, Tiago, Agapiou, John, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471–476, 2016.
15.Gu, Shixiang, Lillicrap, Timothy, Ghahramani, Zoubin, Turner, Richard E, and Levine, Sergey. Q-prop: Sample-efficient policy gradient with an off-policy critic. arXiv preprint arXiv:1611.02247, 2016.
16.He, He, Daume III, Hal, and Eisner, Jason M. Learning to search in branch and bound algorithms. In Advances in Neural Information Processing Systems, pp. 3293–3301, 2014.
17.IBM. CPLEX User’s Manual, Version 12.6.1, 2014.
18.Johnson, David S and McGeoch, Lyle A. Experimental analysis of heuristics for the stsp. In The traveling salesman problem and its variations, pp. 369–443. Springer, 2007.
19.Karp, Richard M. Reducibility among combinatorial problems. In Complexity of computer computations, pp. 85–103. Springer, 1972.
20.Kempe, David, Kleinberg, Jon, and Tardos, Eva. Maximizing the spread of influence through a social network. In KDD, pp. 137–146. ACM, 2003.
21.Khalil, Elias B., Dilkina, B., and Song, L. Scalable diffusion-aware optimization of network topology. In Knowledge Discovery and Data Mining (KDD), 2014.
22.Khalil, Elias B., Le Bodic, Pierre, Song, Le, Nemhauser, George L, and Dilkina, Bistra N. Learning to branch in mixed integer programming. In AAAI, pp. 724–731, 2016.
23.Khalil, Elias B., Dilkina, Bistra, Nemhauser, George, Ahmed, Shabbir, and Shao, Yufen. Learning to run heuristics in tree search. In 26th International Joint Conference on Artificial Intelligence (IJCAI), 2017.
24.Kingma, Diederik and Ba, Jimmy. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
25.Kleinberg, Jon and Tardos, Eva. Algorithm design. Pearson Education India, 2006.
26.Lagoudakis, Michail G and Littman, Michael L. Learning to select branching rules in the dpll procedure for satisfiability. Electronic Notes in Discrete Mathematics, 9:344–359, 2001.
27.Li, Ke and Malik, Jitendra. Learning to optimize. arXiv preprint arXiv:1606.01885, 2016.
28.Mnih, Volodymyr, Kavukcuoglu, Koray, Silver, David, Graves, Alex, Antonoglou, Ioannis, Wierstra, Daan, and Riedmiller, Martin A. Playing atari with deep reinforcement learning. CoRR, abs/1312.5602, 2013. URL http://arxiv.org/abs/1312.5602.
29.Mnih, Volodymyr, Kavukcuoglu, Koray, Silver, David, Rusu, Andrei A, Veness, Joel, Bellemare, Marc G, Graves, Alex, Riedmiller, Martin, Fidjeland, Andreas K, Ostrovski, Georg, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 2015.
30.Papadimitriou, C. H. and Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, New Jersey, 1982.
31.Peleg, David, Schechtman, Gideon, and Wool, Avishai. Approximating bounded 0-1 integer linear programs. In Theory and Computing Systems, 1993., Proceedings of the 2nd Israel Symposium on the, pp. 69–77. IEEE, 1993.
32.Reinelt, Gerhard. Tsplib—a traveling salesman problem library. ORSA journal on computing, 3 (4):376–384, 1991.
33.Riedmiller, Martin. Neural fitted q iteration–first experiences with a data efficient neural reinforcement learning method. In European Conference on Machine Learning, pp. 317–328. Springer, 2005.
34.Sabharwal, Ashish, Samulowitz, Horst, and Reddy, Chandra. Guiding combinatorial optimization with uct. In CPAIOR, pp. 356–361. Springer, 2012.
35.Samulowitz, Horst and Memisevic, Roland. Learning to solve QBF. In AAAI, 2007.
36.Sutton, R.S. and Barto, A.G. Reinforcement Learning: An Introduction. MIT Press, 1998.
37.Vinyals, Oriol, Fortunato, Meire, and Jaitly, Navdeep. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692–2700, 2015.
38.Zhang, Wei and Dietterich, Thomas G. Solving combinatorial optimization tasks by reinforcement learning: A general methodology applied to resource-constrained scheduling. Journal of Artificial Intelligence Reseach, 1:1–38, 2000.

Citation

MLA

Dai, H., et al. “Learning Combinatorial Optimization Algorithms over Graphs”. arXiv, 2017, http://arxiv.org/abs/1704.01665v4.

APA

Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., & Song, L. (2017). Learning Combinatorial Optimization Algorithms over Graphs. arXiv. http://arxiv.org/abs/1704.01665v4

Chicago

Dai, H., E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song. 2017. “Learning Combinatorial Optimization Algorithms over Graphs”. arXiv. http://arxiv.org/abs/1704.01665v4.

Harvard

Dai, H. et al. (2017) “Learning Combinatorial Optimization Algorithms over Graphs”, arXiv [Preprint]. Available at: http://arxiv.org/abs/1704.01665v4.

Vancouver

1. Dai H, Khalil EB, Zhang Y, Dilkina B, Song L (2017) Learning Combinatorial Optimization Algorithms over Graphs. arXiv

BibTeX

@article{dai2017learning,
  title = {Learning Combinatorial Optimization Algorithms over Graphs},
  author = {Dai, Hanjun and Khalil, Elias B. and Zhang, Yuyu and Dilkina, Bistra and Song, Le},
  year = {2017},
  journal = {arXiv},
  url = {http://arxiv.org/abs/1704.01665v4},
  eprint = {1704.01665}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Learning Combinatorial Optimization Algorithms over Graphs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Greedy Combinatorial Optimization Meta-Algorithm Formulation over Graphs

Knowl 2 — Reinforcement Learning MDP Formulation for Graph Combinatorial Optimization

Knowl 3 — Problem Instantiations: Minimum Vertex Cover, Maximum Cut, Traveling Salesman, and Set Covering

Knowl 4 — Structure2Vec Graph Embedding Architecture for Action-Value Parameterization

Knowl 5 — Fitted n-Step Q-Learning for Graph Greedy Policy (S2V-DQN)

Knowl 6 — Computational Time Complexity of S2V-DQN Solution Construction