Research map / Learning theory and algorithms / Combinatorial and search optimization
Geometric Algorithms for Neural Combinatorial Optimization with Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a self-supervised neural CO framework that decomposes neural outputs in a polytope into convex combinations of feasible corners (GLS/Carathéodory-based), giving a differentiable extension loss and a quality-preserving rounding.
Problem
Self-supervised neural combinatorial optimization struggles to enforce discrete constraints in both training losses and inference rounding without tuning penalty terms or using heuristic rounding.
Approach
Map neural outputs to points in the convex hull of feasible solutions, decompose them via a GLS-style Carathéodory iterative algorithm into a distribution over feasible sets, and use the expected objective (a continuous extension) as a loss; the same decomposition rounds outputs with a guarantee that the best set is at least as good as the extension value.
Key results
- Learning-based short variant outperforms learning baselines in both runtime and objective on max coverage without test-time optimization.
- Medium and long variants with test-time optimization surpass most TTO-based baselines except on the Twitch dataset.
- Decomposition-based rounding guarantees the selected set is at least as good as the extension value F(x).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the short decomposition-based method without test-time optimization | Geometric method · Maximum Coverage, tested datasets | objective value | Helped |
| Use the short decomposition-based method without test-time optimization | Geometric method · Maximum Coverage, tested datasets | inference time | Helped |
| Add local improvement by swapping elements from sets in the decomposition support | Geometric method, medium variant · Random500, Random1000, and Railway | objective value | Helped |
| Add data augmentation to the medium variant | Geometric method, long variant · Random500, Random1000, and Railway | objective value | Helped |
| Use the geometric method instead of Greedy | Maximum Coverage · Random500, larger k | objective value | Helped |
| Use the geometric method instead of UCOM | Maximum Coverage · Random1000 and Railway | objective value | Helped |
| Use the geometric method rather than CardNN with test-time optimization | Maximum Coverage · Twitch | objective value | Hurt |
| Optimize the extension on the test set with Adam instead of decomposing a random point projected onto the polytope (ablation) | Decomposition-based method · Cardinality-constrained maximum cut, two datasets and two k settings | objective value | Helped |
| Use a neural network optimized on the test data instead of direct Adam optimization of a random point (ablation) | Decomposition-based method · Cardinality-constrained maximum cut, two datasets and two k settings | objective value | Helped |
| Train the neural network on a separate training set rather than on the test data (ablation) | Self-supervised geometric method · Cardinality-constrained maximum cut, two datasets and two k settings | objective value | No clear effect |
Surprising findings
- Learning-based methods, including this one, perform poorly on the Twitch dataset, attributed to encoder architecture and data distribution.
Limitations
- Performance on Twitch is poor for all learning methods, attributed to the encoder architecture.
- Efficiency depends on polytope structure; strong optimization oracle required.
- Model architecture was not explored in depth.
Experimental setup
Datasets: synthetic random bipartite graphs (uniform and Pareto distributions)
Benchmarks: Maximum Coverage on Random500 Random1000 Twitch Railway
Metrics: objective value inference time
Baselines: random greedy Gurobi CardNN EGN UCOM2 RL (actor-critic with GraphSage)
Builds on: GLS method (Grötschel-Lovász-Schrijver) CardNN UCOM Carathéodory theorem
Closest papers by meaning
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.89)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.88)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.88)
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.87)
- UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems (NeurIPS 2024 · similarity 0.87)
- Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.