Combinatorial Optimization

Follow this topic Ask about this topic

Combinatorial optimization studies how to choose the best arrangement, assignment, route, or schedule when decisions are discrete and constraints interact. Exact methods such as integer programming, constraint programming, SAT, dynamic programming, and branch-and-bound can certify optimality, while approximation algorithms and metaheuristics trade guarantees for speed on larger instances. Learning methods—including graph neural networks, reinforcement learning, and language-model-guided heuristic design—are increasingly paired with classical search to propose solutions, warm-start solvers, or select algorithms. A central challenge is making these methods scale and generalize without sacrificing feasibility, solution quality, or the guarantees that exact and approximation methods provide.

Latest papers

386 papers47 papers in the last four weeks, up 47% on the four weeks before. 0.3% of all new papers.

Feb 13, 2026

Learning to Approximate Uniform Facility Location via Graph Neural Networks

Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming.

Chendi Qian, Christopher Morris, Stefanie Jegelka +1

RWTH Aachen University, Germany · Technical University of Munich, Germany · Massachusetts Institute of Technology, USA +1

Graph Neural Networks Combinatorial Optimization Message Passing Neural Networks Approximation Algorithms Neural Combinatorial Optimization

Feb 10, 2026

ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

LLM-guided evolutionary computation, most notably AlphaEvolve, has been remarkably successful in discovering novel mathematical constructions by solving challenging optimization problems. The standard approach is to evolve a monolithic program that directly outputs a candidate solution. We present ImprovEvolve, an algorithmic alternative that drastically reduces cognitive load on the LLM. Instead of prompting the model for an end-to-end optimizer, we evolve a program with three specialized operators of initialization, local improvement, and perturbation. We then approach the optimum by iteratively applying local improvements and intensity-scheduled perturbations, effectively driving a basin-hopping search with LLM-evolved subroutines. For hexagon in hexagon packing, ImprovEvolve discovers new state-of-the-art packings of 11, 12, 15, and 16 hexagons, and additionally for 14, 17, and 23 hexagons after minimal expert tuning of the generated code. For the second autocorrelation inequality, the evolved and human-scaled program pushes the lower bound from 0.96102 to 0.96258. For spherical codes, the ImprovEvolve program lowers the best-known maximum cosine for the majority of 90 randomly chosen diverse state-of-the-art spherical codes, achieving relative improvements of up to 2.4%.

Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

1MIRIAI, Russia · 2FusionBrain Lab, Russia · 3AXXX, Russia +1

Large Language Model-Guided Scientific Discovery Evolutionary Optimization Metaheuristic Optimization Large Language Model-Guided Optimization Combinatorial Optimization Global Optimization+2

Feb 4, 2026

Graph-Theoretic Formulation of Hamiltonian and Ground-State Sign Structures in Heisenberg Antiferromagnets

We study Heisenberg antiferromagnets through a graph-theoretic representation of their Hamiltonians. In the computational basis of a fixed-magnetization sector, the Heisenberg Hamiltonian equals a constant minus the weighted Laplacian of a graph whose vertices are spin configurations and whose edges connect configurations related by exchanging two antiparallel spins on a lattice bond. We call this graph the Hilbert graph (HG) which is isomorphic to the token graph of the lattice over which the Hamiltonian is defined. The exact ground-state energy is then determined by the largest eigenvalue of the HG Laplacian, which is the spectral relaxation of weighted Max-Cut on the HG. With the amplitudes fixed, the phase-dependent part of the variational energy defines an antiferromagnetic classical XY model on the HG, with couplings set by the amplitudes. Restricting the variational state to be real, i.e., restricting its phases to

\{0,π\}

, reduces the fixed-amplitude energy minimization to solving an antiferromagnetic Ising model and hence a weighted Max-Cut on the HG. When the weights are generated from non-degenerate ground-state amplitudes, the optimal phases give the ground-state sign structure which can be recovered from the weights in time polynomial in the size of the HG. On the Hamiltonian side, a diagonal sign transformation removes all positive off-diagonal matrix elements if and only if the HG is bipartite, which reproduces the Marshall sign rule on bipartite lattices through the graph two-coloring problem; otherwise, the minimal remaining positive weight equals the sum of HG edge weights left uncut by the Max-Cut. This graph formulation establishes a common framework for understanding wave function sign structure, Hamiltonian stoquasticity, non-convexity of phase optimization in variational Monte Carlo, and the average sign in quantum Monte Carlo.

