Elamur Research⌕
☰
home / papers / 2023 / 基于学习-推理的约束求解方法研究进展

基于学习-推理的约束求解方法研究进展

Summary

This Chinese-language survey (Journal of Software, vol. 35, no. 1, 2024; published online July 2023) reviews how machine learning is being combined with automated reasoning to solve constraint satisfaction problems (CSPs) such as SAT, graph coloring and TSP. Classical solvers built on backtracking, constraint propagation and local search depend on hand-designed heuristics, which require domain expertise and careful tuning. The authors sort recent "learn to reason" work into three families:

  • MPNN-based methods encode instances as bipartite graphs. They either predict outcomes end to end or learn variable-selection and branching heuristics through reinforcement learning.
  • Sequence-to-sequence methods build on Pointer Network and Actor-Critic training and are used mostly for routing.
  • Optimization-based methods include semidefinite programming, convex optimization and empirical risk minimization, for example SAT-Net.

For each family, the survey tabulates the problems tackled, the test data and the reported results, and compares methods from several angles. It contributes no new experiments. Its value is a structured map of the field. The map shows that learned solvers adapt and scale well but usually still lag behind mature solvers in wall-clock time.

Key points

  • NeuroSAT reaches about 85% satisfiability-prediction accuracy on random SAT instances (about 40 variables, 200 clauses). Cameron et al. extend it to predict both satisfiability and assignments, reaching 75–82% accuracy on random 3-SAT.
  • Liu et al. apply an MPNN with weighted edges to pseudo-Boolean problems. They exceed 85% accuracy on 0-1 knapsack and weighted independent set instances with fewer than 40 variables and report roughly 10% lower runtime than CPLEX.
  • Kurin et al. combine an MPNN with DQN inside CDCL. The learned heuristic needs one-third to one-half fewer iterations than VSIDS and generalizes to problems with five times more variables.
  • Wen et al. train an MPNN with DDQN to order variables in backtracking. It explores fewer search nodes than MinDom, Dom/Ddeg and Impact but is noticeably slower, a trade-off also seen with Yolcu et al. versus WalkSAT and Amizadeh et al. versus Glucose.
  • The authors are Zou Yue, Lai Jia-Yang and Zhang Yong-Gang of Jilin University, with support from NSFC grants 62076108 and 61872159.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Linguistics & languages · Natural language processing

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.13328/j.cnki.jos.006844

