mlsanityData to 7 Oct 2026

A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs

arXiv 2106.04927 ↗First posted 9 Jun 2021cs.LG math.COcited by 26

Not on the map. Why?

Abstract (arXiv)

Combinatorial Optimization (CO) has been a long-standing challenging research topic featured by its NP-hard nature. Traditionally such problems are approximately solved with heuristic algorithms which are usually fast but may sacrifice the solution quality. Currently, machine learning for combinatorial optimization (MLCO) has become a trending research topic, but most existing MLCO methods treat CO as a single-level optimization by directly learning the end-to-end solutions, which are hard to scale up and mostly limited by the capacity of ML models given the high complexity of CO. In this paper, we propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph (e.g. add, delete or modify edges in a graph), fused with a lower-level heuristic algorithm solving on the optimized graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity. The experiments and results on several popular CO problems like Directed Acyclic Graph scheduling, Graph Edit Distance and Hamiltonian Cycle Problem show its effectiveness over manually designed heuristics and single-level learning methods.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 31 of its 80 references that are in the map. First posted on arXiv 9 Jun 2021.

Builds on

31 of 80 references.

References · 31

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2017Proximal Policy Optimization Algorithmscited by 14,441
  4. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  5. 2017Mask R-CNNcited by 7,259
  6. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  7. 2015Trust Region Policy Optimizationcited by 2,503
  8. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  9. 2015Pointer Networkscited by 882
  10. 2018Attention, Learn to Solve Routing Problems!cited by 646
  11. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  12. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
19 more
  1. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  2. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  3. 2019Graph Matching Networks for Learning the Similarity of Graph Structured Objectscited by 202
  4. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 183
  5. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  6. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
  7. 2021Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyondcited by 151
  8. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
  9. 2018Learning Scheduling Algorithms for Data Processing Clusterscited by 133
  10. 2016Discriminative Embeddings of Latent Variable Models for Structured Datacited by 130
  11. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  12. 2019Reinforcement Learning for Integer Programming: Learning to Cutcited by 108
  13. 2018SimGNN: A Neural Network Approach to Fast Graph Similarity Computationcited by 89
  14. 2019Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matchingcited by 83
  15. 2021Search to aggregate neighborhood for graph neural networkcited by 48
  16. 2020Combinatorial Learning of Graph Edit Distance via Dynamic Embeddingcited by 24
  17. 2020Graph Edit Distance Reward: Learning to Edit Scene Graphcited by 14
  18. 2020TAP-Net: Transport-and-Pack using Reinforcement Learningcited by 12
  19. 2020A Survey on Reinforcement Learning for Combinatorial Optimizationcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 6; 2023: 5; 2024: 7; 2025: 2; 2026: 4.

26 papers.

Sort:

By area:

  1. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  2. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  3. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  4. 2021Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustnesscited by 35
  5. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  6. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  7. 2024Cross-Problem Learning for Solving Vehicle Routing Problemscited by 24
  8. 2024LinSATNet: The Positive Linear Satisfiability Neural Networkscited by 16
  9. 2023iSLAM: Imperative SLAMcited by 14
  10. 2022Neural Topological Ordering for Computation Graphscited by 12
  11. 2022LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisationcited by 8
  12. 2023Automatic MILP Solver Configuration By Learning Problem Similaritiescited by 5
14 more
  1. 2025EFormer: An Effective Edge-based Transformer for Vehicle Routing Problemscited by 5
  2. 2024Improving the interpretability of GNN predictions through conformal-based graph sparsificationcited by 4
  3. 2024Learning Reward and Policy Jointly from Demonstration and Preference Improves Alignmentcited by 4
  4. 2024torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problemcited by 3
  5. 2024Adaptive Stabilization Based on Machine Learning for Column Generationcited by 3
  6. 2024Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networkscited by 2
  7. 2025Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problemscited by 2
  8. 2022Detecting Small Query Graphs in A Large Graph via Neural Subgraph Searchcited by 1
  9. 2023A hybrid deep-learning-metaheuristic framework for bi-level network design problemscited by 1
  10. 2026A Learning Method with Gap-Aware Generation for Heterogeneous DAG Schedulingcited by 1
  11. 2021A General Framework for Evaluating Robustness of Combinatorial Optimization Solvers on Graphscited by 0
  12. 2026Bi-level RL-Heuristic Optimization for Real-world Winter Road Maintenancecited by 0
  13. 2026Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimizationcited by 0
  14. 2026Neural Certificate Pricing for Combinatorial Optimization Problemscited by 0