Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks

Hao Chen, Chendi Qian, Christopher Morris, Andrea Lodi, Can Li

arXivarxiv/2605.07113May 8, 2026cs.LGscore 0

Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we consider this challenge for Max-Cut, where branch and bound commonly uses semidefinite programming (SDP) relaxations to bound subproblems. We propose a Max-Cut-specific graph neural network that serves as a principled, lightweight neural proxy for these SDP solvers and can be plugged directly into an exact branch-and-bound framework. The proposed architecture has update…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.07113
curl -X POST /api/v1/records/arxiv/2605.07113/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.07113/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'