Machine Learning & Combinatorial Optimization ³⁴

A comprehensive overview of machine learning approaches and techniques applied to combinatorial optimization problems, covering foundational concepts, methodologies, and state-of-the-art advances.

Scope: Systematic review of learning-based CO solving methods including supervised learning for heuristics, reinforcement learning for search policies, and hybrid approaches combining classical and neural methods.

Graph Matching #

The problem of finding correspondences between vertices in two graphs, with applications in pattern recognition, shape analysis, and image matching. Deep learning methods have enabled scalable solutions for large graphs.

Definition: Given graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, find a correspondence $\pi: V_1 \to V_2$ that maximizes structural similarity, typically measured by the number of preserved edge relationships or minimizing matching cost.

Quadratic Assignment Problem #

An NP-hard optimization problem that assigns n facilities to n locations to minimize total cost, where costs depend on pairwise assignments. Classical applications include facility layout and keyboard design.

Formulation: Minimize $\sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{\pi(i)j}$ where $\pi$ is a permutation of locations, subject to assignment constraints where each facility is assigned to exactly one location.

Travelling Salesman Problem #

One of the most studied combinatorial optimization problems, seeking the shortest route visiting all cities exactly once. Neural approaches and learning-based heuristics have shown competitive performance compared to traditional methods.

Formulation: Minimize $\sum_{i=1}^{n} d(c_{\pi(i)}, c_{\pi(i+1 \bmod n)})$ where $\pi$ is a permutation of $n$ cities and $d$ is the distance function, subject to visiting each city exactly once.

Portfolio Optimization #

Financial optimization for asset allocation, determining optimal portfolio composition to maximize returns while managing risk and satisfying investment constraints.

Formulation: Maximize $\mathbf{w}^T \boldsymbol{\mu} - \lambda \mathbf{w}^T \Sigma \mathbf{w}$ subject to $\sum w_i = 1$ and $w_i \geq 0$, where $\mathbf{w}$ are weights, $\boldsymbol{\mu}$ expected returns, $\Sigma$ covariance matrix, and $\lambda$ risk aversion.

Maximal Cut #

The problem of partitioning graph vertices into two sets to maximize edges between partitions. A fundamental graph problem with applications in circuit design and network optimization.

Formulation: Partition vertices $V$ into disjoint sets $S$ and $\bar{S}$ to maximize $|{(u,v) \in E : u \in S, v \in \bar{S}}|$, or equivalently maximize $\sum_{(u,v) \in E} x_u(1-x_v)$ where $x_i \in {0,1}$.

Vehicle Routing Problem #

Optimizing routes for a fleet of vehicles to serve customers with minimum distance/cost. Extensions include time windows, capacity constraints, and multiple depots, common in logistics and delivery services.

Formulation: Minimize $\sum_{k=1}^{K} \sum_{i,j} c_{ij} x_{ijk}$ subject to each customer visited by exactly one vehicle, vehicle capacity constraints $\sum_{i \in R_k} d_i \leq C_k$, and flow conservation constraints where $x_{ijk}$ indicates if vehicle $k$ travels from $i$ to $j$.

Job Shop Scheduling Problem #

Scheduling jobs on machines to minimize completion time while respecting precedence and machine constraints. A fundamental problem in manufacturing and production planning.

Formulation: Minimize makespan $C_{max}$ subject to: each job $j$ consists of operations that must be processed in order on specified machines, each machine can process at most one operation at a time, and operation durations are fixed.

Maximum Independent Set #

Finding the largest set of vertices with no edges between them in a graph. An NP-hard problem with applications in scheduling, coding theory, and network design.

Formulation: Maximize $\sum_{i=1}^{n} x_i$ subject to $x_i + x_j \leq 1$ for all $(i,j) \in E$ and $x_i \in {0,1}$, where $x_i = 1$ if vertex $i$ is in the set.

Generalization #

Studying how machine learning solvers generalize across different problem instances and scales, and developing methods that handle adversarial or out-of-distribution scenarios.

Definition: Train model $\theta$ on distribution $D_{train}$ minimizing $\mathbb{E}{\mathbf{x} \sim D{train}}[\ell(f_\theta(\mathbf{x}), y^)]$ such that test error $\mathbb{E}{\mathbf{x} \sim D{test}}[\ell(f_\theta(\mathbf{x}), y^)]$ remains small for $D_{test}$ different from $D_{train}$ (different sizes, perturbations).

Orienteering Problem #

A variant of the traveling salesman problem where a subset of vertices must be selected to maximize profit while respecting a distance constraint. Applications include tourist route planning and project selection.

Formulation: Maximize $\sum_{i \in S} p_i$ subject to the total travel distance $\sum_{i,j \in S} d_{ij} \leq L$ where $S \subseteq V$ is selected vertices, $p_i$ are profits, and $L$ is distance limit.

Knapsack #

The problem of selecting items with given weights and values to maximize total value within a weight capacity. A fundamental dynamic programming problem with numerous variants (0/1, bounded, unbounded).

