Skip to content

Latest commit

 

History

History
484 lines (261 loc) · 25.7 KB

README.md

File metadata and controls

484 lines (261 loc) · 25.7 KB
Raw

Awesome Machine Learning for Combinatorial Optimization Resources

We would like to maintain a list of resources that utilize machine learning technologies to solve combinatorial optimization problems.

We mark work contributed by Thinklab with ✨.

Maintained by members in SJTU-Thinklab: Chang Liu, Runzhong Wang, Jiayi Zhang, Zelin Zhao, Haoyu Geng, Tianzhe Wang, Wenxuan Guo, and Junchi Yan.

We are looking for post-docs interested in machine learning especially for learning combinatorial solvers, dynamic graphs, and reinforcement learning. Please send your up-to-date resume via yanjunchi AT sjtu.edu.cn.

Content

1. Survey
2. Problems
 2.1 Graph Matching (GM)  2.2 Quadratic Assignment Problem (QAP)
 2.3 Travelling Salesman Problem (TSP)  2.4 Maximal Cut
 2.5 Vehicle Routing Problem (VRP)  2.6 Computing Resource Allocation
 2.7 Job Shop Scheduling (JSP)  2.8 Bin Packing Problem (BPP)
 2.9 Graph Edit Distance (GED)  2.10 Graph Coloring
 2.11 Maximal Common Subgraph (MCS)  2.12 Influence Maximization
 2.13 Maximal Independent Set (MIS)  2.14 Mixed Integer Programming
 2.15 Causal Discovery  2.16 Game Theoretic Semantics
 2.17 Boolean Satisfiability (SAT)  2.18 Differentiable Optimization
 2.19 Car Dispatch  

Survey Papers

  1. A Survey of Reinforcement Learning and Agent-Based Approaches to Combinatorial Optimization. INFORMS Journal on Computing, 1999. journal

    Smith, Kate A.

  2. Model-Based Search for Combinatorial Optimization: A Critical Survey. Annals of Operations Research, 2004. journal

    Zlochin, Mark and Birattari, Mauro and Meuleau, Nicolas and Dorigo, Marco.

  3. Machine Learning Approaches to Learning Heuristics for Combinatorial Optimization Problems. Procedia Manufacturing, 2018. journal

    Mirshekarian, Sadegh and Sormaz, Dusan.

  4. Boosting combinatorial problem modeling with machine learning. IJCAI, 2018. paper

    Lombardi, Michele and Milano, Michela.

  5. A Review of combinatorial optimization with graph neural networks. BigDIA, 2019. paper

    Huang, Tingfei and Ma, Yang and Zhou, Yuzhen and Huang, Honglan Huang and Chen, Dongmei and Gong, Zidan and Liu, Yao.

  6. Machine Learning for Combinatorial Optimization: a Methodological Tour d'horizon. EJOR, 2020. journal

    Bengio, Yoshua and Lodi, Andrea and Prouvost, Antoine.

  7. Reinforcement Learning for Combinatorial Optimization: A Survey. Arxiv, 2020. paper

    Mazyavkina, Nina and Sviridov, Sergey and Ivanov, Sergei and Burnaev, Evgeny.

  8. ✨Learning Graph Matching and Related Combinatorial Optimization Problems. IJCAI, 2020. paper

    Yan, Junchi and Yang, Shuang, and Hancock, Edwin R.

  9. Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking. IEEE ACCESS, 2020. journal

    Vesselinova, Natalia and Steinert, Rebecca and Perez-Ramirez, Daniel F. and Boman, Magnus.

  10. From Shallow to Deep Interactions Between Knowledge Representation, Reasoning and Machine Learning. Arxiv, 2020. paper

    Bouraoui, Zied and Cornuéjols, Antoine and Denœux, Thierry and Destercke, Sébastien and Dubois, Didier and Guillaume, Romain and Marques-Silva, João and Mengin, Jérôme and Prade, Henri and Schockaert, Steven and Serrurier, Mathieu and Vrain, Christel.

  11. A Survey on Reinforcement Learning for Combinatorial Optimization. Arxiv, 2020. paper

    Yang, Yunhao and Whinston, Andrew.

Problems

