Geometric Algorithms for Neural Combinatorial Optimization with Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915730809683968 |
|---|---|
| author | Karalias, Nikolaos Rafiey, Akbar Xu, Yifei Luo, Zhishang Tahmasebi, Behrooz Jiang, Connie Jegelka, Stefanie |
| author_facet | Karalias, Nikolaos Rafiey, Akbar Xu, Yifei Luo, Zhishang Tahmasebi, Behrooz Jiang, Connie Jegelka, Stefanie |
| contents | Self-Supervised Learning (SSL) for Combinatorial Optimization (CO) is an emerging paradigm for solving combinatorial problems using neural networks. In this paper, we address a central challenge of SSL for CO: solving problems with discrete constraints. We design an end-to-end differentiable framework that enables us to solve discrete constrained optimization problems with neural networks. Concretely, we leverage algorithmic techniques from the literature on convex geometry and Carathéodory's theorem to decompose neural network outputs into convex combinations of polytope corners that correspond to feasible sets. This decomposition-based approach enables self-supervised training but also ensures efficient quality-preserving rounding of the neural net output into feasible solutions. Extensive experiments in cardinality-constrained optimization show that our approach can consistently outperform neural baselines. We further provide worked-out examples of how our method can be applied beyond cardinality-constrained problems to a diverse set of combinatorial optimization tasks, including finding independent sets in graphs, and solving matroid-constrained problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24039 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Geometric Algorithms for Neural Combinatorial Optimization with Constraints Karalias, Nikolaos Rafiey, Akbar Xu, Yifei Luo, Zhishang Tahmasebi, Behrooz Jiang, Connie Jegelka, Stefanie Machine Learning Artificial Intelligence Self-Supervised Learning (SSL) for Combinatorial Optimization (CO) is an emerging paradigm for solving combinatorial problems using neural networks. In this paper, we address a central challenge of SSL for CO: solving problems with discrete constraints. We design an end-to-end differentiable framework that enables us to solve discrete constrained optimization problems with neural networks. Concretely, we leverage algorithmic techniques from the literature on convex geometry and Carathéodory's theorem to decompose neural network outputs into convex combinations of polytope corners that correspond to feasible sets. This decomposition-based approach enables self-supervised training but also ensures efficient quality-preserving rounding of the neural net output into feasible solutions. Extensive experiments in cardinality-constrained optimization show that our approach can consistently outperform neural baselines. We further provide worked-out examples of how our method can be applied beyond cardinality-constrained problems to a diverse set of combinatorial optimization tasks, including finding independent sets in graphs, and solving matroid-constrained problems. |
| title | Geometric Algorithms for Neural Combinatorial Optimization with Constraints |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2510.24039 |