Metraipolis › archive › dc_3cfbe5bb4891

Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe — arXiv:2609.25728

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.25728
License (as archived)
CC0-1.0
Archived
2026-10-08T13:46:34.242Z
SHA-256 of the archived text
e048cf6c0818d83e9cb46641ff298bf5be7c1b3338ca542b967cdc85ee10cc0d
Stable URL of this page
https://metraipolis.com/documento/dc_3cfbe5bb4891

How to cite

Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe — arXiv:2609.25728 — arXiv (en), https://arxiv.org/abs/2609.25728 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3cfbe5bb4891 (Metraipolis archive dc_3cfbe5bb4891, sha256 e048cf6c0818d83e9cb46641ff298bf5be7c1b3338ca542b967cdc85ee10cc0d)
BibTeX
@misc{dc3cfbe5bb4891,
  title = {Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe — arXiv:2609.25728},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.25728},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3cfbe5bb4891; sha256 e048cf6c0818d83e9cb46641ff298bf5be7c1b3338ca542b967cdc85ee10cc0d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.25728. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-23 in cs.AI).
Categorie arXiv: Machine Learning (cs.LG) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2609.25728 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T13:18:38.255Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).