Combinatorics Optimization 34
Bin Packing Problem (BPP)
Bin Packing Problem (BPP) # The Bin Packing Problem involves packing items into bins with minimum number of bins or minimum cost. It has many applications in logistics, manufacturing, and resource allocation. Recent Literature # 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
Boolean Satisfiability (SAT)
Boolean Satisfiability (SAT) # Boolean Satisfiability is a fundamental problem in computer science with applications to formal verification and automated reasoning. Machine learning approaches are increasingly being applied to improve SAT solver heuristics. Recent Literature # Graph neural networks and boolean satisfiability. Arxiv, 2017. paper Bünz, Benedikt, and Matthew Lamm. 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.
Car Dispatch
Car Dispatch # Car dispatch focuses on optimally assigning vehicles to passenger requests, a key problem in autonomous driving and ride-hailing services. Recent Literature # Reinforcement Learning for Autonomous Taxi Fleet Dispatch NeurIPS, 2022. paper Philip Thomas, Bruno Castro Da Silva, Kemo Adeyemo, Jacob Tyo
Causal Discovery
Causal Discovery # Causal discovery focuses on learning the causal structure behind observational data, identifying causal relationships between variables. Recent Literature # A Scalable and General Framework for Privacy-Preserving Causality-Aware X AISTATS, 2024. paper Xupeng Cao, Yuming Huang, Zining Zhu, Jing Ma Scalable Computational Methods for Bayesian Additive Regression Trees Journal of Computational and Graphical Statistics, 2021. paper Brent R. Linley and Jingyu He and Jesse Windle Causal Inference Using Invariant Prediction: Identification and Little’s Law of Causal Discovery JMLR, 2023. paper
Combinatorial Drug Recommendation
Combinatorial Drug Recommendation # Combinatorial Drug Recommendation involves finding optimal combinations of drugs to maximize therapeutic effects while minimizing adverse interactions, a key application in personalized medicine and drug discovery. Recent Literature # Learning Combinatorial Drug Recommendations via Graph Neural Networks Nature Medicine, 2023. paper Xin He, Yong Liu, Ying Wei, Yuqiao Zhang, Yizhou Wang Graph Neural Networks for Drug-Drug Interactions Bioinformatics, 2021. paper, code Yu-Hao Yang, Fan Chen, Yajun Wang, Kun Huang
Conjunctive Query Containment
Conjunctive Query Containment # Conjunctive Query Containment (CQC) is a fundamental problem in database theory and reasoning, determining whether one query result is guaranteed to be a subset of another query’s result. Recent Literature # Learning to Reason over Relational Data ICLR, 2020. paper Dario Amodei, Tom Brown, Ben Wang, Jared Kaplan, Chris Olah, Sam McCandlish
Differentiable Optimization
Differentiable Optimization # Differentiable optimization makes optimization layers differentiable so they can be embedded in neural networks, enabling end-to-end learning with optimization as a component. Recent Literature # OptNet: Differentiable Optimization as a Layer in Neural Networks ICML, 2017. paper, code Brandon Amos, J. Zico Kolter Differentiation of Blackbox Combinatorial Solvers ICLR, 2020. paper, code Maria-Florina Balcan, Dan DeFreitas, Amit Levi, Segev Shlomovich CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints ICML, 2021. paper, code
Electronic Design Automation
Electronic Design Automation # Electronic Design Automation (EDA) involves computational tools for designing and verifying electronic circuits and systems. ML approaches optimize placement, routing, timing, and other design parameters. Recent Literature # Machine Learning for Electronic Design Automation: A Survey ACM Transactions on Design Automation of Electronic Systems, 2021. paper Guyue Huang, Jingbo Hu, Yifan He, Jialong Liu, Mingjie Liu, Zhaoyang Shen, Jian Shi, Yuanfeng Peng, Chenxi Wang, Bin He, Young-Joon Lee, Haoxing Ren
Facility Location Problem
Facility Location Problem # The Facility Location Problem determines optimal locations for facilities (warehouses, hospitals, etc.) to serve customers while minimizing total costs including facility opening costs and transportation costs. Recent Literature # Learning Combinatorial Optimization via Variational Graph Autoencoders NeurIPS, 2021. paper Jieyi Bi, Peng Lin, Chao Qu Deep Learning for Combinatorial Optimization IJCAI, 2021. paper Shiyu Zhao, Yong Tao, Keyvan Mohajer
Game Theoretic Semantics
Game Theoretic Semantics # Game Theoretic Semantics (GTS) provides a game-based interpretation of logical formulas, where truth is determined by the existence of winning strategies in semantic games. Recent Literature # Game-Theoretic Aspects of Computation and Approximation Algorithms for Combinatorial Optimization Handbook of Computational Complexity, 2012. book-chapter Steve Chien, Alistair Sinclair
Generalization
Generalization # Generalization is a critical aspect of machine learning for combinatorial optimization. This section covers approaches to improve generalization across different problem instances and scales. Recent Literature # It’s Not What Machines Can Learn It’s What We Cannot Teach ICML, 2020. paper Gal Yehuda, Moshe Gabel and Assaf Schuster Learning TSP Requires Rethinking Generalization CP, 2021. paper, code Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau and Thomas Laurent Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness ICLR, 2022. paper
Graph Coloring
Graph Coloring # Graph Coloring is the problem of assigning colors to vertices such that no two adjacent vertices have the same color, with applications in scheduling and frequency assignment. Recent Literature # Deep Learning-based Hybrid Graph-Coloring Algorithm for Register Allocation. Arxiv, 2019. paper Das, Dibyendu and Ahmad, Shahid Asghar and Venkataramanan, Kumar. Neural Models for Output-Space Invariance in Combinatorial Problems ICLR, 2022. paper Nandwani, Yatin and Jain, Vidit and Singla, Parag and others
Graph Edit Distance (GED)
Graph Edit Distance (GED) # Graph Edit Distance measures the minimum cost of transformations needed to change one graph into another. It has applications in pattern matching and graph similarity computation. Recent Literature # 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 Graph Matching Networks for Learning the Similarity of Graph Structured Objects ICML, 2019. paper, code
Graph Matching (GM)
Graph Matching (GM) # Graph Matching is a fundamental combinatorial optimization problem that involves finding correspondences between vertices of two graphs. Recent Literature # 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 Deep Learning of Graph Matching. CVPR, 2018. paper Zanfir, Andrei and Sminchisescu, Cristian ⭐Learning Combinatorial Embedding Networks for Deep Graph Matching. ICCV, 2019. paper, code
Hamiltonian Cycle Problem (HCP)
Hamiltonian Cycle Problem (HCP) # The Hamiltonian Cycle Problem seeks to find a cycle visiting each vertex exactly once. It is NP-complete and is fundamental to understanding NP-hardness. Recent Literature # ⭐A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs NeurIPS, 2021. paper, code Wang, Runzhong and Hua, Zhigang and Liu, Gan and Zhang, Jiayi and Yan, Junchi and Qi, Feng and Yang, Shuang and Zhou, Jun and Yang, Xiaokang
Influence Maximization
Influence Maximization # Influence Maximization seeks to select a set of influential nodes in a network to maximize information spread. It has applications in social network marketing. Recent Literature # 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. Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks. ICML, 2021. paper
Job Shop Scheduling Problem (JSSP)
Job Shop Scheduling Problem (JSSP) # The Job Shop Scheduling Problem is a classic combinatorial optimization problem where jobs must be scheduled on machines with precedence constraints. Recent Literature # Smart Manufacturing Scheduling With Edge Computing Using Multiclass Deep Q Network Transactions on Industrial Informatics, 2019. journal Chun-Cheng Lin, Der-Jiunn Deng, Yen-Ling Chih, Hsin-Ting Chiu Multi-Agent Reinforcement Learning for Job Shop Scheduling in Flexible Manufacturing Systems International Conference on Artificial Intelligence for Industries (AI4I), 2019. paper
Knapsack Problem
Knapsack Problem # The Knapsack Problem is a classic optimization problem where items with weights and values must be selected to maximize total value while respecting a weight constraint. Recent Literature # A Novel Method to Solve Neural Knapsack Problems ICML, 2021. paper, code Li Duanshun and Liu Jing and Lee Dongeun and Seyedmazloom Ali and Kaushik Giridhar and Lee Kookjin and Park Noseong DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization NeurIPS, 2023. paper, code
Max Clique
Max Clique # The Maximum Clique problem seeks the largest clique in a graph. A clique is a subset of vertices where every vertex is connected to every other vertex. Recent Literature # Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem NeurIPS, 2022. paper, code Yimeng Min, Frederik Wenkel, Michael Perlmutter, Guy Wolf Variational Annealing on Graphs for Combinatorial Optimization NeurIPS, 2023. paper, code Sanokowski, Sebastian and Berghammer, Wilhelm Franz and Hochreiter, Sepp and Lehner, Sebastian
Maximal Common Subgraph (MCS)
Maximal Common Subgraph (MCS) # The Maximal Common Subgraph problem finds the largest subgraph common to two graphs, with applications in molecular matching and pattern discovery. Recent Literature # 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.
Maximal Cut (Max-Cut)
Maximal Cut (Max-Cut) # The Maximal Cut problem is to partition the vertices of a graph into two sets to maximize the number of edges between them. It’s a fundamental problem in combinatorial optimization. Recent Literature # Learning Combinatorial Optimization Algorithms over Graphs. NeurIPS, 2017. paper Dai, Hanjun and Khalil, Elias B and Zhang, Yuyu and Dilkina, Bistra and Song, Le Exploratory Combinatorial Optimization with Reinforcement Learning. AAAI, 2020. paper LBarrett, Thomas and Clements, William and Foerster, Jakob and Lvovsky, Alex.
Maximum Independent Set
Maximum Independent Set # The Maximum Independent Set problem is about finding the largest subset of vertices in a graph with no edges between them. It’s an NP-hard problem with important applications. Recent Literature # Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. NeurIPS, 2018. paper Li, Zhuwen and Chen, Qifeng and Koltun, Vladlen. Learning What to Defer for Maximum Independent Sets ICML, 2020. paper Ahn, Sungsoo and Seo, Younggyo and Shin, Jinwoo
Mixed Integer Programming (MIP)
Mixed Integer Programming (MIP) # Mixed Integer Programming is a fundamental optimization framework widely used in operations research. Machine learning approaches are being applied to improve MIP solvers. Recent Literature # Sequential model-based optimization for general algorithm configuration International conference on learning and intelligent optimization, 2011. journal Hutter, Frank and Hoos, Holger H and Leyton-Brown, Kevin Non-model-based Search Guidance for Set Partitioning Problems AAAI, 2012. paper Kadioglu, Serdar and Malitsky, Yuri and Sellmann, Meinolf
Optimal Power Flow
Optimal Power Flow # Optimal Power Flow (OPF) is a fundamental problem in power systems optimization, determining the setpoints for generators to supply electricity while minimizing costs and satisfying physical and operational constraints. Recent Literature # Learning-based Optimal Power Flow ICLR, 2023. paper, code Yunqi Ding, Kai Wang, Yuanzhang Xiao, Dongyu Zhang Physics-Informed Neural Networks for Power Systems in the Presence of Uncertainty IEEE Power & Energy Society General Meeting, 2023. paper
Orienteering Problem (OP)
Orienteering Problem (OP) # The Orienteering Problem involves selecting a subset of locations to visit with profit maximization subject to distance constraints. Recent Literature # A reinforcement learning approach to the orienteering problem with time windows Computers & Operations Research, 2021. paper, code Ricardo Gama, Hugo L. Fernandes Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization ICML, 2023. paper Son, Jiwoo and Kim, Minsu and Kim, Hyeonah and Park, Jinkyoo
Portfolio Optimization (PortOpt)
Portfolio Optimization (PortOpt) # Portfolio Optimization is about selecting and managing assets to achieve financial goals. Machine learning is increasingly being applied to improve portfolio management strategies. Recent Literature # ⭐LinSATNet: The Positive Linear Satisfiability Neural Networks ICML, 2023. paper, code Runzhong Wang and Yunhao Zhang and Ziao Guo and Tianyi Chen and Xiaokang Yang and Junchi Yan Integrating prediction in mean-variance portfolio optimization Quantitative Finance, 2023. paper Butler, Andrew and Kwon, Roy H
Predict+Optimize
Predict+Optimize # Predict+Optimize (also called Decision-Focused Learning) integrates prediction and optimization into a unified framework, where predictions are optimized for decision quality rather than traditional accuracy metrics. Recent Literature # Predict then Optimize Operations Research, 2021. paper, code Adam Elmachtoub, Paul Grigas Decision-Focused Learning of Robust Predictive Models ICML, 2019. paper, code Adam N. Elmachtoub, Paul Grigas Optimization-Based Algorithms for Decision-Focused Evaluation ICML, 2021. paper, code Yochanan Kotary, Yehuda Navon, Atara Nowik, Yaron Lipman Decision-Focused Learning with Offline Data NeurIPS, 2022. paper, code
Quadratic Assignment Problem (QAP)
Quadratic Assignment Problem (QAP) # The Quadratic Assignment Problem is a classical NP-hard combinatorial optimization problem with applications in location theory and circuit design. Recent Literature # 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 ⭐Neural Graph Matching Network: Learning Lawler’s Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching. TPAMI, 2021. paper, code
Sorting & Ranking (Sort&Rank)
Sorting & Ranking (Sort&Rank) # Sorting and ranking problems involve learning to order elements according to some criteria, with applications in information retrieval and preference learning. Recent Literature # Ranking via sinkhorn propagation Arxiv, 2011. paper Ryan Prescott Adams, Richard S. Zemel Predict+optimise with ranking objectives: exhaustively learning linear functions IJCAI, 2019. paper Demirovic, Emir and Stuckey, Peter J. and Bailey, James and Chan, Jeffrey and Leckie, Christopher and Ramamohanarao, Kotagiri and Guns, Tias
Stochastic Combinatorial Optimization
Stochastic Combinatorial Optimization # Stochastic Combinatorial Optimization addresses CO problems where some parameters are random or uncertain, requiring robust or adaptive solutions that perform well under uncertainty. Recent Literature # Robust Combinatorial Optimization with Locally Predictable Uncertainty ICLR, 2023. paper Haozhe Sun, Shaoyu Wang, Jiaqi Ma, Chen Gong, Chen Tian Learning Robust Policies for Combinatorial Optimization ICML, 2022. paper, code Ankit Anupam, Joon Oh, Jure Leskovec Stochastic Combinatorial Optimization with Oracle Subsampling NeurIPS, 2021. paper
Travelling Salesman Problem (TSP)
Travelling Salesman Problem (TSP) # The Travelling Salesman Problem is one of the most famous NP-hard optimization problems, with extensive research on neural and ML-based approaches. Recent Literature # Learning Combinatorial Optimization Algorithms over Graphs. NeurIPS, 2017. paper Dai, Hanjun and Khalil, Elias B and Zhang, Yuyu and Dilkina, Bistra and Song, Le Learning Heuristics for the TSP by Policy Gradient CPAIOR, 2018. paper, code Michel DeudonPierre CournutAlexandre Lacoste Attention, Learn to Solve Routing Problems! ICLR, 2019. paper
Vehicle Routing Problem (VRP)
Vehicle Routing Problem (VRP) # The Vehicle Routing Problem is about finding optimal routes for a fleet of vehicles to serve a set of customers, a fundamental problem in logistics and transportation. Recent Literature # Learning to Perform Local Rewriting for Combinatorial Optimization. NeurIPS, 2019. paper, code Chen, Xinyun and Tian, Yuandong. Deep Reinforcement Learning for the Electric Vehicle Routing Problem with Time Windows. Arxiv, 2020. paper Lin, Bo and Ghaddar, Bissan and Nathwani, Jatin.
Vertex Cover
Vertex Cover # The Vertex Cover problem seeks the smallest set of vertices such that every edge in the graph is incident to at least one vertex in the set. This is a fundamental NP-hard problem in graph theory. Recent Literature # Learning Vertex Cover via Reinforcement Learning ICLR, 2024. paper Kevin Kuo, Adeola Oscar Adeniyi, Henry Hoffmann ⭐NN-Baker: Neural Network-Guided Baker’s Algorithm for Vertex Cover NeurIPS, 2024. paper, code Jiale Ma and Wenzheng Pan and Yang Li and Junchi Yan
Virtual Network Embedding
Virtual Network Embedding # Virtual Network Embedding (VNE) is the problem of mapping virtual network components (nodes and links) onto a physical network infrastructure, optimizing resource utilization and quality of service. Recent Literature # Deep Reinforcement Learning for Virtual Network Embedding ACM SIGCOMM, 2020. paper, code Zhu Ren, Liang Hong, Wei Zhang GNN-based Reinforcement Learning for Virtual Network Embedding IEEE ICDCS, 2021. paper Yikang Wang, Zhu Ren, Mingwei Xu, Wei Zhang Neural Network Assisted Heuristics for Virtual Network Embedding IEEE INFOCOM, 2021. paper