Graph Matching

  1. Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks Arxiv, 2017. paper, code

    Nowak, Alex and Villar, Soledad and Bandeira, S. Afonso and Bruna, Joan

  2. Deep Learning of Graph Matching. CVPR, 2018. paper

    Zanfir, Andrei and Sminchisescu, Cristian

  3. ✨Learning Combinatorial Embedding Networks for Deep Graph Matching. ICCV, 2019. paper, code

    Wang, Runzhong and Yan, Junchi and Yang, Xiaokang

  4. Deep Graphical Feature Learning for the Feature Matching Problem. ICCV, 2019. paper

    Zhang, Zhen and Lee, Wee Sun

  5. GLMNet: Graph Learning-Matching Networks for Feature Matching. Arxiv, 2019. paper

    Jiang, Bo and Sun, Pengfei and Tang, Jin and Luo, Bin

  6. ✨Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching. Arxiv, 2019. paper

    Wang, Runzhong and Yan, Junchi and Yang, Xiaokang

  7. ✨Learning deep graph matching with channel-independent embedding and Hungarian attention. ICLR, 2020. paper

    Yu, Tianshu and Wang, Runzhong and Yan, Junchi and Li, Baoxin

  8. Deep Graph Matching Consensus. ICLR, 2020. paper

    Fey, Matthias and Lenssen, Jan E. and Morris, Christopher and Masci, Jonathan and Kriege, Nils M.

  9. ✨Graduated Assignment for Joint Multi-Graph Matching and Clustering with Application to Unsupervised Graph Matching Network Learning. NeurIPS, 2020. paper

    Wang, Runzhong and Yan, Junchi and Yang, Xiaokang

  10. ✨Combinatorial Learning of Robust Deep Graph Matching: An Embedding Based Approach. TPAMI, 2020. paper

    Wang, Runzhong and Yan, Junchi and Yang, Xiaokang

  11. Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers. ECCV, 2020. paper, code

    Rolinek, Michal and Swoboda, Paul and Zietlow, Dominik and Paulus, Anselm and Musil, Vit and Martius, Georg

  12. ✨Deep Reinforcement Learning of Graph Matching. Arxiv, 2020. paper

    Liu, Chang and Wang, Runzhong and Jiang, Zetian and Yan, Junchi

Quadratic Assignment Problem

  1. Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks Arxiv, 2017. paper, code

    Nowak, Alex and Villar, Soledad and Bandeira, S. Afonso and Bruna, Joan

  2. ✨Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching. Arxiv, 2019. paper

    Wang, Runzhong and Yan, Junchi and Yang, Xiaokang

  3. ✨Deep Reinforcement Learning of Graph Matching. Arxiv, 2020. paper

    Liu, Chang and Wang, Runzhong and Jiang, Zetian and Yan, Junchi

Travelling Salesman Problem

  1. Learning Combinatorial Optimization Algorithms over Graphs. NeurIPS, 2017. paper

    Dai, Hanjun and Khalil, Elias B and Zhang, Yuyu and Dilkina, Bistra and Song, Le

  2. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. NeurIPS, 2018. paper

    Kwon, Yeong-Dae and Choo, Jinho and Kim, Byoungjip and Yoon, Iljoo and Min, Seungjai and Gwon, Youngjune.

  3. Learning Heuristics for the TSP by Policy Gradient CPAIOR, 2018. paper, code

    Michel DeudonPierre CournutAlexandre Lacoste

  4. Attention, Learn to Solve Routing Problems! ICLR, 2019. paper

    Kool, Wouter and Van Hoof, Herke and Welling, Max.

  5. Learning to Solve NP-Complete Problems: A Graph Neural Network for Decision TSP. AAAI, 2019. paper

    Prates, Marcelo and Avelar, Pedro HC and Lemos, Henrique and Lamb, Luis C and Vardi, Moshe Y.

  6. An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem Arxiv, 2019. paper, code

    Chaitanya K. Joshi, Thomas Laurent, Xavier Bresson

  7. Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances Zhang-Hua. Arxiv, 2020. paper

    Fu, Zhang-Hua and Qiu, Kai-Bin and Zha, Hongyuan.

  8. Differentiation of Blackbox Combinatorial Solvers ICLR, 2020. paper, code

    Marin Vlastelica, Anselm Paulus, Vít Musil, Georg Martius, Michal Rolínek

  9. The Transformer Network for the Traveling Salesman Problem IPAM, 2021. paper

    Xavier Bresson，Thomas Laurent

