# Controlling Continuous Relaxation for Combinatorial Optimization

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 82 references that are in the map.
- First posted on arXiv 29 Sep 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [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)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [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)
- [Flow-based generative models for Markov chain Monte Carlo in lattice field theory](https://mlsanity.com/paper/1904.12072/) (2019)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Solving Statistical Mechanics Using Variational Autoregressive Networks](https://mlsanity.com/paper/1809.10606/) (2018)
- [Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective](https://mlsanity.com/paper/2003.00330/) (2020)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [Decision-Focused Learning: Through the Lens of Learning to Rank](https://mlsanity.com/paper/2112.03609/) (2021)
- [Contrastive Losses and Solution Caching for Predict-and-Optimize](https://mlsanity.com/paper/2011.05354/) (2020)
- [Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2206.13211/) (2022)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [It's Not What Machines Can Learn, It's What We Cannot Teach](https://mlsanity.com/paper/2002.09398/) (2020)

## Built on by (most cited first, 16 of 16)

- [Quantization Error Propagation: Revisiting Layer-Wise Post-Training Quantization](https://mlsanity.com/paper/2504.09629/) (2025)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (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)
- [More Than Bits: Multi-Envelope Double Binary Factorization for Extreme Quantization](https://mlsanity.com/paper/2512.24545/) (2025)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)
- [Neural Predictor-Corrector: Solving Homotopy Problems with Reinforcement Learning](https://mlsanity.com/paper/2602.03086/) (2026)
- [Learning for Dynamic Combinatorial Optimization without Training Data](https://mlsanity.com/paper/2505.19497/) (2025)
- [Neural QAOA2: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization](https://mlsanity.com/paper/2605.13072/) (2026)
- [Deep k-grouping: An Unsupervised Learning Framework for Combinatorial Optimization on Graphs and Hypergraphs](https://mlsanity.com/paper/2505.20972/) (2025)
- [BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks](https://mlsanity.com/paper/2505.20997/) (2025)
- [Binarizing Physics-Inspired GNNs for Combinatorial Optimization](https://mlsanity.com/paper/2507.13703/) (2025)
- [On the Dataless Training of Neural Networks](https://mlsanity.com/paper/2510.25962/) (2025)
- [Test-Time Adaptation for Unsupervised Combinatorial Optimization](https://mlsanity.com/paper/2601.21048/) (2026)
- [Signs Beat Floats: Low-Rank Double-Binary Adaptation for On-Device Fine-Tuning](https://mlsanity.com/paper/2605.24058/) (2026)
- [Mixed-Integer Nonlinear Differentiable Predictive Control for Underground Pumped Hydro Energy Storage Systems](https://mlsanity.com/paper/2609.17964/) (2026)

## Abstract (arXiv)

Unsupervised learning (UL)-based solvers for combinatorial optimization (CO) train a neural network that generates a soft solution by directly optimizing the CO objective using a continuous relaxation strategy. These solvers offer several advantages over traditional methods and other learning-based methods, particularly for large-scale CO problems. However, UL-based solvers face two practical issues: (I) an optimization issue, where UL-based solvers are easily trapped at local optima, and (II) a rounding issue, where UL-based solvers require artificial post-learning rounding from the continuous space back to the original discrete space, undermining the robustness of the results. This study proposes a Continuous Relaxation Annealing (CRA) strategy, an effective rounding-free learning method for UL-based solvers. CRA introduces a penalty term that dynamically shifts from prioritizing continuous solutions, effectively smoothing the non-convexity of the objective function, to enforcing discreteness, eliminating artificial rounding. Experimental results demonstrate that CRA significantly enhances the performance of UL-based solvers, outperforming existing UL-based solvers and greedy algorithms in complex CO problems. Additionally, CRA effectively eliminates artificial rounding and accelerates the learning process.