1 of 9

Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time

Section II

Slides by: Giovanni Rivera

​

The paper can be found here: https://arxiv.org/pdf/2006.03750.pdf

2 of 9

2. Unified Framework

3 of 9

Defining the problem space

Suppose we have a weighted graph, G, defined as:

Where,

V = {v , v , …, v } represents vertices (nodes)� E = {ei,j | i, j ∈ V} represents edges� W = {wi,j | i, j ∈ V} represents the weights of� the edges

N(i) = {vj | ei,j ∈ E} represents the neighbors of� v (node i)

1

2

i

n

4 of 9

Defining the problem space (cont’d)

G’s edge-to-vertex dual (line graph) is defined as:

Where,

V* = {(i, j) | ei,j ∈ V} represents edges�E* = {vi | i ∈ V} represents nodes�W* = {wi,j | i, j ∈ V} represents the weights� of the nodes

5 of 9

Defining problems over graphs

  • Minimum Spanning Tree (MST)
    • Goal: Find the tree along all nodes with the minimum sum of weights
      • Boruvka’s [48], Prim’s [53 ] and Kruskal’s algorithm [37]
      • Time Complexity:�O(|E| log |V|)
  • Single-Source Shortest Path (SSP)
    • Goal: Find the shortest paths from the source node to all other nodes
      • Dijkstra’s algorithm [ 21]
        • Time Complexity O(|V| log |V| + |E|)
      • Bellman- Ford [7]
        • Time Complexity O(|V| |E|).
      • Floyd–Warshall algorithm [18]
        • Time Complexity O(|V|3)

6 of 9

Defining problems over graphs

  • Traveling Salesman Problem (TSP)
    • Goal: Find the shortest tour that visits all cities once and returns to the starting city.
    • Approximation Algorithms
      • LKH [42], Christofides [17], 2-opt [41, 1], Farthest Insertion and Nearest Neighbor [55]
    • Exact Algorithms
      • Concorde [5], Gurobi [50] (Integer Linear Programming, ILP)
  • Vehicle Routing Problem (VRP)
    • Goal: Find the optimal routes for each vehicle to visit a unique subset of cities
    • TSP is a special case of VRP with one vehicle

7 of 9

Graph Generation

  • Learning MST and SSP
    • Type:
      • Erdős-Rényi (ER) [24]
      • Barabási-Albert (BA) [3]
      • Stochastic block model (SBM) [28]
      • Watts-Strogatz (WS) [67]
      • Random regular (RR) [60 , 34]
    • Weights:
      • Uniformly distributed from [0, 1]
  • Learning TSP and VRP
    • Type:
      • Complete graphs
  • Nodes:
    • Uniformly distributed from [0,1]2
  • Weights:
    • Distance between nodes

8 of 9

Learning Graph Algorithms as Single Player Games

The paper uses a search tree to represent the reinforcement learning approach.

The root represents an initial (random) state.

The leaves represent the possible solutions based on each state-action pair, following a neural network.

Reaching a leaf represents obtaining a reward (or cost) from an action.

9 of 9

Learning Graph Algorithms (cont’d)

“When the predictions of our neural network capture the global structure of the problem, this mechanism is very efficient.

​

On the other hand, even if the network makes poor predictions for a particular problem, the search will still find the solution if run for a sufficiently long (possibly exponential) time.

​

The network is re-trained using the results of the evaluation oracle on the leaf nodes reached by the search to improve its predictions”