Exact Combinatorial Optimization with Graph Convolutional Neural Networks
Open accessThe DOI matches its OpenAlex record; 25 of the 25 references it cites were found in a registry or an index.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Adam: A Method for Stochastic Optimization
Kingma, D. P., & Ba, J. (2014) · arXiv · doi:10.48550/arxiv.1412.6980 · Cited by 98,946
The graph neural network model
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2005605 · Cited by 9,582
Geurts, P., Ernst, D., & Wehenkel, L. (2006) · Machine Learning · doi:10.1007/s10994-006-6226-1 · Cited by 9,300 · cited 1×
“rformance of full strong branching (FSB), our slow expert. We also compare against three machine learning branchers: the learning-to-score approach of Alvarez et al. [4] (TREES) based on an ExtraTrees[17] model, as well as the learning-to-rankapproachesfromKhalil etal.[29](SVMRANK) andHansknechtetal.[23](LMART),basedo…”
MethodHow Powerful are Graph Neural Networks?
Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2018) · arXiv · doi:10.48550/arxiv.1810.00826 · Cited by 6,078
Optimizing search engines using clickthrough data
Joachims, T. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775067 · Cited by 3,873 · cited 1×
“…branchers: the learning-to-score approach of Alvarez et al. [4] ( TREES ) based on an ExtraTrees [18] model, as well as the learning-to-rank approaches from Khalil et al. [30] ( SVMRANK ) and Hansknecht et al. [24] ( LMART ), based on an SVMrank [28] and a LambdaMART [13] model, respectively.”
MethodNeural Message Passing for Quantum Chemistry
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.01212 · Cited by 3,440 · cited 1×
“.3 Policy parametrization We parametrize our variable selection policy πθ(a|st) as a graph convolutional neural network (GCNN) [22; 45; 11]. Such models, also known as message-passing neural networks [19], are extensions of convolutional neural networks from grid-structured data (as in images or sounds) to arbitrary g…”
MethodDynamic Programming and Markov Processes.
Freimer, M., & Howard, R. A. (1961) · Journal of the American Statistical Association · doi:10.2307/2282268 · Cited by 3,378
Nemhauser, G. L., & Wolsey, L. A. (1972) · Cited by 3,365
Formal Semantics for Kolmogorov-Arnold Network Representations of Operational Games
Zhukov, G. A. (2025) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.15206559 · Cited by 3,212
A new model for learning in graph domains
Gori, M., Monfardini, G., & Scarselli, F. (2006) · Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005. · doi:10.1109/ijcnn.2005.1555942 · Cited by 2,075 · cited 1×
“We parametrize our variable selection policy π θ ( a | s t ) as a graph convolutional neural network [23; 46; 12].”
MethodProduction Planning by Mixed Integer Programming
(2006) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/0-387-33477-7 · Cited by 959 · cited 1×
“tative set of MILP instances [40]. However, in many contexts it is common to repeatedly solve similar combinatorial optimization problems, e.g., day-to-day production planning and lot-sizing problems [43], which may significantly differ from the set of instances on which B&B algorithms are typically evaluated. It i…”
Optimal control of Markov processes with incomplete state information
Åström, K. J. (1965) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(65)90154-x · Cited by 854 · cited 1×
“…note that this is really only a subset of the solver state, which technically turns the process into a partially-observable Markov decision process [6], but also that excellent variable selection policies such as strong branching are able to do well despite relying only on a subset of the solver…”
BackgroundLearning to Branch in Mixed Integer Programming
Khalil, E., Le Bodic, P., Song, L., Nemhauser, G., & Dilkina, B. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10080 · Cited by 298 · cited 1×
“In practice, running strong branching at every node is prohibitive, and modern B&B solvers instead rely on hybrid branching [3; 1] which computes strong branching scores only at the beginning of the solving process and gradually switches to simpler heuristics such as: the conflict score (in the original article), the…”
BackgroundA comparison of heuristics and relaxations for the capacitated plant location problem
Cornuejols, G., Sridharan, R., & Thizy, J. M. (1991) · European Journal of Operational Research · doi:10.1016/0377-2217(91)90261-s · Cited by 285 · cited 1×
“Our third benchmark is comprised of capacitated facility location instances generated following Cornuejols et al. [14], with 100 facilities.”
BackgroundLearning to Search in Branch and Bound Algorithms
He, H., Daumé, H., & Eisner, J. M. (2014) · neural information processing systems · Cited by 275
Machine learning for combinatorial optimization: A methodological tour d'horizon
Bengio, Y., Lodi, A., & Prouvost, A. (2021) · European Journal of Operational Research · doi:10.1016/j.ejor.2020.07.063 · Cited by 195
Self-citationLearning to Run Heuristics in Tree Search
Khalil, E. B., Dilkina, B., Nemhauser, G. L., Ahmed, S., & Shao, Y. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/92 · Cited by 192 · cited 1×
“…of the oracle procedure that expands the node whose feasible set contains the optimal solution, while Song et al. [48] learn node selection and pruning heuristics by imitation learning of shortest paths to good feasible solutions, and Khalil et al. [32] learn primal heuristics for B&B algorithms.”
MethodLearning Rate Based Branching Heuristic for SAT Solvers
Jia, L., Ganesh, V., Poupart, P., et al. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-40970-2_9 · Cited by 175 · cited 1×
“Other works learn variable selection policies, but for algorithms less general than B&B. Liang et al. [39] learn a variable selection policy for SAT solvers using a bandit approach, and Lederman et al. [36] extend their work by taking a reinforcement learning approach with graph convolutional…”
MethodA Machine Learning-Based Approximation of Strong Branching
Alvarez, A. M., Louveaux, Q., & Wehenkel, L. (2017) · INFORMS Journal on Computing · doi:10.1287/ijoc.2016.0723 · Cited by 173
On learning and branching: a survey
Lodi, A., & Zarpellon, G. (2017) · TOP · doi:10.1007/s11750-017-0451-6 · Cited by 172 · cited 2×
“…on variable selection, also known as the branching problem , which lies at the core of the B&B paradigm yet is still not well theoretically understood [41], and adopt an imitation learning strategy to learn a fast approximation of strong branching , a high-quality but expensive branching rule.”
BackgroundMethodSelf-citationLearning to Solve SMT Formulas
Balunović, M., Bielik, P., & Vechev, M. (2018) · neural information processing systems · Cited by 100
DASH: Dynamic Approach for Switching Heuristics
Liberto, G. M. D., Kadıoğlu, S., Leo, K., & Malitsky, Y. (2015) · European Journal of Operational Research · doi:10.1016/j.ejor.2015.08.018 · Cited by 74 · cited 1×
“gainst these approachesin Section 5. Other works also consider using machine learning to improve variable selection in branch-andbound, without directly learning a branching policy. Di Liberto et al. [14] learn a clustering-based classifiertopickavariableselectionruleateverybranchingdecisionuptoacertaindepth,whileBalca…”
BackgroundCuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman ProblemPreprint
Hansknecht, C., Joormann, I., & Stiller, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.01415 · Cited by 58 · cited 4×
“ning branchers: the learning-to-score approach of Alvarez et al. [4] (TREES) based on an ExtraTrees[17] model, as well as the learning-to-rankapproachesfromKhalil etal.[29](SVMRANK) andHansknechtetal.[23](LMART),basedonanSVMrank[27]andaLambdaMART [12] model,respectively. The TREES model uses variable-wisefeatures from…”
BackgroundMethodInfluentialOn Amortizing Inference Cost for Structured Prediction
Srikumar, V., Kundu, G., & Roth, D. (2012) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · Cited by 27
Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement LearningPreprint
Lederman, G., Rabe, M. N., Lee, E. A., & Seshia, S. A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.08058 · Cited by 17 · cited 1×
“[36] extend their work by taking a reinforcement learning approach with graph convolutional neural networks.”
Background
Cited by
Graph neural networks: A review of methods and applications
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2020) · AI Open · doi:10.1016/j.aiopen.2021.01.001 · Cited by 6,880
Graph Neural Networks: A Review of Methods and Applications
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2018) · arXiv · doi:10.48550/arxiv.1812.08434 · Cited by 6,880
Machine learning for combinatorial optimization: A methodological tour d'horizon
Bengio, Y., Lodi, A., & Prouvost, A. (2021) · European Journal of Operational Research · doi:10.1016/j.ejor.2020.07.063 · Cited by 195
Self-citation
Metadata
- Authors
- Gasse, M., Chételat, D., Ferroni, N., Charlin, L., & Lodi, A.
- Venue
- arXiv (Cornell University)
- Publisher
- Cornell University
- Published
- 2019-06-04
- Volume
- 32
- Pages
- 15554-15566
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1906.01629
- OpenAlex
- W2948268323
- Cited by
- 237
- References
- 25
- Type
- posted content
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.