Research map / Learning theory and algorithms / Combinatorial and search optimization
Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes UCom2, a framework for unsupervised combinatorial optimization that derives tight-upper-bound probabilistic objectives and greedy incremental derandomization for cardinality, minimum, covering, clique, and non-binary/uncertain conditions, evaluated on facility location, maximum coverage, and robust coloring.
Problem
Unsupervised learning for combinatorial optimization via the probabilistic method struggles to derive differentiable probabilistic objectives for commonly involved conditions (cardinality, minimum, covering) and relies on random sampling or naive rounding for derandomization.
Approach
Construct probabilistic objectives as expectations of tight upper bounds of penalized objectives (guaranteeing differentiability, entry-wise concavity, and matching minima), and perform greedy derandomization using incremental differences derived per condition, enabling fast and effective discrete solutions.
Key results
- On facility location, UCom2-short/middle/long rank as the top-3 by average rank sum (ARS), with UCom2-short reaching objective ~1.04 at ~1.9x normalized time.
- On maximum coverage, UCom2-short ranks first by ARS (8.5) with running time normalized to 2.8, while UCom2-long reaches objective 1.00 on all datasets.
- On robust coloring, UCom2 (CPU) achieves the best objective average (ranked 1st on most instances) with less running time than all baselines, and GPU is faster still.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UCom2-short rather than greedy | Facility location · Facility location (average) | objective (normalized): 1.17 -> 1.04 | Helped |
| Use UCom2-short rather than greedy | Facility location · Facility location (average) | time (normalized): 7.34 -> 1.89 | Hurt |
| Use UCom2-short rather than greedy | Maximum coverage · Maximum coverage (average) | objective (normalized): 0.99 -> 1.00 | Helped |
| Use UCom2-short rather than greedy | Maximum coverage · Maximum coverage (average) | time (normalized): 1.02 -> 5.41 | Hurt |
| Use UCom2 rather than the compared baselines | Robust coloring · Robust coloring (average rank) | sum rank: 6.13 -> 2.50 | Helped |
| Add good probabilistic objectives (ablation) | UCom2 · Facility location and maximum coverage | optimization quality | Helped |
| Use greedy derandomization instead of iterative rounding (ablation) | UCom2 · Combinatorial optimization problems | optimization quality | Helped |
| Use incremental derandomization (ablation) | UCom2 · Combinatorial optimization problems | speed | Helped |
Surprising findings
- The covering-constraint relaxation used in prior work (max(0, 1 - sum p_v)) is a lower bound rather than an upper bound of the non-coverage probability, so prior derivations violate the probabilistic-method requirements.
Limitations
- Assumes independent Bernoulli decision distributions; dependencies and other distributions are left as future work.
- Does not cover all CO conditions (e.g., cycles and trees are discussed only in appendix).
Experimental setup
Datasets: random graphs (rand500, rand800, rand1000) starbucks mcd subway twitch railway collins gavin krogan PPI
Benchmarks: facility location maximum coverage robust coloring
Metrics: objective running time average rank sum
Baselines: random greedy Gurobi SCIP CardNN CardNN-noTTO EGN-naive RL-transductive RL-inductive Greedy-RD Greedy-GA DC
Builds on: Erdős Goes Neural Karalias & Loukas 2020 probabilistic method iterative rounding CardNN
Closest papers by meaning
- Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation (NeurIPS 2022 · similarity 0.90)
- Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs (NeurIPS 2020 · similarity 0.89)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.87)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.86)
- Optimization Can Learn Johnson Lindenstrauss Embeddings (NeurIPS 2024 · similarity 0.85)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.