Browse State-of-the-Art › Combinatorial Optimization
Combinatorial Optimization
401 papers with code · 0 benchmarks · 3 datasets archive 2025-07-28
Combinatorial Optimization is a category of problems which requires optimizing a function over a combination of discrete objects and the solutions are constrained. Examples include finding shortest paths in a graph, maximizing value in the Knapsack problem and finding boolean settings that satisfy a set of constraints. Many of these problems are NP-Hard, which means that no polynomial time solution can be developed for them. Instead, we can only produce approximations in polynomial time that are guaranteed to be some factor worse than the true optimal solution.
Description from the archive archive 2025-07-28.
Benchmarks archive 2025-07-28
No benchmark for this task in the archive.
Libraries
Not in the archive: the export carries no per-task library table, so there is nothing to show at snapshot 2025-07-28.
Datasets archive 2025-07-28
3 datasets whose archive record lists this task, ordered by the archive's paper count.
Subtasks archive 2025-07-28
No subtask under this task in the archive's task tree.
Papers archive 2025-07-28
archive papers tagged: 1,277 · with a code link: 401 · where Syntology ran a sample: 122 (104 with a run with no instrument failure, 18 where every run was a failure of Syntology's instrument) Syntology
Show: all tagged papersonly where code ran (122 of 1,277 tagged: 104 with a run with no instrument failure, 18 where every run was a failure of Syntology's instrument)
Page 1 of 13: papers 1 to 100 of 1,277, in archive order: by repositories listed in the archive (most first), then newest first, not by stars (the archive holds no stars, so PwC's “Social” and “Latest” sorts cannot be reproduced). Papers that list no repository come after every paper that lists one.
Papers without a page here are shown as plain text. A Syntology line reads “N ran (of which C constructed an object rather than computing a result; K with no instrument failure: H honoured, V violated, P with no contract checked; I where Syntology's instrument failed) · U unverified”; the figure “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. When the archive marks a repository official for the paper, the line starts with that repository's state (the archive's flag, not a verdict on who wrote the code); hover it for the repositories the samples that ran came from. The first sentence of the abstract is shown for the first 30 papers; every abstract is on its paper's page.
-
9 Jun 2015 21 repositories listed Syntology 18 ran (of which 0 constructed an object rather than computing a result; 13 with no instrument failure: 3 honoured, 1 violated, 9 with no contract checked; 5 where Syntology's instrument failed) · 5 unverified (of 23 harvested samples) · 9 pointer-only (licence)It differs from the previous attention attempts in that, instead of using attention to blend hidden units of an encoder to a context vector at each decoder step, it uses attention as a pointer to select a member of the…
-
22 Mar 2018 15 repositories listed Syntology official (archive's flag): 3 ran · 27 ran (of which 0 constructed an object rather than computing a result; 16 with no instrument failure: 3 honoured, 0 violated, 13 with no contract checked; 11 where Syntology's instrument failed) · 13 unverified (of 40 harvested samples) · 5 pointer-only (licence)The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development.
-
29 Nov 2016 10 repositories listed Syntology 14 ran (of which 0 constructed an object rather than computing a result; 10 with no instrument failure: 1 honoured, 1 violated, 8 with no contract checked; 4 where Syntology's instrument failed) · 6 unverified (of 20 harvested samples) · 7 pointer-only (licence)Despite the computational expense, without much engineering and heuristic designing, Neural Combinatorial Optimization achieves close to optimal results on 2D Euclidean graphs with up to 100 nodes.
-
18 May 2018 9 repositories listed Syntology 4 ran (of which 0 constructed an object rather than computing a result; 4 with no instrument failure: 3 honoured, 1 violated, 0 with no contract checked; 0 where Syntology's instrument failed) · 0 unverified (of 4 harvested samples) · 4 pointer-only (licence)A generally intelligent agent must be able to teach itself how to solve problems in complex domains with minimal human supervision.
-
5 Apr 2017 8 repositories listed Syntology community repositories only · 2 ran (of which 0 constructed an object rather than computing a result; 1 with no instrument failure: 0 honoured, 1 violated, 0 with no contract checked; 1 where Syntology's instrument failed) · 0 unverified (of 2 harvested samples) · 2 pointer-only (licence)The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error.
-
4 Jan 2024 6 repositories listed Syntology official (archive's flag): 1 ran · 1 ran (of which 0 constructed an object rather than computing a result; 0 with no instrument failure: 0 honoured, 0 violated, 0 with no contract checked; 1 where Syntology's instrument failed) · 0 unverified (of 1 harvested sample)EoH represents the ideas of heuristics in natural language, termed thoughts.
-
4 Jun 2019 6 repositories listed Syntology official: harvested, nothing ran · 0 ran · 2 unverified (of 2 harvested samples) · 1 pointer-only (licence)Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm.
-
27 Jul 2022 5 repositories listedWe demonstrate its abilities using a pathfinding problem on video game maps as guiding example, as well as three other applications from operations research.
-
26 May 2022 5 repositories listed Syntology official (archive's flag): 12 ran · 16 ran (of which 4 constructed an object rather than computing a result; 9 with no instrument failure: 0 honoured, 0 violated, 9 with no contract checked; 7 where Syntology's instrument failed) · 7 unverified (of 23 harvested samples) · 2 pointer-only (licence)In this paper, we present DevFormer, a novel transformer-based architecture for addressing the complex and computationally demanding problem of hardware design optimization.
-
25 Mar 2020 5 repositories listed Syntology community repositories only · 10 ran (of which 0 constructed an object rather than computing a result; 6 with no instrument failure: 0 honoured, 1 violated, 5 with no contract checked; 4 where Syntology's instrument failed) · 1 unverified (of 11 harvested samples) · 5 pointer-only (licence)Building on recent progress at the intersection of combinatorial optimization and deep learning, we propose an end-to-end trainable architecture for deep graph matching that contains unmodified combinatorial solvers.
-
9 Jun 2021 4 repositories listed Syntology official: harvested, nothing ran · 0 ran · 1 unverified (of 1 harvested sample) · 1 pointer-only (licence)While active search is simple to implement, it is not competitive with state-of-the-art methods because adjusting all model weights for each test instance is very time and memory intensive.
-
8 Apr 2021 4 repositories listedScheduling is a fundamental task occurring in various automated systems applications, e. g., optimal schedules for machines on a job shop allow for a reduction of production costs and waste.
-
12 Jun 2020 4 repositories listed Syntology official: harvested, nothing ran · 3 ran (of which 0 constructed an object rather than computing a result; 1 with no instrument failure: 1 honoured, 0 violated, 0 with no contract checked; 2 where Syntology's instrument failed) · 4 unverified (of 7 harvested samples)End-to-end training of neural network solvers for graph combinatorial optimization problems such as the Travelling Salesperson Problem (TSP) have seen a surge of interest recently, but remain intractable and inefficient…
-
6 Jul 2018 4 repositories listed Syntology official (archive's flag): 7 ran · 7 ran (of which 0 constructed an object rather than computing a result; 7 with no instrument failure: 0 honoured, 0 violated, 7 with no contract checked; 0 where Syntology's instrument failed) · 8 unverified (of 15 harvested samples)We present Memory Augmented Policy Optimization (MAPO), a simple and novel way to leverage a memory buffer of promising trajectories to reduce the variance of policy gradient estimate.
-
12 Feb 2018 4 repositories listed Syntology 3 ran (of which 0 constructed an object rather than computing a result; 2 with no instrument failure: 1 honoured, 1 violated, 0 with no contract checked; 1 where Syntology's instrument failed) · 0 unverified (of 3 harvested samples) · 3 pointer-only (licence)Our model represents a parameterized stochastic policy, and by applying a policy gradient algorithm to optimize its parameters, the trained model produces the solution as a sequence of consecutive actions in real time…
-
2 Sep 2024 3 repositories listedThrough extensive experimental analysis, we identified three key challenges in designing effective data management strategies that enable the model to achieve long-context capability without sacrificing performance in…
-
2 Feb 2024 3 repositories listed Syntology official (archive's flag): 4 ran · 5 ran (of which 1 constructed an object rather than computing a result; 2 with no instrument failure: 0 honoured, 0 violated, 2 with no contract checked; 3 where Syntology's instrument failed) · 5 unverified (of 10 harvested samples) · 2 pointer-only (licence)The omnipresence of NP-hard combinatorial optimization problems (COPs) compels domain experts to engage in trial-and-error heuristic design.
-
29 Jun 2023 3 repositories listed Syntology official (archive's flag): 9 ran · 12 ran (of which 0 constructed an object rather than computing a result; 12 with no instrument failure: 0 honoured, 0 violated, 12 with no contract checked; 0 where Syntology's instrument failed) · 4 unverified (of 16 harvested samples) · 3 pointer-only (licence)To fill this gap, we introduce RL4CO, a unified and extensive benchmark with in-depth library coverage of 23 state-of-the-art methods and more than 20 CO problems.
-
2 Jul 2021 3 repositories listedCombinatorial optimization problems are pervasive across science and industry.
-
3 Jun 2021 3 repositories listed Syntology official (archive's flag): 3 ran · 7 ran (of which 2 constructed an object rather than computing a result; 2 with no instrument failure: 0 honoured, 0 violated, 2 with no contract checked; 5 where Syntology's instrument failed) · 3 unverified (of 10 harvested samples) · 6 pointer-only (licence)We propose Implicit Maximum Likelihood Estimation (I-MLE), a framework for end-to-end learning of models combining discrete exponential family distributions and differentiable neural components.
-
30 Oct 2020 3 repositories listed Syntology community repositories only · 1 ran (of which 0 constructed an object rather than computing a result; 1 with no instrument failure: 0 honoured, 0 violated, 1 with no contract checked; 0 where Syntology's instrument failed) · 7 unverified (of 8 harvested samples) · 8 pointer-only (licence)We introduce Policy Optimization with Multiple Optima (POMO), an end-to-end approach for building such a heuristic solver.
-
9 Feb 2020 3 repositories listedHowever, the fact is, the state of an instance is changed according to the decision that the model made at different construction steps, and the node features should be updated correspondingly.
-
14 May 2025 2 repositories listedWe present RXTX, a new algorithm for computing the product of matrix by its transpose XXᵗ for X∈ℝ^(n×m).
-
6 Sep 2024 2 repositories listed Syntology official (archive's flag): 6 ran · 6 ran (of which 0 constructed an object rather than computing a result; 4 with no instrument failure: 1 honoured, 0 violated, 3 with no contract checked; 2 where Syntology's instrument failed) · 1 unverified (of 7 harvested samples) · 7 pointer-only (licence)In this paper, we design a family of non-autoregressive neural networks to solve CO problems under positive linear constraints with the following merits.
-
5 Sep 2024 2 repositories listed Syntology official (archive's flag): 2 ran · 2 ran (of which 0 constructed an object rather than computing a result; 2 with no instrument failure: 0 honoured, 0 violated, 2 with no contract checked; 0 where Syntology's instrument failed) · 2 unverified (of 4 harvested samples)To address these issues, we propose Parallel AutoRegressive Combinatorial Optimization (PARCO), a reinforcement learning framework designed to construct high-quality solutions for multi-agent combinatorial tasks…
-
29 Jun 2024 2 repositories listedEmploying a high-efficiency Graph Neural Network (GNN) for global instance dividing and a fixed-length sub-path solver for conquering divided sub-problems, the proposed UDC framework demonstrates extensive…
-
25 Jun 2024 2 repositories listed Syntology official (archive's flag): 4 ran · 4 ran (of which 0 constructed an object rather than computing a result; 3 with no instrument failure: 0 honoured, 1 violated, 2 with no contract checked; 1 where Syntology's instrument failed) · 3 unverified (of 7 harvested samples) · 7 pointer-only (licence)Specifically, the whole VNE process is decomposed into an upper-level policy for deciding whether to admit the arriving VNR or not and a lower-level policy for allocating resources of the physical network to meet the…
-
11 Jun 2024 2 repositories listed Syntology official (archive's flag): 5 ran · 5 ran (of which 0 constructed an object rather than computing a result; 5 with no instrument failure: 2 honoured, 0 violated, 3 with no contract checked; 0 where Syntology's instrument failed) · 1 unverified (of 6 harvested samples)We curate MILP distributions from existing work in this area as well as real-world problems that have not been used, and classify them into different hardness levels.
-
14 May 2024 2 repositories listed Syntology official (archive's flag): 4 ran · 4 ran (of which 0 constructed an object rather than computing a result; 0 with no instrument failure: 0 honoured, 0 violated, 0 with no contract checked; 4 where Syntology's instrument failed) · 3 unverified (of 7 harvested samples) · 3 pointer-only (licence)Then, for various conditions commonly involved in different CO problems, we derive nontrivial objectives and derandomization to meet the targets.
-
2 May 2024 2 repositories listed Syntology official (archive's flag): 4 ran · 4 ran (of which 0 constructed an object rather than computing a result; 2 with no instrument failure: 0 honoured, 0 violated, 2 with no contract checked; 2 where Syntology's instrument failed) · 1 unverified (of 5 harvested samples)Learning to solve vehicle routing problems (VRPs) has garnered much attention.
-
11 Mar 2024 2 repositories listed Syntology official (archive's flag): 10 ran · 10 ran (of which 0 constructed an object rather than computing a result; 7 with no instrument failure: 2 honoured, 0 violated, 5 with no contract checked; 3 where Syntology's instrument failed) · 0 unverified (of 10 harvested samples)
-
11 Mar 2024 2 repositories listed
-
25 Jan 2024 2 repositories listed
-
21 Aug 2023 2 repositories listed
-
26 Jun 2023 2 repositories listed
-
31 Jan 2023 2 repositories listed
-
19 Jan 2023 2 repositories listed
-
9 Jan 2023 2 repositories listed
-
12 May 2022 2 repositories listed
-
4 Mar 2022 2 repositories listed Syntology official (archive's flag): 1 ran · 1 ran (of which 0 constructed an object rather than computing a result; 1 with no instrument failure: 1 honoured, 0 violated, 0 with no contract checked; 0 where Syntology's instrument failed) · 0 unverified (of 1 harvested sample)
-
22 Nov 2021 2 repositories listed
-
29 Oct 2021 2 repositories listed Syntology official (archive's flag): 10 ran · 11 ran (of which 0 constructed an object rather than computing a result; 11 with no instrument failure: 0 honoured, 0 violated, 11 with no contract checked; 0 where Syntology's instrument failed) · 1 unverified (of 12 harvested samples)
-
14 Sep 2021 2 repositories listed Syntology official (archive's flag): 2 ran · 4 ran (of which 0 constructed an object rather than computing a result; 0 with no instrument failure: 0 honoured, 0 violated, 0 with no contract checked; 4 where Syntology's instrument failed) · 2 unverified (of 6 harvested samples)
-
21 Jun 2021 2 repositories listed Syntology official: harvested, nothing ran · 4 ran (of which 1 constructed an object rather than computing a result; 4 with no instrument failure: 0 honoured, 0 violated, 4 with no contract checked; 0 where Syntology's instrument failed) · 3 unverified (of 7 harvested samples) · 6 pointer-only (licence)
-
6 Jun 2021 2 repositories listed
-
19 Jan 2021 2 repositories listed
-
Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching16 Dec 2020 2 repositories listed Syntology official (archive's flag): 7 ran · 7 ran (of which 0 constructed an object rather than computing a result; 1 with no instrument failure: 1 honoured, 0 violated, 0 with no contract checked; 6 where Syntology's instrument failed) · 1 unverified (of 8 harvested samples) · 8 pointer-only (licence)
-
23 Nov 2020 2 repositories listed
-
20 Nov 2020 2 repositories listed
-
11 Nov 2020 2 repositories listed Syntology community repositories only · 1 ran (of which 0 constructed an object rather than computing a result; 0 with no instrument failure: 0 honoured, 0 violated, 0 with no contract checked; 1 where Syntology's instrument failed) · 0 unverified (of 1 harvested sample)
-
10 Nov 2020 2 repositories listed Syntology official (archive's flag): 2 ran · 2 ran (of which 0 constructed an object rather than computing a result; 2 with no instrument failure: 1 honoured, 1 violated, 0 with no contract checked; 0 where Syntology's instrument failed) · 0 unverified (of 2 harvested samples) · 2 pointer-only (licence)
-
7 Nov 2020 2 repositories listed
-
22 Oct 2020 2 repositories listed
-
13 Sep 2020 2 repositories listed
-
19 Jul 2020 2 repositories listed Syntology official (archive's flag): 1 ran · 1 ran (of which 0 constructed an object rather than computing a result; 0 with no instrument failure: 0 honoured, 0 violated, 0 with no contract checked; 1 where Syntology's instrument failed) · 0 unverified (of 1 harvested sample) · 1 pointer-only (licence)
-
18 Jun 2020 2 repositories listed
-
6 May 2020 2 repositories listed Syntology official (archive's flag): 2 ran · 2 ran (of which 0 constructed an object rather than computing a result; 0 with no instrument failure: 0 honoured, 0 violated, 0 with no contract checked; 2 where Syntology's instrument failed) · 0 unverified (of 2 harvested samples) · 2 pointer-only (licence)
-
13 Apr 2020 2 repositories listed
-
20 Feb 2020 2 repositories listed
-
12 Nov 2019 2 repositories listed Syntology community repositories only · 7 ran (of which 0 constructed an object rather than computing a result; 7 with no instrument failure: 0 honoured, 0 violated, 7 with no contract checked; 0 where Syntology's instrument failed) · 2 unverified (of 9 harvested samples)
-
9 Sep 2019 2 repositories listed Syntology community repositories only · 10 ran (of which 0 constructed an object rather than computing a result; 10 with no instrument failure: 0 honoured, 0 violated, 10 with no contract checked; 0 where Syntology's instrument failed) · 10 unverified (of 20 harvested samples)
-
28 Mar 2019 2 repositories listed
-
8 Mar 2019 2 repositories listed
-
25 Oct 2018 2 repositories listed
-
19 Oct 2018 2 repositories listed
-
4 Jul 2018 2 repositories listed
-
20 Jun 2025 1 repository listed Syntology official (archive's flag): 2 ran · 2 ran (of which 0 constructed an object rather than computing a result; 0 with no instrument failure: 0 honoured, 0 violated, 0 with no contract checked; 2 where Syntology's instrument failed) · 0 unverified (of 2 harvested samples)
-
18 Jun 2025 1 repository listed
-
10 Jun 2025 1 repository listed
-
9 Jun 2025 1 repository listed Syntology official (archive's flag): 7 ran · 7 ran (of which 0 constructed an object rather than computing a result; 7 with no instrument failure: 0 honoured, 0 violated, 7 with no contract checked; 0 where Syntology's instrument failed) · 5 unverified (of 12 harvested samples)
-
5 Jun 2025 1 repository listed
-
4 Jun 2025 1 repository listed Syntology official (archive's flag): 2 ran · 2 ran (of which 1 constructed an object rather than computing a result; 1 with no instrument failure: 0 honoured, 0 violated, 1 with no contract checked; 1 where Syntology's instrument failed) · 0 unverified (of 2 harvested samples) · 2 pointer-only (licence)
-
25 May 2025 1 repository listed
-
25 May 2025 1 repository listed
-
22 May 2025 1 repository listed
-
22 May 2025 1 repository listed Syntology official (archive's flag): 1 ran · 1 ran (of which 1 constructed an object rather than computing a result; 1 with no instrument failure: 0 honoured, 0 violated, 1 with no contract checked; 0 where Syntology's instrument failed) · 0 unverified; the one sample that ran constructed an object rather than computing a result (of 1 harvested sample) · 1 pointer-only (licence)
-
19 May 2025 1 repository listed
-
12 May 2025 1 repository listed
-
6 May 2025 1 repository listed
-
5 May 2025 1 repository listed
-
7 Apr 2025 1 repository listed
-
6 Apr 2025 1 repository listed Syntology official (archive's flag): 1 ran · 1 ran (of which 0 constructed an object rather than computing a result; 1 with no instrument failure: 1 honoured, 0 violated, 0 with no contract checked; 0 where Syntology's instrument failed) · 0 unverified (of 1 harvested sample) · 1 pointer-only (licence)
-
20 Mar 2025 1 repository listed Syntology official (archive's flag): 2 ran · 2 ran (of which 0 constructed an object rather than computing a result; 2 with no instrument failure: 0 honoured, 0 violated, 2 with no contract checked; 0 where Syntology's instrument failed) · 4 unverified (of 6 harvested samples)
-
20 Mar 2025 1 repository listed
-
18 Mar 2025 1 repository listed
-
6 Mar 2025 1 repository listed
-
5 Mar 2025 1 repository listed
-
26 Feb 2025 1 repository listed
-
22 Feb 2025 1 repository listed Syntology official (archive's flag): 2 ran · 2 ran (of which 0 constructed an object rather than computing a result; 1 with no instrument failure: 0 honoured, 0 violated, 1 with no contract checked; 1 where Syntology's instrument failed) · 3 unverified (of 5 harvested samples) · 5 pointer-only (licence)
-
21 Feb 2025 1 repository listed
-
20 Feb 2025 1 repository listed
-
18 Feb 2025 1 repository listed Syntology official (archive's flag): 4 ran · 4 ran (of which 0 constructed an object rather than computing a result; 2 with no instrument failure: 1 honoured, 1 violated, 0 with no contract checked; 2 where Syntology's instrument failed) · 0 unverified (of 4 harvested samples) · 4 pointer-only (licence)
-
18 Feb 2025 1 repository listed
-
5 Feb 2025 1 repository listed
-
4 Feb 2025 1 repository listed
-
1 Feb 2025 1 repository listed Syntology official (archive's flag): 1 ran · 2 ran (of which 1 constructed an object rather than computing a result; 2 with no instrument failure: 1 honoured, 0 violated, 1 with no contract checked; 0 where Syntology's instrument failed) · 1 unverified (of 3 harvested samples) · 3 pointer-only (licence)
-
30 Jan 2025 1 repository listed
-
15 Jan 2025 1 repository listed Syntology official (archive's flag): 8 ran · 8 ran (of which 0 constructed an object rather than computing a result; 7 with no instrument failure: 0 honoured, 0 violated, 7 with no contract checked; 1 where Syntology's instrument failed) · 2 unverified (of 10 harvested samples) · 1 pointer-only (licence)
-
9 Jan 2025 1 repository listed
Syntology lines on 46 of the papers shown; no Syntology record for the others (a paper without an arXiv id cannot be joined to the graph, and absence from the graph layer is not a recorded non-run). “Ran” means the sample executed on a synthesized fixture, not that the paper's result was reproduced; each line links to that paper's sample list. Syntology's record for this page last changed ; when this build read Syntology's graph is in the build record. For agents: get_harvested_code_for_paper(arxiv_id) lists each paper's samples; how to connect.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections