# Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation

arXiv: https://arxiv.org/abs/2207.05984 · HTML: https://mlsanity.com/paper/2207.05984/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 82 references that are in the map.
- First posted on arXiv 13 Jul 2022.

## Builds on (most cited first, 30 of 46)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Conditioning by adaptive sampling for robust design](https://mlsanity.com/paper/1901.10060/) (2019)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Conservative Objective Models for Effective Offline Model-Based Optimization](https://mlsanity.com/paper/2107.06882/) (2021)
- [Learning Collaborative Policies to Solve NP-hard Routing Problems](https://mlsanity.com/paper/2110.13987/) (2021)

## Built on by (most cited first, 30 of 32)

- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets](https://mlsanity.com/paper/2305.17010/) (2023)
- [Diffusion Models as Constrained Samplers for Optimization with Unknown Constraints](https://mlsanity.com/paper/2402.18012/) (2024)
- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning](https://mlsanity.com/paper/2301.03116/) (2023)
- [Controlling Continuous Relaxation for Combinatorial Optimization](https://mlsanity.com/paper/2309.16965/) (2023)
- [On Learning Latent Models with Multi-Instance Weak Supervision](https://mlsanity.com/paper/2306.13796/) (2023)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Cross-Modality Program Representation Learning for Electronic Design Automation with High-Level Synthesis](https://mlsanity.com/paper/2406.09606/) (2024)
- [Regularized Langevin Dynamics for Combinatorial Optimization](https://mlsanity.com/paper/2502.00277/) (2025)
- [Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More](https://mlsanity.com/paper/2405.08424/) (2024)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [Reheated Gradient-based Discrete Sampling for Combinatorial Optimization](https://mlsanity.com/paper/2503.04047/) (2025)
- [Maximum Independent Set: Self-Training through Dynamic Programming](https://mlsanity.com/paper/2310.18672/) (2023)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Accelerating Diffusion-based Combinatorial Optimization Solvers by Progressive Distillation](https://mlsanity.com/paper/2308.06644/) (2023)
- [Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update](https://mlsanity.com/paper/2407.16468/) (2024)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems](https://mlsanity.com/paper/2402.02190/) (2024)
- [Efficient Combinatorial Optimization via Heat Diffusion](https://mlsanity.com/paper/2403.08757/) (2024)
- [Compact Optimality Verification for Optimization Proxies](https://mlsanity.com/paper/2405.21023/) (2024)
- [A Benchmark on Directed Graph Representation Learning in Hardware Designs](https://mlsanity.com/paper/2410.06460/) (2024)
- [ProgSG: Cross-Modality Representation Learning for Programs in Electronic Design Automation](https://mlsanity.com/paper/2305.10838/) (2023)
- [Deep Inverse Design for High-Level Synthesis](https://mlsanity.com/paper/2407.08797/) (2024)
- [An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem](https://mlsanity.com/paper/2408.08484/) (2024)
- [Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs](https://mlsanity.com/paper/2505.13754/) (2025)
- [On Training-Test (Mis)alignment in Unsupervised Combinatorial Optimization: Observation, Empirical Exploration, and Analysis](https://mlsanity.com/paper/2506.16732/) (2025)
- [Binarizing Physics-Inspired GNNs for Combinatorial Optimization](https://mlsanity.com/paper/2507.13703/) (2025)
- [Test-Time Adaptation for Unsupervised Combinatorial Optimization](https://mlsanity.com/paper/2601.21048/) (2026)
- [UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2603.11456/) (2026)

## Abstract (arXiv)

Using machine learning to solve combinatorial optimization (CO) problems is challenging, especially when the data is unlabeled. This work proposes an unsupervised learning framework for CO problems. Our framework follows a standard relaxation-plus-rounding approach and adopts neural networks to parameterize the relaxed solutions so that simple back-propagation can train the model end-to-end. Our key contribution is the observation that if the relaxed objective satisfies entry-wise concavity, a low optimization loss guarantees the quality of the final integral solutions. This observation significantly broadens the applicability of the previous framework inspired by Erdos' probabilistic method. In particular, this observation can guide the design of objective models in applications where the objectives are not given explicitly while requiring being modeled in prior. We evaluate our framework by solving a synthetic graph optimization problem, and two real-world applications including resource allocation in circuit design and approximate computing. Our framework largely outperforms the baselines based on na"ive relaxation, reinforcement learning, and Gumbel-softmax tricks.