Maximal Cut

  1. Learning Combinatorial Optimization Algorithms over Graphs. NeurIPS, 2017. paper

    Dai, Hanjun and Khalil, Elias B and Zhang, Yuyu and Dilkina, Bistra and Song, Le

  2. Exploratory Combinatorial Optimization with Reinforcement Learning. AAAI, 2020. paper

    LBarrett, Thomas and Clements, William and Foerster, Jakob and Lvovsky, Alex.

  3. Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs. NeurIPS, 2020. paper

    Karalias, Nikolaos and Loukas, Andreas

Vehicle Routing Problem

  1. Learning to Perform Local Rewriting for Combinatorial Optimization. NeurIPS, 2019. paper, code

    Chen, Xinyun and Tian, Yuandong.

  2. Deep Reinforcement Learning for the Electric Vehicle Routing Problem with Time Windows. Arxiv, 2020. paper

    Lin, Bo and Ghaddar, Bissan and Nathwani, Jatin.

  3. A Learning-based Iterative Method for Solving Vehicle Routing Problems ICLR, 2020. paper

    Lu, Hao and Zhang, Xingwen and Yang, Shuang

Computing Resource Allocation

  1. Resource Management with Deep Reinforcement Learning. HotNets, 2016. paper

    Mao, Hongzi and Alizadeh, Mohammad and Menache, Ishai and Kandula, Srikanth.

  2. Learning to Perform Local Rewriting for Combinatorial Optimization. NeurIPS, 2019. paper, code

    Chen, Xinyun and Tian, Yuandong.

  3. Learning Scheduling Algorithms for Data Processing Clusters SIGCOMM, 2019. paper, code

    Mao, Hongzi and Schwarzkopf, Malte and Venkatakrishnan, Bojja Shaileshh and Meng, Zili and Alizadeh, Mohammad.

  4. Smart Resource Allocation for Mobile Edge Computing: A Deep Reinforcement Learning Approach IEEE Transactions on Emerging Topics in Computing, 2019. Paper

    Jiadai; Lei Zhao; Jiajia Liu; Nei Kato

Job Shop Scheduling

  1. Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning. NeurIPS, 2020. paper, code

    Zhang, Cong and Song, Wen and Cao, Zhiguang and Zhang, Jie and Tan, Puay Siew and Xu, Chi.

Bin Packing Problem

  1. Small Boxes Big Data: A Deep Learning Approach to Optimize Variable Sized Bin Packing BigDataService, 2017. paper

    Mao, Feng and Blanco, Edgar and Fu, Mingang and Jain, Rohit and Gupta, Anurag and Mancel, Sebastien and Yuan, Rong and Guo, Stephen and Kumar, Sai and Tian, Yayang

  2. Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method Arxiv, 2017. paper

    Hu, Haoyuan and Zhang, Xiaodong and Yan, Xiaowei and Wang, Longfei and Xu, Yinghui

  3. Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization Alexandre Arxiv, 2018. paper

    Laterre, Alexandre and Fu, Yunguan and Jabri, Mohamed Khalil and Cohen, Alain-Sam and Kas, David and Hajjar, Karl and Dahl, Torbjorn S and Kerkeni, Amine and Beguir, Karim

  4. A Multi-task Selected Learning Approach for Solving 3D Bin Packing Problem. AAMAS, 2019. paper

    Duan, Lu and Hu, Haoyuan and Qian, Yu and Gong, Yu and Zhang, Xiaodong and Xu, Yinghui and Wei, Jiangwen.

  5. A Data-Driven Approach for Multi-level Packing Problems in Manufacturing Industry KDD, 2019. paper

    Chen, Lei and Tong, Xialiang and Yuan, Mingxuan and Zeng, Jia and Chen, Lei

  6. Solving Packing Problems by Conditional Query Learning OpenReview, 2019. paper

    Li, Dongda and Ren, Changwei and Gu, Zhaoquan and Wang, Yuexuan and Lau, Francis

  7. RePack: Dense Object Packing Using Deep CNN with Reinforcement Learning CACS, 2019. paper

    Chu, Yu-Cheng and Lin, Horng-Horng

  8. A Generalized Reinforcement Learning Algorithm for Online 3D Bin-Packing. AAAI Workshop, 2020. paper

    Verma, Richa and Singhal, Aniruddha and Khadilkar, Harshad and Basumatary, Ansuma and Nayak, Siddharth and Singh, Harsh Vardhan and Kumar, Swagat and Sinha, Rajesh.

  9. Robot Packing with Known Items and Nondeterministic Arrival Order. TASAE, 2020. paper

    Wang, Fan and Hauser, Kris.

  10. TAP-Net: Transport-and-Pack using Reinforcement Learning. TOG, 2020. paper, code

    Hu, Ruizhen and Xu, Juzhan and Chen, Bin and Gong, Minglun and Zhang, Hao and Huang, Hui.

  11. Simultaneous Planning for Item Picking and Placing by Deep Reinforcement Learning IROS, 2020. paper

    Tanaka, Tatsuya and Kaneko, Toshimitsu and Sekine, Masahiro and Tangkaratt, Voot and Sugiyama, Masashi

  12. Monte Carlo Tree Search on Perfect Rectangle Packing Problem Instances GECCO, 2020. paper

    Pejic, Igor and van den Berg, Daan

  13. PackIt: A Virtual Environment for Geometric Planning ICML, 2020. paper

    Goyal, Ankit and Deng, Jia

  14. Online 3D Bin Packing with Constrained Deep Reinforcement Learning. AAAI, 2021. paper

    Zhao, Hang and She, Qijin and Zhu, Chenyang and Yang, Yin and Xu, Kai.

