Reproduce “Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Haoyu Wang, Nan Wu, Hang Yang, Cong Hao, Pan Li
Researchers from Purdue, UCSB, and Georgia Tech developed an unsupervised learning framework for combinatorial optimization that trains end-to-end using a principled objective relaxation technique and provides deterministic performance guarantees. Their method achieved superior optimization performance and efficiency over existing machine learning baselines across traditional CO and challenging proxy-based CO problems, including circuit design.
Key insights
- The proposed 'entry-wise concavity' principle for relaxing objective functions allows for deterministic performance guarantees and effective gradient-based optimization in unsupervised combinatorial optimization.
- Any binary-input function can be relaxed to an entry-wise affine function, a special case of entry-wise concavity, and GNNs can effectively model such functions.
- Guiding the design of learned 'proxy' objectives in proxy-based CO (PCO) problems using the entry-wise concavity principle leads to superior optimization performance.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.