Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Differentiable extensions with rounding guarantees for combinatorial optimization over permutations
Authors: Robert (Riley) Nerem, Zhishang Luo, Akbar Rafiey, Yusu Wang
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We present experimental results to verify our theoretical results on several combinatorial optimization problems related to permutations. |
| Researcher Affiliation | Academia | Robert R. Nerem UCSD EMAIL Zhishang Luo UCSD EMAIL Akbar Rafiey NYU EMAIL Yusu Wang UCSD EMAIL |
| Pseudocode | Yes | Algorithm 1 Classical Birkhoff decomposition [8] Algorithm 2 Continuous Birkhoff decomposition Algorithm 3 Static score Frank-Wolfe over Dn Algorithm 4 Dynamic score Frank-Wolfe over Dn Algorithm 5 Constrained Continuous Birkhoff decomposition Algorithm 6 Constrained Frank-Wolfe over Dn Algorithm 7 2-approximation maximum weight perfect matching |
| Open Source Code | Yes | We have made code and data public (or reference the data source where appropriate). It is available at https://github.com/luckyjackluo/BE-for-Combinatorial Optimization. |
| Open Datasets | Yes | We evaluate on the QAPLIB library [10], which contains N = 136 problem instances with sizes between 12 and 256. Some instances have confirmed optimal objective values, while others have the best-known objective values reported. |
| Dataset Splits | Yes | We generate a training dataset with N = 6000 instances and with a mixture of instance sizes, n = 20, 30, and 40. The input to Nθ, for each instance, is the vector XI and the MST-derived score matrix St. We trained Nθ for T = 100 epochs, and selected a learning rate of η = 0.001 using a hyperparameter search of the set {0.01, 0.05, 0.001, 0.0005}. At testing we optimize the trained neural network Nθ for a few more iterations as a fine-tuning. |
| Hardware Specification | Yes | We are using Cent OS Linux 7 system on a Intel Xeon CPU E5-2650L processor. Gurobi is run on a single thread per process. |
| Software Dependencies | No | The paper mentions "Gurobi" and the "Adam optimizer [1]" but does not provide specific version numbers for these or other software libraries. |
| Experiment Setup | Yes | In particular, we update the score matrix every 10 epochs (i.e., update_score = True in Alg. 4 if and only if t {10, 20, . . . , T}). To overcome the O(n5) time complexity, we truncate the Birkhoff decomposition to only the first k = 5 terms. Automatic differentiation is used to compute gradients. ... For Gurobi, we use the Kaufman Broeckx linearization [30] for the Mixed-Integer Linear Programming (MILP), and we set same maximum time budget for Gurobi and our method as 2n seconds... The learning rate is η = 0.01. The maximum number of optimization steps is T = 10000, and early stopping triggers after 2000 steps without improvement. ... we limit the runtime of both algorithms to n/10 minutes for equal comparison. ... The learning rate is η = 0.005. |