Polynomial-time method solves complex combinatorial semi-bandits.
problem Optimal strategies for combinatorial semi-bandits with uncorrelated Gaussian rewards.
method Proposes a polynomial-time method to solve the Graves-Lai optimization problem for various combinatorial structures.
result First known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.
A new method uses heat diffusion to efficiently solve combinatorial optimization problems.
problem Challenges in combinatorial optimization due to discrete nature and limited search scope.
method Transforming the target function through heat diffusion to enable information flow and more efficient navigation.
result Superior performance across various combinatorial optimization problems.
MOCA-HESP optimizes high-dimensional combinatorial and mixed spaces using hyper-ellipsoid partitioning.
problem Challenges in optimizing high-dimensional, combinatorial and mixed spaces.
method MOCA-HESP uses hyper-ellipsoid space partitioning with different categorical encoders and multi-armed bandit for adaptive selection.
result MOCA-HESP outperforms existing methods on various synthetic and real-world benchmarks.
DeepCO uses deep learning for offline combinatorial optimization in warehouse operations.
problem Optimizing warehouse operation sequences in offline settings.
method DeepCO framework utilizing distribution regularized optimization for TSP.
result DeepCO reduces route length by 5.7% on average for TSP problems.
Graph neural networks improve combinatorial optimization by leveraging inductive bias.
problem Combinatorial optimization problems often arise from related data distributions.
method Using graph neural networks to enhance or solve combinatorial tasks.
result Graph neural networks effectively encode combinatorial and relational input.
ML4CO uses machine learning to improve combinatorial optimization solvers.
problem Solving combinatorial problems in practice often involves related data distributions.
method Replacing heuristic components with machine learning approaches.
result Improved state-of-the-art combinatorial optimization solvers.
Bayesian optimization method tackles combinatorial spaces, scalable for large data.
problem Optimization over combinatorial categorical spaces in natural sciences.
method Combines variational optimization and continuous relaxations for gradient-based optimization.
result Method performs comparably to state-of-the-art methods while scaling well.
Bayesian optimization adapted for discrete spaces using random mappings.
problem Global optimization of expensive black-box functions with discrete variables.
method Embeds discrete space into a convex polytope, performs optimization in continuous space.
result Method outperforms existing methods in large combinatorial spaces.
This paper tackles combinatorial optimization under uncertainty with limited feedback.
problem Tackling combinatorial optimization problems with uncertain or unknown parameters.
method Review of techniques for combinatorial pure exploration with limited bandit feedback.
result Introduction of methods for combinatorial optimization under uncertainty with limited observation.
The optimization of expensive-to-evaluate black-box functions over combinatorial structures is an ubiquitous task in machine learning, engineering and the natural sciences. The combinatorial explosion of the search space and costly evaluations pose challenges for current techniques in discrete optimization and machine …
Surveying machine learning for solving graph optimization problems.
problem Solving combinatorial optimization problems on graphs requires algorithmic engineering.
method Surveying machine learning approaches for graph optimization.
result Machine learning offers new ways to solve graph optimization problems.
Paper uses RL to solve constrained combinatorial optimization problems.
problem Constrained combinatorial optimization problems.
method Extending NCO theory to CMDPs, using RL with penalty signals.
result Proposes a superior method for solving constrained problems.
New method uses diffusion models for unsupervised combinatorial optimization.
problem Learning to sample from intractable discrete distributions without training data.
method Lifts the restriction of generative models needing exact sample likelihoods using a loss that bounds reverse KL divergence.
result Achieves new state-of-the-art results in data-free Combinatorial Optimization.
LGS-Net improves NCO performance on combinatorial optimization tasks.
problem NP-hard combinatorial optimization problems in logistics, manufacturing, and drug discovery.
method LGS-Net uses a latent space model that conditions on problem instances and introduces Latent Guided Sampling for efficient inference.
result Empirical results show state-of-the-art performance on benchmark routing tasks.
This paper surveys RL for combinatorial optimization, focusing on TSP.
problem Optimizing solutions for combinatorial optimization problems.
method Reinforcement learning applied to combinatorial optimization problems, specifically the TSP.
result Deep learning mechanisms enhance RL algorithms for near-optimal solutions.
End-to-end trainable graph matching using improved combinatorial solvers.
problem Graph matching in deep learning.
method Combining deep learning with optimized combinatorial solvers.
result Advances state-of-the-art on deep graph matching benchmarks.
Bayesian optimization method for permutations accelerates combinatorial search.
problem Optimizing expensive-to-evaluate objectives on permutation problems.
method LAW2ORDER, a batch Bayesian optimization method based on the acquisition weighted kernel.
result LAW2ORDER achieves sublinear batch cumulative regret, demonstrating accelerated search.
This work proposes an unsupervised neural network framework for solving combinatorial optimization problems on graphs.
problem Challenges in neural networks solving combinatorial optimization problems without labeled instances.
method Inspired by Erdos' probabilistic method, a neural network parametrizes a probability distribution over sets, optimizing it to find low-cost integral solutions.
result The method provides valid solutions to the maximum clique problem and local graph clustering, achieving competitive results.
New algorithm eliminates arms to minimize regret in complex bandit problems.
problem Minimizing regret in combinatorial bandit problems with explicit exploration.
method Introduces a novel arm elimination scheme that partitions arms into three categories and incorporates explicit exploration.
result Achieves near-optimal regret in combinatorial multi-armed and linear contextual bandit problems.
Bayesian optimization for high-dimensional combinatorial spaces using embeddings.
problem Optimizing expensive functions over large, complex input spaces.
method Dictionary-based ordinal embeddings for high-dimensional combinatorial structures, using Gaussian process models.
result The proposed method outperforms state-of-the-art BO methods on diverse real-world benchmarks.
New model enhances SPIM for solving low-rank combinatorial optimization and statistical learning problems.
problem Solving large-scale combinatorial optimization problems efficiently.
method Proposed a new computing model for SPIM that can handle low-rank interaction matrices.
result Demonstrated efficient learning, classification, and sampling of MNIST images using the model.
A method learns to solve multilevel combinatorial problems with two players.
problem Multilevel combinatorial optimization problems with multiple players.
method Value-based multi-agent reinforcement learning in a graph neural network framework.
result Close to optimal solutions on graphs up to 100 nodes, with a significant speedup.
GFlowNets improve combinatorial optimization by efficiently sampling from solution spaces.
problem NP-hard combinatorial optimization problems with structured constraints.
method Design Markov decision processes and train conditional GFlowNets to sample solutions.
result GFlowNet policies find high-quality solutions efficiently on various CO tasks.
Study non-linear combinatorial bandits with polynomial rewards, finding significant differences from linear cases.
problem Adversarial combinatorial bandits with general non-linear reward functions.
method Extending existing work on adversarial linear combinatorial bandits, analyzing minimax optimal regret for polynomial and non-polynomial reward functions.
result Minimax optimal regret bounds for adversarial combinatorial bandits with general non-linear reward functions.
New method improves combinatorial optimization by overcoming inefficient sampling.
problem Wandering in contours: sampling similar solutions for long periods.
method Reheated Gradient-based Discrete Sampling with a novel mechanism.
result Superior performance across various combinatorial optimization problems.
New method improves combinatorial optimization by capturing dependencies among solution variables.
problem Performance limitations in solving combinatorial optimization problems using independent solution variables.
method Subgraph tokenization and variational annealing to capture dependencies and improve learning efficiency.
result Empirical evidence shows superior performance of autoregressive methods with tokenization and annealed entropy regularization.
SRL embeds combinatorial optimization into RL for better decision-making.
problem Challenges of standard RL in complex, structured decision-making problems.
method Structured Reinforcement Learning (SRL) with combinatorial optimization layers in actor neural network.
result SRL outperforms unstructured RL and imitation learning by up to 92% on dynamic problems.
The emergence of specialized optimization hardware such as CMOS annealers and adiabatic quantum computers carries the promise of solving hard combinatorial optimization problems more efficiently in hardware. Recent work has focused on formulating different combinatorial optimization problems as Ising models, the core m…
Bayesian Optimization for graph node subset functions.
problem Optimizing functions over node subsets in graphs.
method Bayesian Optimization framework for combinatorial optimization on graphs.
result Effectiveness of the proposed BO framework on various graph types and tasks.
Optimizes bounds for multiple T-singularities on surfaces.
problem Bounding T-singularities on non-rational projective surfaces with many singularities.
method Analyzes combinatorial configurations and classifies them to find optimal bounds.
result Classifies all combinatorial configurations leading to high bounds, proving their non-existence gives optimal bounds.
Improved statistical efficiency of Thompson Sampling for combinatorial semi-bandits.
problem Efficiency of policies in stochastic combinatorial multi-armed bandits with semi-bandit feedback.
method Analysis of Combinatorial Thompson Sampling (CTS) using Beta and Gaussian priors for mutually independent and multivariate sub-Gaussian outcomes.
result CTS provides an efficient policy with optimal asymptotic regret for both mutually independent and multivariate sub-Gaussian outcomes.
This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a distribution over different city permutations. Using negative t…
When samples have internal structure, we often see a mismatch between the objective optimized during training and the model's goal during inference. For example, in sequence-to-sequence modeling we are interested in high-quality translated sentences, but training typically uses maximum likelihood at the word level. The…
Paper analyzes FTPL's effectiveness in combinatorial semi-bandit problems.
problem Optimizing FTPL policy in combinatorial semi-bandit problems.
method Geometric resampling (GR) and conditional geometric resampling (CGR) for FTPL in semi-bandit setting.
result FTPL achieves optimal regret bounds in both Fréchet and Pareto distributions.
New framework analyzes effectiveness of neural network-based combinatorial problem solvers.
problem Analyzing neural network-based methods for combinatorial optimization problems.
method Introducing a theoretical framework to assess the effectiveness of solution-samplers using policy-gradient methods.
result Positive theoretical answer to the existence of expressive, tractable, and benign optimization landscapes for combinatorial problems.
This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are other…
Combinatorial approach to α-Ricci and Lin-Lu-Yau Ricci curvatures on graphs
problem Curvature formulas for α-Ricci and Lin-Lu-Yau Ricci curvatures on graphs method Combinatorial construction of optimal transport plans and exact formulas
result Combinatorial proof of known curvature formulas
A framework for generating 3D shapes by sequentially assembling primitives.
problem Combinatorial complexity in generating 3D shapes.
method Bayesian optimization for efficient exploration and exploitation of feasible combinations.
result Successfully generates realistic combinatorial 3D shapes.
Improves scalability of Bayesian optimization for combinatorial spaces.
problem Optimizing expensive functions over large combinatorial spaces.
method Parametrized Submodular Relaxation (PSR) to solve AFO problems for BOCS.
result Significant improvements in scalability and accuracy for BOCS model.
This paper focuses on Bayesian Optimization (BO) for objectives on combinatorial search spaces, including ordinal and categorical variables. Despite the abundance of potential applications of Combinatorial BO, including chipset configuration search and neural architecture search, only a handful of methods have been pro…
Paper tackles combinatorial reinforcement learning with preference feedback.
problem Modeling long-term user engagement in scenarios like recommender systems and online advertising.
method Assumes a contextual MNL preference model with linear mean utilities and approximates item values. Proposes MNL-VQL algorithm.
result Achieves nearly minimax-optimal regret for linear MDPs with preference feedback.
New framework for resilient bi-criteria optimization under noisy feedback.
problem Bi-criteria combinatorial optimization with noisy function evaluations.
method Introducing (α,β,δ,extttN)-resilience and developing a black-box framework. result Achieves sublinear regret and constraint violation for bi-criteria bandit problems.
VCSMC improves efficiency in Bayesian phylogenetic inference.
problem Inefficient exploration of phylogenetic state space.
method Variational Combinatorial Sequential Monte Carlo (VCSMC) and nested CSMC.
result VCSMC and VNCSMC explore higher probability spaces efficiently.
Linear-time graph optimization using reinforcement learning.
problem Solving combinatorial optimization problems on real-world graphs.
method Graph neural network trained with reinforcement learning.
result Approximate solutions in linear time for various graph problems.
Many traditional algorithms for solving combinatorial optimization problems involve using hand-crafted heuristics that sequentially construct a solution. Such heuristics are designed by domain experts and may often be suboptimal due to the hard nature of the problems. Reinforcement learning (RL) proposes a good alterna…
Many real-world problems can be reduced to combinatorial optimization on a graph, where the subset or ordering of vertices that maximize some objective function must be found. With such tasks often NP-hard and analytically intractable, reinforcement learning (RL) has shown promise as a framework with which efficient he…
New method improves solving combinatorial optimization problems with smoothed policies.
problem Solving combinatorial optimization problems repeatedly with varying instances.
method Smoothed policies with controlled random perturbations to linear oracle, leading to differentiable surrogate risk.
result Generalization bound decomposes excess risk into bias, estimation, and optimization components.
RLD improves combinatorial optimization by avoiding local minima.
problem Efficiently solving combinatorial optimization problems.
method Regularized Langevin Dynamics (RLD) for combinatorial optimization.
result RLD achieves comparable or better performance than previous methods.