Mahmud Ashraf Shamim, Md Moshiur Rahman Raj, Mohamed Hibat-Allah +3

Department of Physics and Astronomy, University of Alabama, Tuscaloosa, 35487, Alabama, USA. · Department of Physics, University of Rajshahi, P.O. Box 6205, Rajshahi, Bangladesh. · Department of Applied Mathematics, University of Waterloo, Ontario Canada N2L 3G1 +1

Quantum Many-Body Physics Combinatorial Optimization

Feb 3, 2026

Fair and Efficient Investment in Public Transportation

We study a stylized model of infrastructure investment in public transportation. In our model, each agent travels between a pair of terminals in a network captured by a weighted graph, where edge weights represent distances. The central planner can reduce the travel time along a fixed number of edges, with the goal of maximizing the utilitarian or egalitarian welfare. When there is only one agent, we provide a polynomial-time algorithm that combines Dijkstra's algorithm with a dynamic program. We then demonstrate how to use this algorithm as a subroutine to solve the problem for two agents. Generalizing this idea, we present an XP algorithm parameterized by the number of agents

n

; however, our problem turns out to be W[1]-hard with respect to

n

. Nevertheless, we establish a fixed-parameter tractability result for the special case where all agents travel to a common hub. If the number of agents is variable, we obtain NP-completeness and inapproximability results. We discuss implications of our results for a related model of railway network design.

Martin Bullinger, Edith Elkind, Kassian Köck

School of Engineering Mathematics and Technology, University of Bristol, Bristol, UK · School of Engineering, Northwestern University, Evanston, USA · School of Computation, Information and Technology, Technical University of Munich, Munich, Germany

Algorithmic Fairness Combinatorial Optimization Parameterized Complexity

Jan 29, 2026

Towards Solving the Gilbert-Pollak Conjecture via Large Language Models

The Gilbert-Pollak Conjecture \citep{gilbert1968steiner}, also known as the Steiner Ratio Conjecture, states that for any finite point set in the Euclidean plane, the Steiner minimum tree has length at least

\sqrt{3}/2 \approx 0.866

times that of the Euclidean minimum spanning tree (the Steiner ratio). A sequence of improvements through the 1980s culminated in a lower bound of

0.824

, with no substantial progress reported over the past three decades. Recent advances in LLMs have demonstrated strong performance on contest-level mathematical problems, yet their potential for addressing open, research-level questions remains largely unexplored. In this work, we present a novel AI system for obtaining tighter lower bounds on the Steiner ratio. Rather than directly prompting LLMs to solve the conjecture, we task them with generating rule-constrained geometric lemmas implemented as executable code. These lemmas are then used to construct a collection of specialized functions, which we call verification functions, that yield theoretically certified lower bounds of the Steiner ratio. Through progressive lemma refinement driven by reflection, the system establishes a new certified lower bound of 0.8559 for the Steiner ratio. The entire research effort involves only thousands of LLM calls, demonstrating the strong potential of LLM-based systems for advanced mathematical research.

Yisi Ke, Tianyu Huang, Yankai Shu +3

School of EECS, Peking University · School of Mathematical Sciences, Peking University · State Key Laboratory of General Artificial Intelligence, Peking University, Beijing, China +2

Combinatorial Optimization Large Language Model-Guided Scientific Discovery

Jan 19, 2026

Graph Neural Networks are Heuristics

Graph neural networks are usually treated as auxiliaries for combinatorial optimization: they imitate algorithms, guide search, or supply scores to classical procedures. We show that this auxiliary role is not intrinsic. A GNN can itself be a heuristic. For the Euclidean Travelling Salesman Problem, we train a non-autoregressive GNN with no labels, rewards, sequential decoding, search, or local improvement. A differentiable Hamiltonian-cycle objective is the only supervision. The trained model produces a complete tour in one forward pass, while dropout and snapshots from a single training trajectory provide solution diversity without engineered moves. The heuristic is therefore learned, not programmed. It is also fast: batched inference remains in the millisecond regime on GPUs. Experiments on TSP100, TSP200, and TSP500 show that the model consistently improves over nearest-neighbor greedy baselines. These results identify unsupervised GNNs as a class of fast learned heuristics for combinatorial optimization.

Yimeng Min, Carla P. Gomes

Department of Computer Science Cornell University Ithaca, NY, USA

Traveling Salesperson Problem Graph Neural Networks Combinatorial Optimization Neural Combinatorial Optimization

Jan 13, 2026