Formulation: Maximize $\sum_{i=1}^{n} v_i x_i$ subject to $\sum_{i=1}^{n} w_i x_i \leq W$ and $x_i \in {0,1}$, where $v_i$ are values, $w_i$ are weights, and $W$ is capacity.

Computing Resource Allocation #

Optimal allocation of computational resources (CPU, memory, bandwidth) across tasks or virtual machines to maximize utilization while meeting performance requirements.

Formulation: Maximize $\sum_{t=1}^{T} u_t$ subject to $\sum_{t \in task_i} r_{t,d} \leq R_{i,d}$ for each device $d$, latency constraints $L_t \leq L_{max,t}$, where $u_t$ is utility and $r_{t,d}$ is resource $d$ for task $t$.

Bin Packing Problem #

Packing items of varying sizes into a minimum number of bins, a classic problem in logistics and resource management. Variants include 2D and 3D packing with practical applications in shipping and manufacturing.

Formulation: Minimize $\sum_{b=1}^{B} y_b$ subject to $\sum_{i \in b} s_i \leq C \cdot y_b$ for each bin $b$, where $s_i$ is item size, $C$ is bin capacity, $y_b \in {0,1}$ indicates if bin is used.

Graph Edit Distance #

Measuring the dissimilarity between two graphs as the minimum cost of edit operations (insertions, deletions, substitutions) needed to transform one into another. Used in pattern recognition and molecule comparison.

Definition: $GED(G_1, G_2) = \min_{\xi} \sum_{op \in \xi} cost(op)$ where $\xi$ is an edit path transforming $G_1$ to $G_2$, and cost is the sum of operation costs (vertex/edge insertion, deletion, substitution).

Hamiltonian Cycle Problem #

Finding a cycle that visits every vertex exactly once in an undirected graph. A fundamental NP-complete problem related to the traveling salesman problem.

Definition: Determine if there exists a cycle in graph $G = (V, E)$ that visits every vertex in $V$ exactly once. Decision problem: is a Hamiltonian cycle present?

Graph Coloring #

Assigning colors to vertices such that no adjacent vertices share the same color, using the minimum number of colors. Applications include scheduling, register allocation, and map coloring.

Formulation: Minimize $k$ such that $c: V \to {1, …, k}$ where $c(u) \neq c(v)$ for all $(u,v) \in E$, i.e., find the chromatic number $\chi(G)$.

Maximal Common Subgraph #

Finding the largest subgraph isomorphic to both input graphs, useful in molecular structure comparison and pattern discovery applications.

Definition: Find subgraph $G_{mcs} = (V_{mcs}, E_{mcs})$ that is isomorphic to subgraphs of both $G_1$ and $G_2$, maximizing $|V_{mcs}|$ (or $|E_{mcs}|$).

Influence Maximization #

Selecting a subset of nodes in a social network to maximize the spread of information or influence through the network. A key problem in viral marketing and network analysis.

Formulation: Select subset $S \subseteq V$ with $|S| \leq k$ to maximize expected spread $f(S)$, where $f(S) = E[|T(S)|]$ is the expected number of influenced nodes given initial set $S$.

Boolean Satisfiability #

Determining if a boolean formula can be satisfied, one of the most studied NP-complete problems. Recent neural approaches have shown promise for both solving and reasoning about SAT instances.

Definition: Given boolean formula $\phi$ in conjunctive normal form (CNF) with $m$ clauses over $n$ variables, determine if there exists an assignment $\mathbf{x} \in {0,1}^n$ such that $\phi(\mathbf{x}) = \text{true}$.

Max Clique #

Finding the largest clique (complete subgraph) in an undirected graph. An NP-hard problem with applications in social network analysis and bioinformatics.

Formulation: Maximize $\sum_{i=1}^{n} x_i$ subject to $x_i + x_j \leq 1 + \mathbb{1}_{(i,j) \in E}$ for all $i < j$ and $x_i \in {0,1}$, finding largest complete subgraph.

Mixed Integer Programming #

Optimizing linear objective functions subject to linear constraints where some variables must be integers. A general framework encompassing many CO problems, widely used in operations research.

Formulation: Minimize $\mathbf{c}^T \mathbf{x}$ subject to $A\mathbf{x} \leq \mathbf{b}$, $\mathbf{x} \geq \mathbf{0}$, and $x_i \in \mathbb{Z}$ for $i \in I$, where $I$ indicates integer-constrained variables.

Causal Discovery #

Learning the underlying causal structure from observational data, identifying causal relationships between variables. Important for understanding complex systems in medicine, economics, and science.

Definition: Learn directed acyclic graph (DAG) $G = (V, E)$ from observational data where edge $(i \to j) \in E$ indicates $i$ causally influences $j$. Goal: identify true DAG $G^*$ minimizing score $S(G | \mathbf{D})$ subject to acyclicity constraint.

Game Theoretic Semantics #

A game-based interpretation of logical formulas where truth is determined by winning strategies in semantic games, providing computational game-theoretic perspectives on logic and reasoning.

