Research map / Optimization / Optimizers
Differentiable extensions with rounding guarantees for combinatorial optimization over permutations
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 Birkhoff Extension, a continuous, a.e.-differentiable, polytime-computable extension of permutation functions to doubly stochastic matrices, with rounding guarantees, used for gradient-based combinatorial optimization on QAP, TSP and DFASP.
Problem
Optimizing real-valued objectives over permutations (QAP, TSP, directed feedback arc set) via continuous extensions that are differentiable and preserve solution quality under rounding.
Approach
A continuous variant of Birkhoff decomposition that fixes a total order of permutations (induced by an inner product with a score matrix) so coefficients are continuous, Lipschitz and a.e. differentiable; the resulting extension rounds any doubly stochastic matrix to a permutation without increasing f, and a score matrix set to an approximate solution gives local improvement.
Key results
- On QAPLIB (136 instances), the Birkhoff extension method (random S init.) achieves 6.30% average gap vs 7.67% for Gurobi Kaufman-Broeckx under the same ~2n-second budget.
- On TSP, MST-initialized score refinement improves MST tour lengths by about 4.6-8.5% (e.g., 4.746 to 4.345 at n=20), but Gurobi remains optimal.
- On DFASP at p=0.1 and n=250 and at large sizes for p=0.5 and p=0.9, the method (random S init.) beats Gurobi (e.g., 12198.7 vs 13652.4 at p=0.9, n=250) under equal time limits.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Birkhoff Extension with random score initialization instead of Gurobi, Kaufman-Broeckx | QAPLIB optimization · QAPLIB | Average gap from the best known: 7.67% -> 6.30% | Helped |
| Use Birkhoff Extension with MST-derived score initialization instead of Gurobi | TSP optimization · TSP, n=20, 30, 40, 50, 100 | Tour length: 3.889 vs 4.345; 4.531 vs 5.290; 5.190 vs 6.328; 5.707 vs 6.892; 7.748 vs 9.836 | Hurt |
| Use Birkhoff Extension with random score initialization instead of Gurobi | DFASP optimization · DFASP, p=0.1, 0.5, 0.9; n=20, 50, 100, 250 | Feedback-arc set size: p=0.1: 3.8 vs 4.7; 44.8 vs 53.0; 269.1 vs 289.0; 875.6 vs 991.3. p=0.5: 67.7 vs 65.0; 475.4 vs 496.5; 2229.9 vs 2123.4; | Mixed |
Surprising findings
- Gurobi is highly effective and optimal on TSP, outperforming the Birkhoff-based method in both accuracy and efficiency.
- Initializing the optimized matrix at the approximate permutation gives weaker guarantees than using it as the score matrix.
Limitations
- Computing the extension is O(n^5), so experiments truncate the decomposition to 5 terms.
- Gurobi outperforms the method on TSP in accuracy and speed.
- Neural optimizer component is only proof-of-concept with limited experiments.
Experimental setup
Datasets: QAPLIB randomly generated Euclidean TSP instances random directed Erdos-Renyi DFASP instances
Benchmarks: QAPLIB TSP random instances (n=20-100) DFASP random instances (n=20-250)
Metrics: average gap to best known assignment cost tour length feedback arc set size run-time
Baselines: Gurobi (Kaufman-Broeckx linearization) Fast Approximate QAP 2-opt MST approximation quadratic programming relaxation MCTS with random simulation Gurobi (DFASP)
Builds on: Birkhoff decomposition Frank-Wolfe Karalias set extension
Closest papers by meaning
- OT4P: Unlocking Effective Orthogonal Group Path for Permutation Relaxation (NeurIPS 2024 · similarity 0.87)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.87)
- Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent (ICML 2025 · similarity 0.85)
- Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems (ICML 2025 · similarity 0.85)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.85)
- Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More (ICML 2024 · 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.