Research map / Optimization / Optimizers
Differentiable Quadratic Optimization For the Maximum Independent Set Problem
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 pCQO-MIS, a dataless differentiable quadratic relaxation of maximum independent set that adds a clique (complement) term, optimized with parallel momentum gradient descent and a fast MIS-check, with theory on local minimizers and stationary points.
Problem
Maximum Independent Set (MIS) is NP-hard; existing differentiable solvers are data-driven (poor generalization) or dataless quadratic relaxations lacking strong guarantees and scalability on dense graphs.
Approach
Adds a maximum-clique term -γ'/2 x^T A_{G'} x over the complement graph to the continuous QUBO relaxation of MIS, proves local minimizers are maximal independent sets under γ ≥ 1+γ'k (or γ > 1+γ'Δ(G')), and optimizes many degree-informed initializations in parallel with projected momentum gradient descent.
Key results
- On ER graphs pCQO-MIS reaches average MIS size 45.109 in under 55 minutes, above ReduMIS (44.87), CP-SAT (41.15) and Gurobi (39.14) and the best learning method (42.06).
- On SATLIB pCQO-MIS (425.148) falls short of ReduMIS, Gurobi and CP-SAT (425.96), but beats all learning-based methods (best 425.13 for DIFUSCO RL+S) with no training data.
- Adding the clique term improves over gamma'=0 by about 11 nodes on SATLIB and 4 nodes on ER at similar run-time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the MC term to the quadratic objective (ablation) | pCQO-MIS · SATLIB | MIS size: nearly 11 nodes | Helped |
| add the MC term to the quadratic objective (ablation) | pCQO-MIS · ER | MIS size: 4 nodes | Helped |
Surprising findings
- On SATLIB, the sparse benchmark, pCQO-MIS does not match ReduMIS and exact solvers, which the authors attribute to ReduMIS's graph reductions and 2-opt local search.
- The non-extremal stationary point is generally outside the box constraints, so it was never encountered in the experiments.
Limitations
- Falls short of ReduMIS and exact solvers on sparse SATLIB graphs.
- Hyperparameters (alpha, beta, T, eta, gamma, gamma') require tuning per graph set; run-times exclude tuning time.
- Problem remains non-convex and NP-hard; the method is a relaxation with no global optimality guarantee.
Experimental setup
Datasets: SATLIB ER (128 graphs, 700-800 nodes, p=0.15) DIMACS GNM random graphs
Benchmarks: SATLIB ER DIMACS
Metrics: average MIS size total sequential run-time (minutes)
Baselines: ReduMIS Gurobi CP-SAT iSCO DIFUSCO DIMES LwD GCN (Intel)
Builds on: QUBO relaxation for MIS projected momentum gradient descent PI-GNN dataless neural networks
Closest papers by meaning
- Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More (ICML 2024 · similarity 0.87)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.87)
- Differentiable extensions with rounding guarantees for combinatorial optimization over permutations (NeurIPS 2025 · similarity 0.87)
- Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation (ICML 2025 · similarity 0.86)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.86)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.86)
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.