analiza aiqbench
This research addresses a critical bottleneck in neural combinatorial optimization by enabling gradient-based training without projecting outputs onto feasible polytopes. The proposed framework utilizes Frank-Wolfe methods to decompose continuous predictions into sparse convex combinations of valid solutions, ensuring hard constraints are met automatically at inference time. Empirical results demonstrate robust performance across discrete problems like the Traveling Salesperson Problem and Quadratic Assignment Problem, offering a generalizable approach for solving constrained optimization tasks with neural networks.
Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe
arXiv:2609.25728v1 Announce Type: cross Abstract: Self-supervised learning for combinatorial optimization has emerged as a promising paradigm for solving discrete optimization problems with neural networks, but a central challenge remains: handling hard combinatorial constraints within continuous, gradient-based training. Continuously extending combinatorial objectives to convex domains is a powerful technique, yet existing approaches often require projection steps that constrain neural network outputs to lie inside the feasible polytope and rely on ad-hoc and problem-specific constructions. We propose a general framework in which the neural network is allowed to predict arbitrary continuous vectors that could potentially lie outside of the feasible polytope. These predictions are then approximated by sparse convex combinations of feasible solutions using a geometric decomposition algorithm based on Frank--Wolfe methods and approximate Caratheodory results. This decomposition induces an a.e.-differentiable, self-supervised loss defined as the expected value of the discrete objective. The same procedure provides an automatic rounding guarantee at inference time. We demonstrate strong empirical performance across multiple combinatorial problems, including the Quadratic Assignment Problem, Maximum Coverage, and the Traveling Salesperson Problem.
Abstract:Self-supervised learning for combinatorial optimization has emerged as a promising paradigm for solving discrete optimization problems with neural networks, but a central challenge remains: handling hard combinatorial constraints within continuous, gradient-based training. Continuously extending combinatorial objectives to convex domains is a powerful technique, yet existing approaches often require projection steps that constrain neural network outputs to lie inside the feasible polytope and rely on ad-hoc and problem-specific constructions. We propose a general framework in which the neural network is allowed to predict arbitrary continuous vectors that could potentially lie outside of the feasible polytope. These predictions are then approximated by sparse convex combinations of feasible solutions using a geometric decomposition algorithm based on Frank--Wolfe methods and approximate Caratheodory results. This decomposition induces an a.e.-differentiable, self-supervised loss defined as the expected value of the discrete objective. The same procedure provides an automatic rounding guarantee at inference time. We demonstrate strong empirical performance across multiple combinatorial problems, including the Quadratic Assignment Problem, Maximum Coverage, and the Traveling Salesperson Problem.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2609.25728 [cs.LG]
(or arXiv:2609.25728v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.25728 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 264 cuvinte
Subiecte conexe
[AINews] Reality Checks on AI News (Yegge shuts down Gas Town, Databricks’ +60% Astra cost)
Latent Space · 17 sept. 2026
Compute Time Scaling with Recursive Models for Combinatorial Optimization
arXiv · 30 sept. 2026
A brief history of quantum vs classical computational advantage
Quantum Journal · 1 sept. 2026
Amazon is investing in the Lean Focused Research Organization
Amazon Science · 26 iul. 2026