Graph Edit Distance

  1. SimGNN - A Neural Network Approach to Fast Graph Similarity Computation WSDM, 2019. paper, code

    Bai, Yunsheng and Ding, Hao and Bian, Song and Chen, Ting and Sun, Yizhou and Wang, Wei

  2. Graph Matching Networks for Learning the Similarity of Graph Structured Objects ICML, 2019. paper

    Li, Yujia and Gu, Chenjie and Dullien, Thomas and Vinyals, Oriol and Kohli, Pushmeet

  3. ✨Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. CVPR, 2021. paper

    Wang, Runzhong and Zhang, Tianqi and Yu, Tianshu and Yan, Junchi and Yang, Xiaokang.

Graph Coloring

  1. Deep Learning-based Hybrid Graph-Coloring Algorithm for Register Allocation. Arxiv, 2019. paper

    Das, Dibyendu and Ahmad, Shahid Asghar and Venkataramanan, Kumar.

Maximal Common Subgraph

  1. Fast Detection of Maximum Common Subgraph via Deep Q-Learning. Arxiv, 2020. paper

    Bai, Yunsheng and Xu, Derek and Wang, Alex and Gu, Ken and Wu, Xueqing and Marinovic, Agustin and Ro, Christopher and Sun, Yizhou and Wang, Wei.

Influence Maximization

  1. Learning Heuristics over Large Graphs via Deep Reinforcement Learning. NeurIPS, 2020. paper

    Mittal, Akash and Dhawan, Anuj and Manchanda, Sahil and Medya, Sourav and Ranu, Sayan and Singh, Ambuj.

Maximal Independent Set

  1. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. NeurIPS, 2018. paper

    Li, Zhuwen and Chen, Qifeng and Koltun, Vladlen.

Mixed Integer Programming

  1. Improving Learning to Branch via Reinforcement Learning. NeurIPS Workshop, 2020. paper

    Sun, Haoran and Chen, Wenbo and Li, Hui and Song, Le.

Causal Discovery

  1. Causal Discovery with Reinforcement Learning. ICLR, 2020. paper

    Zhu, Shengyu and Ng, Ignavier and Chen, Zhitang.

Game Theoretic Semantics

  1. First-Order Problem Solving through Neural MCTS based Reinforcement Learning. Arxiv, 2021. paper

    Xu, Ruiyang and Kadam, Prashank and Lieberherr, Karl.