Definition: For formula $\phi$ in language $L$, define semantic game where two players (verifier and falsifier) move according to formula structure. Formula is true in structure if verifier has winning strategy.

Differentiable Optimization #

Making optimization layers differentiable so they can be embedded in neural networks, enabling end-to-end learning where optimization problems become trainable components of deep models.

Formulation: Given parametric optimization problem $y^* = \arg\min_y f(y; \theta)$, compute implicit gradient $\frac{\partial y^}{\partial \theta}$ using implicit differentiation: $\nabla_\theta y^ = -[\nabla_y^2 f]^{-1} \nabla_{\theta,y}^2 f$ enabling backpropagation through optimizer.

Car Dispatch #

Optimally assigning vehicles to passenger requests in ride-hailing and autonomous driving systems, minimizing empty miles and response times.

Formulation: Assign requests $R$ to vehicles $V$ minimizing $\sum_{r \in R} (\alpha \cdot ETA_r + \beta \cdot det_{r})$ subject to vehicle capacity $|A_v| \leq C_v$, time window constraints on pickups/dropoffs, and driver constraints.

Conjunctive Query Containment #

A fundamental problem in database theory and reasoning, determining whether one query result is guaranteed to be a subset of another query’s result.

Definition: Given conjunctive queries $Q_1, Q_2$ over schema, determine if $\text{ans}(Q_1, I) \subseteq \text{ans}(Q_2, I)$ for all possible database instances $I$. Equivalently, check if there exists homomorphism from $Q_2$ to $Q_1$.

Virtual Network Embedding #

Mapping virtual network components (nodes and links) onto physical infrastructure, optimizing resource utilization and quality of service in cloud computing and network management.

Formulation: Map virtual network $G_v = (V_v, E_v)$ to substrate network $G_s = (V_s, E_s)$ by finding embedding $e_n: V_v \to V_s$ and $e_l: E_v \to P(E_s)$ minimizing resource usage while ensuring capacity constraints.

Predict+Optimize #

Decision-focused learning that integrates prediction and optimization into a unified framework, optimizing predictions for decision quality rather than traditional accuracy metrics.

Formulation: Train predictor $f_\theta$ to minimize task loss $\mathcal{L}(y^(f_\theta(\mathbf{x})), y^{opt}) = \mathcal{L}(\arg\min_y f(y; f\theta(\mathbf{x})), y^_{opt})$, where $y^_{opt}$ is optimal decision under true parameters, using implicit differentiation through optimization layer.

Optimal Power Flow #

Determining optimal setpoints for generators in power systems to supply electricity while minimizing costs and satisfying physical constraints, fundamental for smart grid management.

Formulation: Minimize $\sum_{g=1}^{G} (a_g + b_g P_g + c_g P_g^2)$ subject to power balance $P_i = \sum_g P_g - L_i$, voltage constraints $|V_i| \in [V_{min}, V_{max}]$, and transmission limits.

Facility Location Problem #

Determining optimal locations for facilities (warehouses, hospitals, schools) to serve customers, minimizing total distance and facility opening costs.

Formulation: Minimize $\sum_{j=1}^{m} f_j y_j + \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij} x_{ij}$ subject to $\sum_j x_{ij} = 1$ (serve all customers), $x_{ij} \leq y_j$ (assignment constraints), and $y_j \in {0,1}$.

Sorting & Ranking #

Differentiable sorting and ranking operations that can be integrated into neural networks, enabling permutation-based learning and differentiable ranking optimization.

Definition: Approximate permutation matrix $P \in \mathbb{R}^{n \times n}$ where $P\mathbf{x}$ sorts vector $\mathbf{x}$ in differentiable manner, or compute ranking scores $r_i$ for items proportional to quality or preference.

Combinatorial Drug Recommendation #

Finding optimal combinations of drugs to maximize therapeutic efficacy while minimizing adverse interactions, a key application in personalized medicine and drug discovery.

Formulation: Select drug subset $S \subseteq D$ to maximize efficacy $f(S)$ subject to safety constraint (drug interactions) $g(S) \leq \epsilon$ and cardinality limit $|S| \leq k$.

Stochastic Combinatorial Optimization #

Addressing CO problems with random or uncertain parameters, developing robust or adaptive solutions that perform well under uncertainty and variability.

Formulation: Minimize $\mathbb{E}[f(\mathbf{x}, \boldsymbol{\xi})]$ over decision $\mathbf{x} \in X$ where $\boldsymbol{\xi}$ is random parameter vector, or find robust solution $\mathbb{x}^* = \arg\min_\mathbf{x} \max_{\boldsymbol{\xi} \in U} f(\mathbf{x}, \boldsymbol{\xi})$.

Vertex Cover #

Finding the minimum set of vertices that covers all edges in a graph. A fundamental NP-hard problem with applications in network design and bioinformatics.

Formulation: Minimize $\sum_{i=1}^{n} x_i$ subject to $x_i + x_j \geq 1$ for all $(i,j) \in E$ and $x_i \in {0,1}$, where $x_i = 1$ if vertex $i$ is in the cover.

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