Enabling Population-Based Architectures for Neural Combinatorial Optimization

Neural Combinatorial Optimization (NCO) has mostly focused on learning policies, typically neural networks, that operate on a single candidate solution at a time, either by constructing one from scratch or iteratively improving it. In contrast, decades of work in metaheuristics have shown that maintaining and evolving populations of solutions improves robustness and exploration, and often leads to stronger performance. To close this gap, we study how to make NCO explicitly population-based by learning policies that act on sets of candidate solutions. We first propose a simple taxonomy of population awareness levels and use it to highlight two key design challenges: (i) how to represent a whole population inside a neural network, and (ii) how to learn population dynamics that balance intensification (generating good solutions) and diversification (maintaining variety). We make these ideas concrete with two complementary tools: one that improves existing solutions using information shared across the whole population, and the other generates new candidate solutions that explicitly balance being high-quality with diversity. Experimental results on Maximum Cut and Maximum Independent Set indicate that incorporating population structure is advantageous for learned optimization methods and opens new connections between NCO and classical population-based search.

Andoni Irazusta Garmendia, Josu Ceberio, Alexander Mendiburu

University of the Basque Country (EHU), Department of Computer Science and Artificial Intelligence, San Sebastian, Spain.

Metaheuristic Optimization Combinatorial Optimization Neural Combinatorial Optimization

Jan 10, 2026

Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach

In this paper, we investigate the Resource-Constrained Project Scheduling Problem (RCPSP) with Time-of-Use (TOU) energy tariffs and machine states, a variant of RCPSP for production scheduling, where energy price is part of the criteria and one highly energy-demanding machine can be in one of the following three states: proc, idle, or off. The problem involves scheduling all tasks, respecting precedence constraints and resource limitations, while minimizing the combination of the overall makespan and the Total Energy Cost (TEC), which varies according to the TOU tariffs, which can take negative values. We propose two novel approaches to solve it: a monolithic Constraint Programming (CP) approach and a Logic-Based Benders Decomposition (LBBD) approach. The latter combines a master problem handling the energy cost solved using Integer Linear Programming (ILP) with a subproblem handling the RCPSP, resolved using CP. Both approaches outperform the monolithic compact ILP counterpart, but the LBBD significantly outperforms the monolithic CP in most cases, especially when the makespan criterion is not included in the objective function, solving to optimality instances with up to 480 tasks. Finally, we propose a way to generalize our LBBD approach to other problems sharing similar characteristics, and applied it to various problems, such as an RCPSP with blocking times & total weighted tardiness criterion, or a flexible job shop.

Corentin Juvigny, Antonín Novák, Jan Mandík +1

Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugosl´avsk´ych partyz´an˚u 1580/3, 160 00, Prague 6, Czech Republic

Resource-Constrained Project Scheduling Combinatorial Optimization Constraint Programming

Jan 9, 2026

A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm

Anticlustering is an NP-hard combinatorial optimization problem that consists of partitioning a set of objects into equal-sized groups called anticlusters such that the objects in the same anticluster are as dissimilar as possible and thereby representative of the entire set of objects. Here we study the case where the dissimilarity metric is the squared Euclidean distance between the respective feature vectors. Applications of Euclidean anticlustering include social studies, cross-validation, creating mini-batches for stochastic gradient descent, and finding balanced K-cut partitions. In particular, machine-learning applications such as mini-batch generation involve million-scale datasets and very large values of K, making scalable anticlustering algorithms essential. We propose a new algorithm, the Assignment-Based Anticlustering (ABA) algorithm, that scales to instances with millions of objects and hundreds of thousands of anticlusters within seconds to minutes, which is far beyond what existing anticlustering methods can manage. We demonstrate here, via an extensive computational study, that our algorithm outperforms existing anticlustering methods in both solution quality and running time. This is so also for anticlustering with categories. For the related problem of balanced K-cut partitioning, our algorithm is superior to the well-known METIS method. The code of our algorithm is available on GitHub.

Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum +1

Department of Business Administration, University of Bern, Engehaldenstr. 4, 3012 Bern, Switzerland · Riverside County Office of Education, Riverside, CA 92501, USA · Industrial Engineering and Operations Research Department, University of California, Berkeley, CA 94720, USA

Clustering Combinatorial Optimization

Jan 1, 2026

Neural Minimum Weight Perfect Matching for Quantum Error Codes