Boolean Satisfiability

  1. Graph neural networks and boolean satisfiability. Arxiv, 2017. paper

    Bünz, Benedikt, and Matthew Lamm.

  2. Learning a SAT solver from single-bit supervision. Arxiv, 2018. paper, code

    Selsam, Daniel, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill.

  3. Machine learning-based restart policy for CDCL SAT solvers. SAT, 2018. paper

    Liang, Jia Hui, Chanseok Oh, Minu Mathew, Ciza Thomas, Chunxiao Li, and Vijay Ganesh.

  4. Learning to solve circuit-SAT: An unsupervised differentiable approach ICLR, 2019. paper, code

    Amizadeh, Saeed, Sergiy Matusevych, and Markus Weimer.

  5. Learning Local Search Heuristics for Boolean Satisfiability. NeurIPS, 2019. paper, code

    Yolcu, Emre and Poczos, Barnabas

  6. Improving SAT solver heuristics with graph networks and reinforcement learning. Arxiv, 2019. paper

    Kurin, Vitaly, Saad Godil, Shimon Whiteson, and Bryan Catanzaro.

  7. Graph neural reasoning may fail in certifying boolean unsatisfiability Arxiv, 2019. paper

    Chen, Ziliang, and Zhanfu Yang.

  8. Guiding high-performance SAT solvers with unsat-core predictions SAT, 2019. paper

    Selsam, Daniel, and Nikolaj Bjørner.

  9. G2SAT: Learning to Generate SAT Formulas NeurIPS, 2019. paper, code

    You, Jiaxuan, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec.

  10. Learning Heuristics for Quantified Boolean Formulas through Reinforcement Learning Arxiv, 2019. paper, code

    Lederman, Gil, Markus N. Rabe, Edward A. Lee, and Sanjit A. Seshia.

  11. Enhancing SAT solvers with glue variable predictions. Arxiv, 2020. paper

    Han, Jesse Michael.

  12. Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver? NeurIPS, 2020. paper

    Whiteson, Shimon.

  13. Online Bayesian Moment Matching based SAT Solver Heuristics. ICML, 2020. paper, code

    Duan, Haonan, Saeed Nejati, George Trimponias, Pascal Poupart, and Vijay Ganesh.

  14. Learning Clause Deletion Heuristics with Reinforcement Learning. AITP, 2020. paper

    Vaezipoor, Pashootan, Gil Lederman, Yuhuai Wu, Roger Grosse, and Fahiem Bacchus.

  15. Classification of SAT problem instances by machine learning methods. CEUR, 2020. paper

    Danisovszky, Márk, Zijian Győző Yang, and Gábor Kusper.

  16. Predicting Propositional Satisfiability via End-to-End Learning. AAAI, 2020. paper

    Cameron, Chris, Rex Chen, Jason Hartford, and Kevin Leyton-Brown.

  17. Neural heuristics for SAT solving. Arxiv, 2020. paper

    Jaszczur, Sebastian, Michał Łuszczyk, and Henryk Michalewski.

  18. NLocalSAT: Boosting Local Search with Solution Prediction Arxiv, 2020. paper, code

    Zhang, Wenjie, Zeyu Sun, Qihao Zhu, Ge Li, Shaowei Cai, Yingfei Xiong, and Lu Zhang.

Differentiable Optimization

  1. Differentiable Learning of Submodular Models NeurIPS, 2017. paper, code

    Josip Djolonga, Andreas Krause

  2. Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization AAAI, 2019. paper

    Bryan Wilder, Bistra Dilkina, Milind Tambe

  3. MIPaaL: Mixed Integer Program as a Layer AAAI, 2020. paper, code

    Aaron Ferber, Bryan Wilder, Bistra Dilkina, Milind Tambe

  4. Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems AAAI, 2020. paper, code

    Jaynta Mandi, Emir Demirovi, Peter. J Stuckey, Tias Guns

  5. Differentiation of blackbox combinatorial solvers ICLR, 2020. paper, code

    Marin Vlastelica Pogani, Anselm Paulus, Vit Musil, Georg Martius, Michal Rolinek

  6. Interior Point Solving for LP-based prediction+optimization NeurIPS, 2020. paper, code

    Jayanta Mandi, Tias Guns

Car Dispatch

  1. Dispatch of autonomous vehicles for taxi services: A deep reinforcement learning approach Transportation Research, 2020. paper

    Chao Mao, Yulin Liu, Zuo-Jun (Max) Shen