@article{2023,
  title = {{基于学习-推理的约束求解方法研究进展}},
  author = {邹悦 and 赖家洋 and 张永刚},
  journal = {软件学报 (Journal of Software)},
  year = {2023},
  doi = {10.13328/j.cnki.jos.006844},
  url = {https://doi.org/10.13328/j.cnki.jos.006844}
}

References

94 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Gent IP. Principles and Practice of Constraint Programming—CP 2009. Berlin: Springer, 2009. [doi: 10.1007/978-3-642-04244-7] — [doi:10.1007/978-3-642-04244-7](https://doi.org/10.1007/978-3-642-04244-7) find
  2. Nguyen S, Zhang MJ, Johnston M, Tan KC. Automatic programming via iterated local search for dynamic job shop scheduling. IEEE Trans. on Cybernetics, 2015, 45(1): 1–14. [doi: 10.1109/TCYB.2014.2317488] — [doi:10.1109/tcyb.2014.2317488](https://doi.org/10.1109/tcyb.2014.2317488) find
  3. Song W, Kang DH, Zhang J, Xi H. Proactive project scheduling with time-dependent workability uncertainty. In: Proc. of the 16th Conf. on Autonomous Agents and Multiagent Systems. São Paulo: Int ’l Foundation for Autonomous Agents and Multiagent Systems, 2017. 221–229. find
  4. Berbeglia G, Cordeau JF, Laporte G. A hybrid tabu search and constraint programming algorithm for the dynamic dial-a-ride problem. INFORMS Journal on Computing, 2012, 24(3): 343–355. [doi: 10.1287/ijoc.1110.0454] — [doi:10.1287/ijoc.1110.0454](https://doi.org/10.1287/ijoc.1110.0454) find
  5. Tang K, Wang J, Li XD, Yao X. A scalable approach to capacitated arc routing problems based on hierarchical decomposition. IEEE Trans. on Cybernetics, 2017, 47(11): 3928–3940. [doi: 10.1109/TCYB.2016.2590558] — [doi:10.1109/tcyb.2016.2590558](https://doi.org/10.1109/tcyb.2016.2590558) find
  6. Ginsberg ML. Dynamic backtracking. Journal of Artificial Intelligence Research, 1993, 1(1): 25–46. find
  7. Dib M. Tabu-NG: Hybridization of constraint programming and local search for solving CSP [Ph.D. Thesis]. Franch: Université de Technologie de Belfort-Montbeliard, 2010. find
  8. Liberatore P. On the complexity of choosing the branching literal in DPLL. Artificial Intelligence, 2000, 116(1–2): 315–326. [doi: 10.1016/S0004-3702(99)00097-1] — [doi:10.1016/s0004-3702(99)00097-1](https://doi.org/10.1016/s0004-3702%2899%2900097-1) find
  9. van Beek P. Backtracking search algorithms. Foundations of Artificial Intelligence, 2006, 2: 85–134. [doi: 10.1016/S1574-6526(06)80008-8] — [doi:10.1016/s1574-6526(06)80008-8](https://doi.org/10.1016/s1574-6526%2806%2980008-8) find
  10. Dai WZ, Xu QL, Yu Y, Zhou ZH. Bridging machine learning and logical reasoning by abductive learning. In: Proc. of the 33rd Int ’l Conf. on Neural Information Processing Systems. Vancouver: Curran Associates Inc., 2019. 253. find
  11. Zhou ZH, Huang YX. Abductive learning. In: Hitzler P, Sarker K, eds. Neuro-symbolic Artificial Intelligence: The State of the Art. IOP Press, 2021. 353–369. [doi: 10.3233/FAIA210363] — [doi:10.3233/faia210363](https://doi.org/10.3233/faia210363) find
  12. Huang YX, Dai WZ, Yang J, Cai LW, Cheng SF, Huang RZ, Li YF, Zhou ZH. Semi-supervised abductive learning and its application to theft judicial sentencing. In: Proc. of the 2020 IEEE Int ’l Conf. on Data Mining. Sorrento: IEEE, 2020. 1070 –1075. [doi: 10.1109/ICDM50108.2020.00127] — [doi:10.1109/icdm50108.2020.00127](https://doi.org/10.1109/icdm50108.2020.00127) find
  13. Selsam D, Lamm M, Bünz B, Liang P, de Moura L, Dill DL. Learning a SAT solver from single-bit supervision. In: Proc. of the 7th Int’l Conf. on Learning Representations. New Orleans: ICLR, 2018. find
  14. Bello I, Pham H, Le QV, Norouzi M, Bengio S. Neural combinatorial optimization with reinforcement learning. In: Proc. of the 5th Int’l Conf. on Learning Representations. Toulon: ICLR, 2016. find
  15. Wang PW, Donti PL, Wilder B, Kolter Z. SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In: Proc. of the 36th Int’l Conf. on Machine Learning. Long Beach: ICML, 2019. 6545–6554. find
  16. Brouard C, de Givry S, Schiex T. Pushing data into CP models using graphical model learning and solving. In: Proc. of the 26th Int’l Conf. on Principles and Practice of Constraint Programming. Louvain-la-Neuve: Springer, 2020. 811 –827. [doi: 10.1007/978-3-030-58475-7_47] — [doi:10.1007/978-3-030-58475-7_47](https://doi.org/10.1007/978-3-030-58475-7_47) find
  17. Jensen TR, Toft B. Graph Coloring Problems. New York: John Wiley & Sons, 2011. 1–320. [doi: 10.1002/9781118032497] — [doi:10.1002/9781118032497](https://doi.org/10.1002/9781118032497) find
  18. Cook SA. The complexity of theorem-proving procedures. In: Proc. of the 3rd Annual ACM Symp. on Theory of Computing. Shaker Heights: ACM, 1971. 151–158. [doi: 10.1145/800157.805047] find
  19. Bellman R. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 1962, 9(1): 61–63. [doi: 10.1145/321105.321111] — [doi:10.1145/321105.321111](https://doi.org/10.1145/321105.321111) find
  20. Dorigo M, Gambardella LM. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans. on Evolutionary Computation, 1997, 1(1): 53–66. [doi: 10.1109/4235.585892] — [doi:10.1109/4235.585892](https://doi.org/10.1109/4235.585892) find
  21. Sun JG, Zhu XJ, Zhang YG, Li Y. An approach of solving constraint satisfaction problem based on preprocessing. Chinese Journal of Computers, 2008, 31(6): 919–926 (in Chinese with English abstract). [doi: 10.3321/j.issn:0254-4164.2008.06.004] — [doi:10.3321/j.issn:0254-4164.2008.06.004](https://doi.org/10.3321/j.issn:0254-4164.2008.06.004) find
  22. Dechter R. Constraint Processing. Amsterdam: Elsevier, 2003. 1–481. [doi: 10.1016/B978-1-55860-890-0.X5000-2] — [doi:10.1016/b978-1-55860-890-0.x5000-2](https://doi.org/10.1016/b978-1-55860-890-0.x5000-2) find
  23. Bessiere C. Constraint propagation. In: Rossi F, van Beek P, Walsh T, eds. Handbook of Constraint Programming. Amsterdam: Elsevier, 2006. 29–83. find
  24. Zhu XJ, Sun JG, Zhang YG, Li Y. A new preprocessing technique based on entirety singleton consistency. Acta Automatica Sinica, 2009, 35(1): 71–76 (in Chinese with English abstract). [doi: 10.3724/SP.J.1004.2009.00071] — [doi:10.3724/sp.j.1004.2009.00071](https://doi.org/10.3724/sp.j.1004.2009.00071) find
  25. Applegate D, Bixby R, Chvatal V, Cook W. Concorde TSP solver. 2006. http://www.math.uwaterloo.ca/tsp/concorde/m ↗
  26. Gori M, Monfardini G, Scarselli F. A new model for learning in graph domains. In: Proc. of the 2005 IEEE Int’l Joint Conf. on Neural Networks. Montreal: IEEE, 2005. 729–734. [doi: 10.1109/IJCNN.2005.1555942] — [doi:10.1109/ijcnn.2005.1555942](https://doi.org/10.1109/ijcnn.2005.1555942) find
  27. Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE. Neural message passing for quantum chemistry. In: Proc. of the 34th Int’l Conf. on Machine Learning. Sydney: ICML, 2017. 1263–1272. find our card
  28. Liu MH, Zhang F, Huang P, Niu SZ, Ma FF, Zhang J. Learning the satisfiability of pseudo-Boolean problem with graph neural networks. In: Proc. of the 26th Int’l Conf. on Principles and Practice of Constraint Programming. Louvain-la-Neuve: Springer, 2020. 885–898. [doi: 10.1007/978-3-030-58475-7_51] — [doi:10.1007/978-3-030-58475-7_51](https://doi.org/10.1007/978-3-030-58475-7_51) find
  29. Lemos H, Prates M, Avelar P, Lamb L. Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems. In: Proc. of the 31st IEEE Int ’l Conf. on Tools with Artificial Intelligence. Portland: IEEE, 2019. 879 –885. [doi: 10.1109/ICTAI.2019.00125] — [doi:10.1109/ictai.2019.00125](https://doi.org/10.1109/ictai.2019.00125) find
  30. Cameron C, Chen R, Hartford J, Leyton-Brown K. Predicting propositional satisfiability via end-to-end learning. In: Proc. of the 34th AAAI Conf. on Artificial Intelligence. New York: IEEE, 2020. 3324–3331. [doi: 10.1609/aaai.v34i04.5733] — [doi:10.1609/aaai.v34i04.5733](https://doi.org/10.1609/aaai.v34i04.5733) find
  31. Tönshoff J, Ritzert M, Wolf H, Grohe M. Graph neural networks for maximum constraint satisfaction. Frontiers in Artificial Intelligence, 2021, 3: 580607. [doi: 10.3389/frai.2020.580607] — [doi:10.3389/frai.2020.580607](https://doi.org/10.3389/frai.2020.580607) find
  32. Amizadeh S, Matusevych S, Weimer M. PDP: A general neural framework for learning constraint satisfaction solvers. arXiv:1903.01969, 2019. — [arXiv:1903.01969](https://arxiv.org/abs/1903.01969) find
  33. Abboud R, Ceylan I, Lukasiewicz T. Learning to reason: Leveraging neural networks for approximate DNF counting. In: Proc. of the 34th AAAI Conf. on Artificial Intelligence. New York: IEEE, 2019. 3097–3104. [doi: 10.1609/aaai.v34i04.5705] — [doi:10.1609/aaai.v34i04.5705](https://doi.org/10.1609/aaai.v34i04.5705) find
  34. Jaszczur S, Łuszczyk M, Michalewski H. Neural heuristics for SAT solving. arXiv:2005.13406, 2020. — [arXiv:2005.13406](https://arxiv.org/abs/2005.13406) find
  35. Yolcu E, Póczos B. Learning local search heuristics for boolean satisfiability. In: Proc. of the 33rd Int ’l Conf. on Neural Information Processing Systems. Vancouver: Curran Associates Inc., 2019. 718. find
  36. Kurin V, Godil S, Whiteson S, Catanzaro B. Can Q-learning with graph networks learn a generalizable branching heuristic for a SAT solver? In: Proc. of the 34th Int’l Conf. on Neural Information Processing Systems. Vancouver: Curran Associates Inc., 2020. 9608–9621. find
  37. Wen S, Cao ZG, Zhang J, Xu C, Lim A. Learning variable ordering heuristics for solving constraint satisfaction problems. Engineering Applications of Artificial Intelligence, 2022, 109: 104603. [doi: 10.1016/j.engappai.2021.104603] — [doi:10.1016/j.engappai.2021.104603](https://doi.org/10.1016/j.engappai.2021.104603) find
  38. Bünz B, Lamm M. Graph neural networks and Boolean satisfiability. arXiv:1702.03592, 2017. — [arXiv:1702.03592](https://arxiv.org/abs/1702.03592) find
  39. Hochreite S, Schmidhuber J. Long short-term memory. Neural Computation, 1997, 9(8): 1735–1780. [doi: 10.1162/neco.1997.9.8.1735] find
  40. Hertz A, de Werra D. Using tabu search techniques for graph coloring. Computing, 1987, 39(4): 345–351. [doi: 10.1007/BF02239976] — [doi:10.1007/bf02239976](https://doi.org/10.1007/bf02239976) find
  41. Berg J, Demirović E, Stuckey PJ. Core-boosted linear search for incomplete MaxSAT. In: Proc. of the 16th Int’l Conf. on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Thessaloniki: Springer, 2019. 39–56. [doi: 10.1007/978-3-030-19212-9_3] — [doi:10.1007/978-3-030-19212-9_3](https://doi.org/10.1007/978-3-030-19212-9_3) find
  42. Selman B, Kautz H, Cohen B. Local search strategies for satisfiability testing. Cliques, Coloring, and Satisfiability, 1996, 26: 521–531. find
  43. Hoos HH. An adaptive noise mechanism for WalkSAT. In: Proc. of the18th Conf. on Artificial Intelligence (AAAI 2002). Alberta: AAAI. 2002. 655–660. find
  44. Boettcher S, Percus AG. Extremal optimization for graph partitioning. Physical Review E, 2001, 64(2): 026114. [doi: 10.1103/PhysRevE.64.026114] — [doi:10.1103/physreve.64.026114](https://doi.org/10.1103/physreve.64.026114) find
  45. Montanari A, Ricci-Tersenghi F, Semerjian G. Solving constraint satisfaction problems through belief propagation-guided decimation. arXiv:0709.1667, 2007. — [arXiv:0709.1667](https://arxiv.org/abs/0709.1667) find
  46. Audemard G, Simon L. On the glucose SAT solver. Int’l Journal on Artificial Intelligence Tools, 2018, 27(1): 1840001. [doi: 10.1142/S0218213018400018] — [doi:10.1142/s0218213018400018](https://doi.org/10.1142/s0218213018400018) find
  47. Gent IP, MacIntyre E, Presser P, Smith BM, Walsh T. An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem. In: Proc. of the 2nd Int’l Conf. on Principles and Practice of Constraint Programming. Cambridge: Springer, 1996. 179–193. [doi: 10.1007/3-540-61551… — [doi:10.1007/3-540-61551-2_74](https://doi.org/10.1007/3-540-61551-2_74) find
  48. Marques-Silva J. The impact of branching heuristics in propositional satisfiability algorithms. In: Proc. of the 9th Portuguese Conf. on Artificial Intelligence. Evora: Springer, 1999. 62–74. [doi: 10.1007/3-540-48159-1_5] — [doi:10.1007/3-540-48159-1_5](https://doi.org/10.1007/3-540-48159-1_5) find
  49. Krizhevsky A, Sutskever I, Hinton GE. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 2017, 60(6): 84–90. [doi: 10.1145/3065386] — [doi:10.1145/3065386](https://doi.org/10.1145/3065386) find
  50. Silver D, Hubert T, Schrittwieser J, Antonoglou I, Lai M, Guez A, Lanctot M, Sifre L, Kumaran D, Graepel T, Lillicrap T, Simonyan K, Hassabis D. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 2018, 362(6419): 1140–1144. [doi: 10.1126/science.… — [doi:10.1126/science.aar6404](https://doi.org/10.1126/science.aar6404) find
  51. Zhang B, Zhu J, Su H. Toward the third generation of artificial intelligence. Scientia Sinica Informationis, 2020, 50(9): 1281–1302 (in Chinese with English abstract). [doi: 10.1360/SSI-2020-0204] — [doi:10.1360/ssi-2020-0204](https://doi.org/10.1360/ssi-2020-0204) find
  52. Veličković P, Cucurull G, Casanova A, Romero A, Liò P, Bengio Y. Graph attention networks. arXiv:1710.10903, 2017. find our card
  53. Kaelbling LP, Littman ML, Moore AW. Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 1996(4): 237–285. [doi: 10.1613/jair.301] — [doi:10.1613/jair.301](https://doi.org/10.1613/jair.301) find
  54. Lagoudakis M G, Littman M L. Learning to select branching rules in the DPLL procedure for satisfiability. Electronic Notes in Discrete Mathematics, 2001, 9: 344–359. [doi: 10.1016/S1571-0653(04)00332-4] — [doi:10.1016/s1571-0653(04)00332-4](https://doi.org/10.1016/s1571-0653%2804%2900332-4) find
  55. Liang JH, Ganesh V, Poupart P, Czarnecki K. Learning rate based branching heuristic for SAT solvers. In: Proc. of the 19th Int’l Conf. on Theory and Applications of Satisfiability Testing. Bordeaux: Springer, 2016. 123–140. [doi: 10.1007/978-3-319-40970-2_9] — [doi:10.1007/978-3-319-40970-2_9](https://doi.org/10.1007/978-3-319-40970-2_9) find
  56. Bayardo RJ Jr, Schrag R. Using CSP look-back techniques to solve real-world SAT instances. In: Proc. of the 14th National Conf. on Artificial Intelligence and the 9th Conf. on Innovative Applications of Artificial Intelligence. Providence: AAAI Press, 1997. 203–208. find
  57. Marques-Silva JP, Sakallah KA. GRASP: A search algorithm for propositional satisfiability. IEEE Trans. on Computers, 1999, 48(5): 506–521. [doi: 10.1109/12.769433] — [doi:10.1109/12.769433](https://doi.org/10.1109/12.769433) find
  58. Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, Riedmiller M, Fidjeland AK, Ostrovski G, Petersen S, Beattie C, Sadik A, Antonoglou I, King H, Kumaran D, Wierstra D, Legg S, Hassabis D. Human-level control through deep reinforcement learning. Nature, 2015, 518(7540): 529–… find
  59. Moskewicz MW, Madigan CF, Zhao Y, Zhang LT, Malik S. Chaff: Engineering an efficient SAT solver. In: Proc. of the 38th Design Automation Conf. Las Vegas: IEEE, 2001. 530–535. [doi: 10.1145/378239.379017] find
  60. van Hasselt H, Guez A, Silver D. Deep reinforcement learning with double Q-learning. In: Proc. of the 30th AAAI Conf. on Artificial Intelligence. Phoenix: AAAI, 2016. 2094–2100. find
  61. Haralick RM, Elliott Gl. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 1980, 14(3): 263–313. [doi: 10.1016/0004-3702(80)90051-X] — [doi:10.1016/0004-3702(80)90051-x](https://doi.org/10.1016/0004-3702%2880%2990051-x) find
  62. Bessière C, Régin JC. MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems. In: Proc. of the 2nd Int’l Conf. on Principles and Practice of Constraint Programming. Cambridge: Springer, 1996. 61–75. [doi: 10.1007/3-540-61551-2_66] — [doi:10.1007/3-540-61551-2_66](https://doi.org/10.1007/3-540-61551-2_66) find
  63. Refalo P. Impact-based search strategies for constraint programming. In: Proc. of the 10th Int ’l Conf. on Principles and Practice of Constraint Programming. Toronto: Springer, 2004. 557–571. [doi: 10.1007/978-3-540-30201-8_41] — [doi:10.1007/978-3-540-30201-8_41](https://doi.org/10.1007/978-3-540-30201-8_41) find
  64. Sutskever I, Vinyals O, Le OV. Sequence to sequence learning with neural networks. In: Proc. of the 27th Int ’l Conf. on Neural Information Processing Systems. Montreal: MIT Press, 2014. 3104–3112. find
  65. Vinyals O, Fortunato M, Jaitly N. Pointer networks. In: Proc. of the 28th Int’l Conf. on Neural Information Processing Systems. Montreal: MIT Press, 2015. 2692–2700. find
  66. Bahdanau D, Cho K, Bengio Y. Neural machine translation by jointly learning to align and translate. In: Proc. of the 3rd Int’l Conf. on Learning Representations. San Diego: ICLR, 2015. 1–14. [doi: 10.48550/arXiv.1409.0473] find our card
  67. Papadimitriou CH. The euclidean travelling salesman problem is NP-complete. Theoretical Computer Science, 1977, 4(3): 237–244. [doi: 10.1016/0304-3975(77)90012-3] — [doi:10.1016/0304-3975(77)90012-3](https://doi.org/10.1016/0304-3975%2877%2990012-3) find
  68. Nazari M, Oroojlooy A, Takáč M, Snyder LV. Reinforcement learning for solving the vehicle routing problem. In: Proc. of the 32nd Int’l Conf. on Neural Information Processing Systems. Montréal: Curran Associates Inc., 2018. 9861–9871. find
  69. Deudon M, Cournut P, Lacoste A, Adulyasak Y, Rousseau LM. Learning heuristics for the TSP by policy gradient. In: Proc. of the 15th Int’l Conf. on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Delft: Springer, 2018. 170–181. [doi: 10.1007/978-3-319-93031-2_… — [doi:10.1007/978-3-319-93031-2_12](https://doi.org/10.1007/978-3-319-93031-2_12) find
  70. Kool W, van Hoof H, Welling M. Attention, learn to solve routing problems! In: Proc. of the 7th Int’l Conf. on Learning Representations. New Orleans: ICLR, 2019. 1–25. find
  71. Ma Q, Ge SW, He DY, Thaker D, Drori I. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv:1911.04936, 2019. — [arXiv:1911.04936](https://arxiv.org/abs/1911.04936) find
  72. Wu YX, Song W, Cao ZG, Zhang J, Lim A. Learning improvement heuristics for solving routing problems. IEEE Trans. on Neural Networks and Learning Systems, 2022, 33(9): 5057–5069. [doi: 10.1109/TNNLS.2021.3068828] — [doi:10.1109/tnnls.2021.3068828](https://doi.org/10.1109/tnnls.2021.3068828) find
  73. Mnih V, Badia AP, Mirza M, Graves A, Lillicrap T, Harley T, Silver D, Kavukcuoglu K. Asynchronous methods for deep reinforcement learning. In: Proc. of the 33rd Int’l Conf. on Machine Learning. New York City: PMLR, 2016. 1928–1937. find
  74. Williams RJ. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 1992, 8(3): 229–256. [doi: 10.1007/BF00992696] find
  75. Perron L, Furnon V. Or-tools. 2022. https://developers.google.com/optimization/ ↗
  76. Helsgaun K. General k-opt submoves for the lin-kernighan TSP heuristic. Mathematical Programming Computation, 2009, 1(2 –3): 119–163. [doi: 10.1007/s12532-009-0004-6] — [doi:10.1007/s12532-009-0004-6](https://doi.org/10.1007/s12532-009-0004-6) find
  77. Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez AN, Kaiser Ł, Polosukhin I. Attention is all you need. In: Proc. of the 31st Int’l Conf. on Neural Information Processing Systems. Long Beach: Curran Associates Inc., 2017. 6000–6010. find
  78. Ribeiro LFR, Saverese PHP, Figueiredo DR. struc2vec: Learning node representations from structural identity. In: Proc. of the 23rd ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Halifax: ACM, 2017. 385–394. [doi: 10.1145/3097983.3098061] — [doi:10.1145/3097983.3098061](https://doi.org/10.1145/3097983.3098061) find
  79. Scarselli F, Gori M, Tsoi AC, Hagenbuchner M, Monfardini G. The graph neural network model. IEEE Trans. on Neural Networks, 2009, 20(1): 61–80. [doi: 10.1109/TNN.2008.2005605] — [doi:10.1109/tnn.2008.2005605](https://doi.org/10.1109/tnn.2008.2005605) find
  80. Battaglia PW, Hamrick JB, Bapst V, et al. Relational inductive biases, deep learning, and graph networks. arXiv:1806.01261, 2018. find our card
  81. Haarnoja T, Zhou A, Abbeel P, Levine S. Soft Actor-Critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In: Proc. of the 35th Int’l Conf. on Machine Learning. Stockholm: ICML, 2018. 1861–1870. find
  82. Wang PW, Chang WC, Kolter JZ. The mixing method: Low-rank coordinate descent for semidefinite programming with diagonal constraints. arXiv:1706.00476, 2017. — [arXiv:1706.00476](https://arxiv.org/abs/1706.00476) find
  83. Shalev-Shwartz S, Shamir O, Shammah S. Failures of gradient-based deep learning. In: Proc. of the 34th Int ’l Conf. on Machine Learning. Sydney: ICML, 2017. 3067–3075. find
  84. LeCun Y, Bottou L, Bengio Y, Haffner P. Gradient-based learning applied to document recognition. Proc. of the IEEE, 1998, 86(11): 2278–2324. [doi: 10.1109/5.726791] find
  85. Park Y, Hallac D, Boyd S, Leskovec J. Learning the network structure of heterogeneous data via pairwise exponential Markov random fields. In: Proc. of the 20th Int’l Conf. on Artificial Intelligence and Statistics. Fort Lauderdale: AISTATS, 2017. 1302–1310. find
  86. Palm RB, Paquet U, Winther O. Recurrent relational networks. In: Proc. of the 32nd Int ’l Conf. on Neural Information Processing Systems. Montréal: Curran Associates Inc., 2018. 3372–3382. find
  87. Kumar M, Kolb S, Teso S, De Raedt L. Learning MAX-SAT from contextual examples for combinatorial optimisation. Artificial Intelligence, 2023, 314: 103794. [doi: 10.1016/j.artint.2022.103794] — [doi:10.1016/j.artint.2022.103794](https://doi.org/10.1016/j.artint.2022.103794) find
  88. Bessiere C, Daoudi A, Hebrard E, Katsirelos G, Lazaar N, Mechqrane Y, Narodytska N, Quimper CG, Walsh T. New approaches to constraint acquisition. In: Bessiere C, De Raedt L, Kotthoff L, Nijssen S, O'Sullivan B, Pedreschi D, eds. Data Mining and Constraint Programming. Cham: Springer, 2016. 51–76. [… — [doi:10.1007/978-3-319-50137-6_3](https://doi.org/10.1007/978-3-319-50137-6_3) find
  89. Zhang WJ, Sun ZY, Zhu QH, Li G, Cai SW, Xiong YF, Zhang L. NLocalSAT: Boosting local search with solution prediction. In: Proc. of the 29th Int’l Joint Conf. on Artificial Intelligence. Yokohama: IJCAI, 2020. 1177–1183. [doi: 10.24963/ijcai.2020/164] — [doi:10.24963/ijcai.2020/164](https://doi.org/10.24963/ijcai.2020/164) find
  90. Dudek JM, Vardi MY. Parallel weighted model counting with tensor networks. arXiv:2006.15512, 2020. find
  91. Jiang Y, Wu YX, Cao ZG, Zhang J. Learning to solve routing problems via distributionally robust optimization. In: Proc. of the 36th AAAI Conf. on Artificial Intelligence. AAAI, 2022. 9786–9794. [doi: 10.1609/aaai.v36i9.21214] — [doi:10.1609/aaai.v36i9.21214](https://doi.org/10.1609/aaai.v36i9.21214) find
  92. Yu TS, Wang RZ, Yan JC, Li BX. Deep latent graph matching. In: Proc. of the 38th Int ’l Conf. on Machine Learning. ICML, 2021. 12187–12197. find
  93. Skryagin A, Stammer W, Ochs D, Dhami DS, Kersting K. Neural-probabilistic answer set programming. In: Proc. of the 19th Int’l Conf. on Principles of Knowledge Representation and Reasoning. Haifa: KR, 2022. 463–473. [doi: 10.24963/kr.2022/48] — [doi:10.24963/kr.2022/48](https://doi.org/10.24963/kr.2022/48) find
  94. Popescu A, Polat-Erdeniz S, Felfernig A, Uta M, Atas M, Le VM, Pilsl K, Enzelsberger M, Tran TNT. An overview of machine learning techniques in constraint solving. Journal of Intelligent Information Systems, 2022, 58(1): 91–118. [doi: 10.1007/s10844-021-00666-5] 附中文参考文献: [21] 孙吉贵, 朱兴军, 张永刚, 李莹. 一种基于… — [doi:10.1007/s10844-021-00666-5](https://doi.org/10.1007/s10844-021-00666-5) find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/zou-2023-methods-constraint-solving/