Realizing the full potential of quantum computation requires Quantum Error Correction (QEC). QEC reduces error rates by encoding logical information across redundant physical qubits, enabling errors to be detected and corrected. A common decoder used for this task is Minimum Weight Perfect Matching (MWPM) a graph-based algorithm that relies on edge weights to identify the most likely error chains. In this work, we propose a data-driven decoder named Neural Minimum Weight Perfect Matching (NMWPM). Our decoder utilizes a hybrid architecture that integrates Graph Neural Networks (GNNs) to extract local syndrome features and Transformers to capture long-range global dependencies, which are then used to predict dynamic edge weights for the MWPM decoder. To facilitate training through the non-differentiable MWPM algorithm, we formulate a novel proxy loss function that enables end-to-end optimization. Our findings on the toric code under depolarizing noise demonstrate thresholds of 17.9% and 10.95%, nearing the 18.9% and 11.0% maximum likelihood bounds, highlighting the advantage of hybrid decoders that combine the predictive capabilities of neural networks with the algorithmic structure of classical matching.

Yotam Peled, David Zenati, Eliya Nachmani

School of Electrical and Computer Engineering (ECE), Ben-Gurion University, Beer Sheva, Israel.

Neural Decoding Quantum Error Correction Combinatorial Optimization Quantum Error Correction Decoding

Nov 4, 2025

Leveraging Discrete Function Decomposability for Scientific Design

In the era of AI-driven science and engineering, we often want to design discrete objects in silico according to user-specified properties. For example, we may wish to design a protein to bind its target, arrange components within a circuit to minimize latency, or find materials with certain properties. Given a property predictive model, in silico design typically involves training a generative model over the design space (e.g., protein sequence space) to concentrate on designs with the desired properties. Distributional optimization

\unicode{x2013}

which can be formalized as an estimation of distribution algorithm or as reinforcement learning policy optimization

\unicode{x2013}

finds the generative model that maximizes an objective function in expectation. Optimizing a distribution over discrete-valued designs is in general challenging because of the combinatorial nature of the design space. However, many property predictors in scientific applications are decomposable in the sense that they can be factorized over design variables in a way that could in principle enable more effective optimization. For example, amino acids at a catalytic site of a protein may only loosely interact with amino acids of the rest of the protein to achieve maximal catalytic activity. Current distributional optimization algorithms are unable to make use of such decomposability structure. Herein, we propose and demonstrate use of a new distributional optimization algorithm, Decomposition-Aware Distributional Optimization (DADO), that can leverage any decomposability defined by a junction tree on the design variables, to make optimization more efficient. At its core, DADO employs a soft-factorized "search distribution"

\unicode{x2013}

a learned generative model

\unicode{x2013}

for efficient navigation of the search space, invoking graph message-passing to coordinate optimization across linked factors.

James C. Bowden, Sergey Levine, Jennifer Listgarten

Department of Electrical Engineering and Computer Sciences, UC Berkeley. · Center for Computational Biology, UC Berkeley. · UC Berkeley–UCSF Graduate Program in Bioengineering, UC San Francisco.

AI-Assisted Scientific Research Combinatorial Optimization

Nov 4, 2025

Arithmetic Circuits and Neural Networks for Regular Matroids

We prove that there exist uniform

(+,\times,/)

-circuits of size

O(n^3)

to compute the basis generating polynomial of regular matroids on

n

elements. By tropicalization, this implies that there exist uniform

(\max,+,-)

-circuits and ReLU neural networks of the same size for weighted basis maximization of regular matroids. As a consequence in linear programming theory, we obtain a first example where taking the difference of two extended formulations can be more efficient than the best known individual extended formulation for the base polytope of regular matroids of size

O(n^6)

by Aprile and Fiorini. Such differences have recently been introduced as virtual extended formulations. The proof of our main result relies on a fine-tuned version of Seymour's decomposition of regular matroids which allows us to identify and maintain graphic substructures to which we can apply a local version of the star-mesh transformation.

Christoph Hertrich, Stefan Kober, Georg Loho

University of Technology Nuremberg, Germany · Universit´e Libre de Bruxelles, Belgium · Freie Universität Berlin, Germany +1

Combinatorial Optimization

Oct 16, 2025

Column Generation with Domain-Independent Dynamic Programming

