DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.61

Constraint-Aware Self-Supervised Learning for Edge Selection

Authors: Xinda Zheng, Frits de Nijs, and Edward Lam

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

Many edge-selection problems, such as the Traveling Salesman Problem and Orienteering Problem, are NP-hard, making them expensive to solve with exact methods and challenging to address with hand-crafted heuristics. Learning-based approaches provide an efficient alternative, while self-supervised methods avoid costly solution labels. However, existing approaches often still rely on heavy post-processing or narrow problem-specific designs. We propose a reusable self-supervised framework for edge-selection optimization that learns directly from unlabeled instances. The framework uses differentiable surrogate objectives and feasibility-driven penalties to encourage the model to learn feasibility-aware solution structure during training. To support efficient inference, we introduce a lightweight graph architecture centered on a cost-attention convolution, where edge costs and feasibility information directly shape message passing. Experiments on three problem families demonstrate strong solution quality and efficient inference across diverse edge-selection settings.

Cite as

Xinda Zheng, Frits de Nijs, and Edward Lam. Constraint-Aware Self-Supervised Learning for Edge Selection. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 61:1-61:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.CP.2026.61,
  author =	{Zheng, Xinda and de Nijs, Frits and Lam, Edward},
  title =	{{Constraint-Aware Self-Supervised Learning for Edge Selection}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{61:1--61:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.61},
  URN =		{urn:nbn:de:0030-drops-266949},
  doi =		{10.4230/LIPIcs.CP.2026.61},
  annote =	{Keywords: Combinatorial Optimization, Learning to optimize, Graph neural networks}
}

Search Results

Documents authored by Zheng, Xinda

Constraint-Aware Self-Supervised Learning for Edge Selection

Abstract

Cite as

Thanks for your feedback!

Could not send message