Column generation and branch-and-price (B&P) are leading mathematical optimization methods for large-scale exact optimization, iterating between solving a master problem and a pricing problem. Due to the difficulty of discrete optimization, high-performance column generation often relies on a custom pricing algorithm built specifically to exploit the problem's structure. This bespoke nature of the pricing solver makes column generation a problem-specific method and hinders the use of generic implementations across a wide range of problems. We show that domain-independent dynamic programming (DIDP), a model-based paradigm for dynamic programming, can be used as a generic pricing solver. We develop new modeling features and a solving algorithm for DIDP to achieve better performance in typical pricing problems. We demonstrate that in four problem classes, our implementations of B&P, with pricing by DIDP, empirically outperform an existing automated B&P solver and B&P with pricing by mixed-integer programming or constraint programming.

Ryo Kuroiwa, Edward Lam

Department of Data Science and Artificial Intelligence, Monash University, Melbourne, Australia · The Graduate University for Advanced Studies, SOKENDAI, Kanagawa, Japan

Dynamic Programming Combinatorial Optimization

Oct 4, 2025

Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity

Balancing resource efficiency and fairness is critical in networked systems that support modern learning applications. We introduce the Fair Minimum Labeling (FML) problem: the task of designing a minimum-cost temporal edge activation plan that ensures each group of nodes in a network has sufficient access to a designated target set, according to specified coverage requirements. FML captures key trade-offs in systems where edge activations incur resource costs and equitable access is essential, such as distributed data collection, update dissemination in edge-cloud systems, and fair service restoration in critical infrastructure. We first give a structural characterisation of the single-terminal case, showing that it is equivalent to the rooted Covering Steiner problem. We prove that FML is NP-hard and admits no

((1-ε)\ln |\mathcal{C}|)

-approximation for

|\mathcal{C}|

groups, already on a star, while for any fixed number of groups it inherits a constant-factor approximation and remains APX-hard. We then present probabilistic approximation algorithms for the two-group, single-terminal case: an algorithm whose tree subroutine is exact, hence optimal on tree-structured networks and

\mathcal{O}(\log |V|)

in expectation on general graphs, together with a faster bicriteria variant whose coverage violation degrades gracefully with the merge depth of the tree computation. For practical scalability, we additionally introduce a graph-native variant based on a shortest-path-tree reduction. Empirical results show that FML enforces group-level fairness, while the graph-native variant substantially improves scalability and achieves competitive activation cost.

Lutz Oettershagen, Othon Michail

University of Liverpool

Fair Resource Allocation Combinatorial Optimization Group Fairness Approximation Algorithms

Sep 29, 2025

Graph Optimization Foundation Model: Tokenizing Graph via A Language-Model Paradigm

The pretrain-transfer paradigm, which underpins the success of large language models (LLMs), has demonstrated the immense power of creating foundation models that learn generalizable representations from vast datasets. However, extending this paradigm to Operations Research (OR) problems on graph structures remains challenging due to the fundamental conflict between the statistical flexibility of language and the strict combinatorial constraints of graphs. To bridge this gap, we introduce the Graph Foundation Model (GFM), the first framework capable of solving all distance-based optimization problems on graph structures. By introducing the LLM-like self-supervised pre-training paradigm on the paths generated from random walks in the graph, GFM is compelled to internalize the graph's complex topological and combinatorial rules, where the connectivity of the structure itself can be treated as the supervisory signal. Unlike existing neural methods that learn complex and task-specific solving policies, our approach leverages the pre-trained GFM as a foundational model of the graph's intrinsic structure, which in turn enables a simple generative heuristic to tackle a diverse range of optimization challenges effectively. Comprehensive experiments on networks ranging from 20 to 893 nodes demonstrate that GFM achieves competitive performance against specialized solvers across a variety of distinct optimization task classes, while maintaining significantly faster inference times. Our work establishes a new paradigm of adapting the pretrain-transfer framework to graph optimization, opening the door for applying foundation model innovations to OR.

Yunhao Liang, Pujun Zhang, Yuan Qu +3

Faculty of Engineering, The University of Hong Kong, Hong Kong SAR, China · Costello College of Business, George Mason University, VA, USA · Faculty of Business and Economics, The University of Hong Kong, Hong Kong, China +1

Graph SSL Combinatorial Optimization Graph Foundation Models

Sep 26, 2025

Self-Improving Neural Pruning: A Graph Neural Network Framework for Scalable Mixed Bundle Pricing

Mixed bundle pricing is a classic revenue management problem arising in industries such as e-commerce, tourism, and video games. It refers to designing product combinations (i.e., bundles) and determining their prices to maximize expected profit. Exact mixed-bundling formulations capture this structure but are computationally intractable because the number of possible bundles grows exponentially with the number of products. We propose a graph neural network (GNN)-guided pruning framework for scalable (non-)additive bundle pricing. Instead of learning on the exponential bundle-level formulation, we encode each instance as a compact customer-product graph and train an edge-output GNN to learn the product-assignment probabilities from optimal mixed-bundling solutions. The predicted probabilities are then converted into restricted candidate bundle families through fixed cutoff pruning and progressive cutoff pruning; the final prices and assignments are obtained by solving the mixed bundling formulation over the retained bundles. We further introduce a GNN-guided local search and an iterative self-improvement procedure for larger instances. The local search refines the retained bundle family by prioritizing high-confidence add/drop moves, while the iterative self-improvement procedure generates high-quality solutions on larger instances for retraining. Theoretically, we show that under mild distinguishability conditions the proposed edge-output GNN class is expressive enough to recover the optimal product-assignment mapping. Experiments show that the proposed policies recover over 98% of the optimal profit on small instances and outperform bundle-size pricing on larger instances with substantial runtime savings.

Liangyu Ding, Chenghan Wu, Guokai Li +1

School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, China

Graph Neural Networks Combinatorial Optimization Neural Combinatorial Optimization

Sep 5, 2025

Recurrent State Encoders for Efficient Neural Combinatorial Optimization

The primary paradigm in Neural Combinatorial Optimization (NCO) consists of construction methods, where a neural network is trained to sequentially add one solution component at a time until a complete solution is formed. We observe that the typical changes to the state between two steps are small, since usually only the node added to the solution is removed from the state. An efficient model should be able to reuse computation from prior steps. To that end, we propose a recurrent encoder that computes state embeddings based not only on the current state but also on embeddings from the previous state. We show that this recurrent encoder can achieve equivalent or better performance than a non-recurrent encoder even with

3\times

fewer layers, thus significantly improving latency. We demonstrate our findings on three different problems: the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Orienteering Problem (OP), and integrate the models into a large neighborhood search algorithm to showcase the practical relevance of our findings.

Tim Dernedde, Daniela Thyssens, Lars Schmidt-Thieme

Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim

Recurrent Neural Networks Combinatorial Optimization Neural Encoding Neural Combinatorial Optimization

Aug 11, 2025

Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture

Although the Maximum Clique Problem (MCP) has been extensively studied and features a rich ecosystem of exact solvers, empirical evidence shows that solver performance varies substantially across graph families. Consequently, selecting an appropriate algorithm for a given instance remains an open and practically important challenge that has received little systematic attention. We address this gap by developing an instance-aware selection framework that systematically combines global statistical descriptors with learned topological representations. We construct a comprehensive benchmark by evaluating four state-of-the-art exact solvers on a diverse collection of graph instances and deriving both global statistical and local structural features. An evaluation of conventional classifiers establishes Random Forest as a strong baseline and reveals that connectivity and topological features are key predictors of performance. Motivated by these observations, we introduce a dual-channel architecture that jointly leverages a Graph Attention Network for capturing local neighborhood patterns and a Multilayer Perceptron for modeling global statistical features. Extensive experiments show that the proposed dual-channel model consistently surpasses classical baselines and the single-best solver, achieving 90.43% test accuracy. These findings demonstrate the value of integrating local topological encoding with global statistical cues for combinatorial algorithm selection. Code and models are available at: https://anonymous.4open.science/r/GAT-MLP-7E5F.

Xiang Li, Shanshan Wang, Chenglong Xiao

College of Mathematics and Computer, Shantou University, Shantou, China

Algorithm Selection Combinatorial Optimization

Jun 30, 2025

Flow-Through Tensors: A Unified Computational Graph Architecture for Multi-Layer Transportation Network Optimization

Modern transportation network modeling increasingly involves the integration of diverse methodologies including sensor-based forecasting, reinforcement learning, classical flow optimization, and demand modeling that have traditionally been developed in isolation. This paper introduces Flow Through Tensors (FTT), a unified computational graph architecture that connects origin destination flows, path probabilities, and link travel times as interconnected tensors. Our framework makes three key contributions: first, it establishes a consistent mathematical structure that enables gradient-based optimization across previously separate modeling elements; second, it supports multidimensional analysis of traffic patterns over time, space, and user groups with precise quantification of system efficiency; third, it implements tensor decomposition techniques that maintain computational tractability for large scale applications. These innovations collectively enable real time control strategies, efficient coordination between multiple transportation modes and operators, and rigorous enforcement of physical network constraints. The FTT framework bridges the gap between theoretical transportation models and practical deployment needs, providing a foundation for next generation integrated mobility systems.

Xuesong Zhou, Taehooie Kim, Mostafa Ameli +3

Intelligent Transportation Systems Combinatorial Optimization

Aug 2, 2024

Physics Inspired Neural Networks Enable Efficient Graph Coloring

Combinatorial optimization problems near algorithmic phase transitions represent a fundamental challenge for both classical algorithms and machine learning approaches. Among them, graph coloring is a prototypical constraint satisfaction problem characterized by phase transitions that fragment the solution space into distinct clusters, making the search for valid solutions challenging. Here we introduce a physics-inspired neural framework that learns to solve large-scale graph coloring instances by combining graph neural networks with statistical-mechanics principles. Our approach integrates a planting-based supervised signal, symmetry-breaking regularization, and iterative noise-annealed neural dynamics to navigate complex solution landscapes. When the number of iterations scales quadratically with graph size, the learned solver successfully tackles increasingly challenging instances, even in regimes where finding valid solutions becomes particularly difficult, demonstrating its ability to extract meaningful information from the graph structure. The model generalizes from small training graphs to instances up to 20 times larger, demonstrating that neural architectures can learn scalable algorithmic strategies that remain effective in hard connectivity regions. These results establish a general framework for learning neural solvers that operate near fundamental phase boundaries in combinatorial optimization and inference.

Lorenzo Colantonio, Andrea Cacioppo, Federico Scarpati +3

Department of Physics, Sapienza University of Rome

Combinatorial Optimization Neural Combinatorial Optimization Graph Neural Networks

Jun 9, 2024

Probabilistic Approach to Black-Box Binary Optimization with Budget Constraints: Application to Sensor Placement

This paper presents a fully probabilistic approach for solving optimal experimental design problems under budget constraints. The experimental design is viewed as a random variable and is associated with a parametric conditional distribution that inherently models the budget constraints. The original optimization problem is replaced with an optimization over the expected value of the original objective, which is then optimized over the distribution parameters. The resulting optimal parameter (policy) is used to sample the feasible region of binary space to produce estimates of the optimal solution(s) of the original optimization problem. In this work we extend the family of conditional Bernoulli models to model the random variable conditioned by the total number of nonzero entries, that is, the budget constraint. This approach (a) is generally applicable to binary optimization problems with nonstochastic black-box objective functions and budget constraints; (b) employs conditional probabilities to model and sample only the feasible region and thus considerably reduces the computational cost compared with employing soft constraints; and (c) does not employ soft constraints and thus does not require tuning of a regularization parameter, for example to promote sparsity, which is generally challenging. The proposed approach is verified numerically using an optimal sensor placement experiment based on an advection-diffusion forward model in a parameter identification setup.

Ahmed Attia

Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL, USA

Black-Box Optimization Combinatorial Optimization Bayesian Experimental Design

Jun 9, 2024

GFPack++: Attention-Driven Gradient Fields for Optimizing 2D Irregular Packing

2D irregular packing is a classic combinatorial optimization problem with various applications, such as material utilization and texture atlas generation. Due to its NP-hard nature, conventional numerical approaches typically encounter slow convergence and high computational costs. Previous research (GFPack) introduced a generative method for gradient-based packing, providing early evidence of its feasibility but faced limitations such as insufficient rotation support, poor boundary adaptability, and high overlap ratios. In this paper, we propose GFPack++, a deeply investigated framework that adopts attention-based geometry and relation encoding, enabling more comprehensive modeling of complex packing relationships. We further design a constrained gradient and a weighting function to enhance both the feasibility of the produced solutions and the learning effectiveness. Experimental results on multiple datasets demonstrate that GFPack++ achieves higher space utilization, supports continuous rotation, generalizes well to arbitrary boundaries, and infers orders of magnitude faster than previous approaches. Codes for this paper are at https://github.com/TimHsue/GFPack-pp.

Tianyang Xue, Lin Lu, Yang Liu +5

Shandong University, China · Microsoft Research Asia, China · Peking University, China

Combinatorial Optimization Constrained Optimization Attention Mechanisms Neural Combinatorial Optimization

May 22, 2024

Leader Reward for POMO-Based Neural Combinatorial Optimization

Deep neural networks based on reinforcement learning (RL) for solving combinatorial optimization (CO) problems are developing rapidly and have shown a tendency to approach or even outperform traditional solvers. However, existing methods overlook an important distinction: CO problems differ from other traditional problems in that they focus solely on the optimal solution provided by the model within a specific length of time, rather than considering the overall quality of all solutions generated by the model. In this paper, we propose Leader Reward and apply it during two different training phases of the Policy Optimization with Multiple Optima (POMO) model to enhance the model's ability to generate optimal solutions. This approach is applicable to a variety of CO problems, such as the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Flexible Flow Shop Problem (FFSP), but also works well with other POMO-based models or inference phase's strategies. We demonstrate that Leader Reward greatly improves the quality of the optimal solutions generated by the model. Specifically, we reduce the POMO's gap to the optimum by more than 100 times on TSP100 with almost no additional computational overhead.

Chaoyang Wang, Pengzhi Cheng, Jingze Li +1

Fudan University

Traveling Salesperson Problem Reward Shaping Policy Optimization Combinatorial Optimization RL for Combinatorial Optimization Neural Combinatorial Optimization

Mar 13, 2024

A short review on the maximum clique problem algorithms with classical, AI, and quantum methods

This manuscript provides a comprehensive review of the Maximum Clique Problem, a computational problem that involves finding subsets of vertices in a graph that are all pairwise adjacent to each other. As such, this review is a continuation of the series of previous reviews from 1994, 1999 and 2014. The manuscript covers in a simple way classical algorithms and includes a review of recent developments in graph neural networks and quantum algorithms.

Raffaele Marino, Lorenzo Buffoni, Bogdan Zavalnij

Dipartimento di Fisica e Astronomia Università degli studi di Firenze Via Giovanni Sansone 1, 50019 Sesto Fiorentino, Florence, Italy · HUN-REN Rényi Institute of Mathematics H-1053, Reáltanoda u. 13-15 Budapest, Hungary

Combinatorial Optimization

Feb 2, 2023

Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary

We consider online scheduling on unrelated (heterogeneous) machines in a speed-oblivious setting, where an algorithm is unaware of the exact job-dependent processing speeds. We show strong impossibility results for clairvoyant and non-clairvoyant algorithms and overcome them in models inspired by practical settings: (i) we provide competitive learning-augmented algorithms, assuming that (possibly erroneous) predictions on the speeds are given, and (ii) we provide competitive algorithms for the speed-ordered model, where a single global order of machines according to their unknown job-dependent speeds is known. We prove strong theoretical guarantees and evaluate our findings on a representative heterogeneous multi-core processor. These seem to be the first empirical results for scheduling algorithms with predictions that are evaluated in a non-synthetic hardware environment.

Alexander Lindermayr, Nicole Megow, Martin Rapp

University of Bremen, Faculty of Mathematics and Computer Science, Germany · Faculty for Informatics, Karlsruhe Institute of Technology, Germany

Combinatorial Optimization Learning-Augmented Algorithms Heterogeneous Computing

Jun 14, 2017

Context-Aware System Synthesis, Task Assignment, and Routing

The design and organization of complex robotic systems traditionally requires laborious trial-and-error processes to ensure both hardware and software components are correctly connected with the resources necessary for computation. This paper presents a novel generalization of the quadratic assignment and routing problem, introducing formalisms for selecting components and interconnections to synthesize a complete system capable of providing some user-defined functionality. By introducing mission context, functional requirements, and modularity directly into the assignment problem, we derive a solution where components are automatically selected and then organized into an optimal hardware and software interconnection structure, all while respecting restrictions on component viability and required functionality. The ability to generate complete functional systems directly from individual components reduces manual design effort by allowing for a guided exploration of the design space. Additionally, our formulation increases resiliency by quantifying resource margins and enabling adaptation of system structure in response to changing environments, hardware or software failure. The proposed formulation is cast as an integer linear program which is provably

\mathcal{NP}

-hard. Two case studies are developed and analyzed to highlight the expressiveness and complexity of problems that can be addressed by this approach: the first explores the iterative development of a ground-based search-and-rescue robot in a variety of mission contexts, while the second explores the large-scale, complex design of a humanoid disaster robot for the DARPA Robotics Challenge. Numerical simulations quantify real world performance and demonstrate tractable time complexity for the scale of problems encountered in many modern robotic systems.

Jason Ziglar, Ryan Williams, Alfred Wicks

Combinatorial Optimization Robotics Hardware-Software Co-Design Integer Linear Programming