Combinatorial Optimization

Ask about this topic

Overview

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

CardsList

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

Mar 17, 2026

Scalable Inspection Planning via Flow-based Mixed Integer Linear Programming

Inspection planning is concerned with computing the shortest robot path to inspect a given set of points of interest (POIs) using the robot's sensors. This problem arises in a wide range of applications from manufacturing to medical robotics. To alleviate the problem's complexity, recent methods rely on sampling-based methods to obtain a more manageable (discrete) graph inspection planning (GIP) problem. Unfortunately, GIP still remains highly difficult to solve at scale as it requires simultaneously satisfying POI-coverage and path-connectivity constraints, giving rise to a challenging optimization problem, particularly at scales encountered in real-world scenarios. In this work, we present highly scalable Mixed Integer Linear Programming (MILP) solutions for GIP that significantly advance the state-of-the-art in both runtime and solution quality. Our key insight is a reformulation of the problem's core constraints as a network flow, which enables effective MILP models and a specialized Branch-and-Cut solver that exploits the combinatorial structure of flows. We evaluate our approach on medical and infrastructure benchmarks alongside large-scale synthetic instances. Across all scenarios, our method produces substantially tighter lower bounds than existing formulations, reducing optimality gaps by 30-50% on large instances. Furthermore, our solver demonstrates unprecedented scalability: it provides non-trivial solutions for problems with up to 15,000 vertices and thousands of POIs, where prior state-of-the-art methods typically exhaust memory or fail to provide any meaningful optimality guarantees.

Adir Morgan, Kiril Solovey, Oren Salzman

Technion–Israel Institute of Technology, Haifa, Israel

Robotic InspectionCombinatorial OptimizationMixed-Integer Linear Programming
AskPDF
Mar 17, 2026

Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling

The dynamic multi-mode resource-constrained project scheduling problem (DMRCPSP) is of practical importance, as it requires making real-time decisions under changing project states and resource availability. Genetic Programming (GP) has been shown to effectively evolve heuristic rules for such decision-making tasks; however, the evolutionary process typically relies on a large number of simulation-based fitness evaluations, resulting in high computational cost. Surrogate models offer a promising solution to reduce evaluation cost, but their application to GP requires problem-specific phenotypic characterisation (PC) schemes of heuristic rules. There is currently a lack of suitable PC schemes for GP applied to DMRCPSP. This paper proposes a rank-based PC scheme derived from heuristic-driven ordering of eligible activity-mode pairs and activity groups in decision situations. The resulting PC vectors enable a surrogate model to estimate the fitness of unevaluated GP individuals. Based on this scheme, a surrogate-assisted GP algorithm is developed. Experimental results demonstrate that the proposed surrogate-assisted GP can identify high-quality heuristic rules consistently earlier than the state-of-the-art GP approach for DMRCPSP, while introducing only marginal computational overhead. Further analyses demonstrate that the surrogate model provides useful guidance for offspring selection, leading to improved evolutionary efficiency.

Yuan Tian, Yi Mei, Mengjie Zhang

Centre for Data Science and Artificial Intelligence & School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand

Resource-Constrained Project SchedulingGenetic ProgrammingCombinatorial OptimizationSurrogate-Assisted OptimizationSurrogate Modeling
AskPDF
Mar 17, 2026

A General Deep Learning Framework for Wireless Resource Allocation under Discrete Constraints

While deep learning (DL)-based methods have achieved remarkable success in continuous wireless resource allocation, efficient solutions for problems involving discrete variables remain challenging. This is primarily due to the zero-gradient issue in backpropagation, the difficulty of enforcing intricate constraints with discrete variables, and the inability in generating solutions with non-same-parameter-same-decision (non-SPSD) property. To address these challenges, this paper proposes a general DL framework by introducing the support set to represent the discrete variables. We model the elements of the support set as random variables and learn their joint probability distribution. By factorizing the joint probability as the product of conditional probabilities, each conditional probability is sequentially learned. This probabilistic modeling directly tackles all the aforementioned challenges of DL for handling discrete variables. By operating on probability distributions instead of hard binary decisions, the framework naturally avoids the zero-gradient issue. During the learning of the conditional probabilities, discrete constraints can be seamlessly enforced by masking out infeasible solutions. Moreover, with a dynamic context embedding that captures the evolving discrete solutions, the non-SPSD property is inherently provided by the proposed framework. We apply the proposed framework to two representative mixed-discrete wireless resource allocation problems: (a) joint user association and beamforming in cell-free systems, and (b) joint antenna positioning and beamforming in movable antenna-aided systems. Simulation results demonstrate that the proposed DL framework consistently outperforms existing baselines in terms of both system performance and computational efficiency.

Yikun Wang, Yang Li, Yik-Chung Wu +1

Department of Electrical and Electronic Engineering, The University of Hong Kong, Hong Kong · School of Computing and Information Technology, Great Bay University, Dongguan 523000, China · Department of Electrical and Computer Engineering, National University of Singapore, Singapore

Wireless Resource AllocationWireless CommunicationsCombinatorial Optimization
AskPDF
Mar 16, 2026

Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks

Complex real-world optimization problems often involve both discrete decisions and nonlinear relationships between variables. Many such problems can be modeled as polynomial-objective integer programs, encompassing cases with quadratic and higher-degree variable interactions. Nonlinearity makes them more challenging than their linear counterparts. In this paper, we propose a hypergraph neural network (HNN) based method to solve polynomial-objective integer programming (POIP). Besides presenting a high-degree-term-aware hypergraph representation to capture both high-degree information and variable-constraint interdependencies, we also propose a hypergraph neural network, which integrates convolution between variables and high-degree terms alongside convolution between variables and constraints, to predict solution values. Finally, a search process initialized from the predicted solutions is performed to further refine the results. Comprehensive experiments across a range of benchmarks demonstrate that our method consistently outperforms both existing learning-based approaches and state-of-the-art solvers, delivering superior solution quality with favorable efficiency. Note that our experiments involve both polynomial objectives and constraints, demonstrating our HNN's versatility for general POIP problems and highlighting its advancement over the existing literature.

Minshuo Li, Yaoxin Wu, Pavel Troubil +2

Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, the Netherlands · Eindhoven Artificial Intelligence Systems Institute, Eindhoven University of Technology, Eindhoven, the Netherlands · Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, Eindhoven, the Netherlands +1

Combinatorial OptimizationNeural Combinatorial OptimizationHypergraph Neural Networks
AskPDF
Mar 12, 2026

UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization

Unsupervised neural combinatorial optimization (NCO) offers an appealing alternative to supervised approaches by training learning-based solvers without ground-truth solutions, directly minimizing instance objectives and constraint violations. Yet for graph node subset-selection problems (e.g., Maximum Clique and Maximum Independent Set), existing unsupervised methods are typically specialized to a single problem class and rely on problem-specific surrogate losses, which hinders learning across classes within a unified framework. In this work, we propose UniHetCO, a unified heterogeneous graph representation for constrained quadratic programming-based combinatorial optimization that encodes problem structure, objective terms, and linear constraints in a single input. This formulation enables training a single model across multiple problem classes with a unified label-free objective. To improve stability under multi-problem learning, we employ a gradient-norm-based dynamic weighting scheme that alleviates gradient imbalance among classes. Experiments on multiple datasets and four constrained problem classes demonstrate competitive performance with state-of-the-art unsupervised NCO baselines, strong cross-problem adaptation potential, and effective warm starts for a commercial classical solver under tight time limits.

Kien X. Nguyen, Ilya Safro

Department of Computer and Information Sciences, University of Delaware, Newark DE 19716, USA

Combinatorial OptimizationNeural Combinatorial OptimizationConstrained OptimizationHeterogeneous GNNs
AskPDF
Mar 10, 2026

Algebraic Structure Discovery for Real World Combinatorial Optimisation Problems: A General Framework from Abstract Algebra to Quotient Space Learning

Many combinatorial optimisation problems hide algebraic structures that, once exposed, shrink the search space and improve the chance of finding the global optimal solution. We present a general framework that (i) identifies algebraic structure, (ii) formalises operations, (iii) constructs quotient spaces that collapse redundant representations, and (iv) optimises directly over these reduced spaces. Across a broad family of rule-combination tasks (e.g., patient subgroup discovery and rule-based molecular screening), conjunctive rules form a monoid. Via a characteristic-vector encoding, we prove an isomorphism to the Boolean hypercube {0,1}n\{0,1\}^n with bitwise OR, so logical AND in rules becomes bitwise OR in the encoding. This yields a principled quotient-space formulation that groups functionally equivalent rules and guides structure-aware search. On real clinical data and synthetic benchmarks, quotient-space-aware genetic algorithms recover the global optimum in 48% to 77% of runs versus 35% to 37% for standard approaches, while maintaining diversity across equivalence classes. These results show that exposing and exploiting algebraic structure offers a simple, general route to more efficient combinatorial optimisation.

Min Sun, Federica Storti, Valentina Martino +2

F. Hoffmann-La Roche AG, Roche Pharma Research and Early Development

Combinatorial Optimization
AskPDF
Mar 9, 2026

Cluster-Aware Attention-Based Deep Reinforcement Learning for Pickup and Delivery Problems

The Pickup and Delivery Problem (PDP) is a fundamental and challenging variant of the Vehicle Routing Problem, characterized by tightly coupled pickup--delivery pairs, precedence constraints, and spatial layouts that often exhibit clustering. Existing deep reinforcement learning (DRL) approaches either model all nodes on a flat graph, relying on implicit learning to enforce constraints, or achieve strong performance through inference-time collaborative search at the cost of substantial latency. In this paper, we propose CAADRL (Cluster-Aware Attention-based Deep Reinforcement Learning), a DRL framework that explicitly exploits the multi-scale structure of PDP instances via cluster-aware encoding and hierarchical decoding. The encoder builds on a Transformer and combines global self-attention with intra-cluster attention over depot, pickup, and delivery nodes, producing embeddings that are both globally informative and locally role-aware. Based on these embeddings, we introduce a Dynamic Dual-Decoder with a learnable gate that balances intra-cluster routing and inter-cluster transitions at each step. The policy is trained end-to-end with a POMO-style policy gradient scheme using multiple symmetric rollouts per instance. Experiments on synthetic clustered and uniform PDP benchmarks show that CAADRL matches or improves upon strong state-of-the-art baselines on clustered instances and remains highly competitive on uniform instances, particularly as problem size increases. Crucially, our method achieves these results with substantially lower inference time than neural collaborative-search baselines, suggesting that explicitly modeling cluster structure provides an effective and efficient inductive bias for neural PDP solvers.

Wentao Wang, Lifeng Han, Guangyu Zou

Leicester International Institute, Dalian University of Technology, Panjin, 124221, Liaoning, China. · Department of Electronic and Information Technology, Dalian University of Technology, Panjin, 124221, Liaoning, China.

Vehicle RoutingRL for Combinatorial OptimizationNeural Combinatorial OptimizationCombinatorial OptimizationAttention Mechanisms
AskPDF
Mar 9, 2026

Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions

The multiple-choice knapsack problem (MCKP) is a classic combinatorial optimization with wide practical applications. This paper investigates a significant yet underexplored extension of MCKP: the multi-objective chance-constrained MCKP (MO-CCMCKP) under implicit probability distributions. The goal of the problem is to simultaneously minimize the total cost and maximize the confidence level of satisfying the capacity constraint, capturing essential trade-offs in domains like 5G network configuration. To address the computational challenge of evaluating chance constraints under implicit distributions, we first propose an order-preserving efficient resource allocation Monte Carlo (OPERA-MC) method. This approach adaptively allocates sampling resources to preserve dominance relationships while reducing evaluation time significantly. Further, we develop NHILS, a hybrid evolutionary algorithm that integrates specialized initialization and local search into NSGA-II to navigate sparse feasible regions. Experiments on synthetic benchmarks and real-world 5G network configuration benchmarks demonstrate that NHILS consistently outperforms several state-of-the-art multi-objective optimizers in convergence, diversity, and feasibility. The benchmark instances and source code will be made publicly available to facilitate research in this area.

Xuanfeng Li, Shengcai Liu, Wenjie Chen +2

Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China · School of Information Management, Central China Normal University, Wuhan 430079, China · Centre for Frontier AI Research, Institute of High Performance Computing, Agency for Science Technology and Research, Singapore 138632 +1

Chance-Constrained OptimizationCombinatorial OptimizationStochastic OptimizationMulti-Objective Evolutionary Optimization
AskPDF
Mar 8, 2026

Column Generation for the Micro-Transit Zoning Problem

Along with the rapid development of new urban mobility options like ride-sharing over the past decade, on-demand micro-transit services stand out as a middle ground, bridging the gap between fixed-line mass transit and single-request ride-hailing, balancing ridership maximization and travel time minimization. Micro-transit adoption can have significant social impact. It improves urban sustainability, through lower energy consumption and reduced emissions, while enhancing equitable mobility access for disadvantaged communities, thanks to its lower vehicle miles per passenger, flexible schedules, and affordable pricing. However, effective operation of micro-transit services requires planning geo-fenced zones in advance, which involves solving a challenging combinatorial optimization problem. Existing approaches enumerate candidate zones first and selects a fixed number of optimal zones in the second step. In this paper, we generalize the Micro-Transit Zoning Problem (MZP) to allow a global budget rather than imposing a size limit for candidate zones. We also design a Column Generation (CG) framework to solve the problem and several pricing heuristics to accelerate computation. Extensive numerical experiments across major U.S. cities demonstrate that our approach produces higher-quality solutions more efficiently and scales better in the generalized setting.

Hins Hu, Rishav Sen, Jose Paolo Talusan +3

Cornell University · Vanderbilt University · Pennsylvania State University

Combinatorial OptimizationUrban Planning
AskPDF
Mar 8, 2026

Large Language Model for Discrete Optimization Problems: Evaluation and Step-by-step Reasoning

This work investigated the capabilities of different models, including the Llama-3 series of models and CHATGPT, with different forms of expression in solving discrete optimization problems by testing natural language datasets. In contrast to formal datasets with a limited scope of parameters, our dataset included a variety of problem types in discrete optimization problems and featured a wide range of parameter magnitudes, including instances with large parameter sets, integrated with augmented data. It aimed to (1) provide an overview of LLMs' ability in large-scale problems, (2) offer suggestions to those who want to solve discrete optimization problems automatically, and (3) regard the performance as a benchmark for future research. These datasets included original, expanded and augmented datasets. Among these three datasets, the original and augmented ones aimed for evaluation while the expanded one may help finetune a new model. In the experiment, comparisons were made between strong and week models, CoT methods and No-CoT methods on various datasets. The result showed that stronger model performed better reasonably. Contrary to general agreement, it also showed that CoT technique was not always effective regarding the capability of models and disordered datasets improved performance of models on easy to-understand problems, even though they were sometimes with high variance, a manifestation of instability. Therefore, for those who seek to enhance the automatic resolution of discrete optimization problems, it is recommended to consult the results, including the line charts presented in the Appendix, as well as the conclusions drawn in this study for relevant suggestions.

Tianhao Qian, Guilin Qi, Z. Y. Wu +3

School of Mathematics, Southeast University, Nanjing, China · School of Computer Science and Engineering, Southeast University, Nanjing, China · School of Mathematical Sciences, Chongqing Normal University, Chongqing, China

LLM EvaluationLarge Language Model-Guided OptimizationCombinatorial OptimizationCoT Reasoning
AskPDF
Mar 8, 2026

CDEoH: Category-Driven Automatic Algorithm Design With Large Language Models

With the rapid advancement of large language models (LLMs), LLM-based heuristic search methods have demonstrated strong capabilities in automated algorithm generation. However, their evolutionary processes often suffer from instability and premature convergence. Existing approaches mainly address this issue through prompt engineering or by jointly evolving thought and code, while largely overlooking the critical role of algorithmic category diversity in maintaining evolutionary stability. To this end, we propose Category Driven Automatic Algorithm Design with Large Language Models (CDEoH), which explicitly models algorithm categories and jointly balances performance and category diversity in population management, enabling parallel exploration across multiple algorithmic paradigms. Extensive experiments on representative combinatorial optimization problems across multiple scales demonstrate that CDEoH effectively mitigates convergence toward a single evolutionary direction, significantly enhancing evolutionary stability and achieving consistently superior average performance across tasks and scales.

Yu-Nian Wang, Shen-Huan Lyu, Ning Chen +3

Key Laboratory of Water Big Data Technology of Ministry of Water Resources, College of Computer Science and Software Engineering, Hohai University, Nanjing, China · Department of Computer Science, City University of Hong Kong, Hong Kong, China · State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China

Automated Heuristic DesignAutomated Algorithm DiscoveryLarge Language Model-Guided OptimizationEvolutionary OptimizationCombinatorial Optimization
AskPDF
Mar 7, 2026

DyACE: Dynamic Algorithm Co-evolution for Online Automated Heuristic Design with Large Language Model

The prevailing paradigm in Automated Heuristic Design (AHD) typically relies on the assumption that a single, fixed algorithm can effectively navigate the shifting dynamics of a combinatorial search. This static approach often proves inadequate for Perturbative Heuristics, where the optimal algorithm for escaping local optima depends heavily on the specific search phase. To address this limitation, we reformulate heuristic design as a Non-stationary Bi-level Control problem and introduce DyACE (Dynamic Algorithm Co-evolution). Distinct from standard open-loop solvers, DyACE use a Receding Horizon Control architecture to continuously co-evolve the heuristic logic alongside the solution population. A core element of this framework is the Look-Ahead Rollout Search, which queries the landscape geometry to extract Search Trajectory Features. This sensory feedback allows the Large Language Model (LLM) to function as a grounded meta-controller, prescribing phase-specific interventions tailored to the real-time search status. We validate DyACE on three representative combinatorial optimization benchmarks. The results demonstrate that our method significantly outperforms state-of-the-art static baselines, exhibiting superior scalability in high-dimensional search spaces. Furthermore, ablation studies confirm that dynamic adaptation fails without grounded perception, often performing worse than static algorithms. This indicates that DyACE's effectiveness stems from the causal alignment between the synthesized logic and the verified gradients of the optimization landscape.

Guidong Lu, Yiping Liu, Xiangxiang Zeng

Automated Heuristic DesignCombinatorial OptimizationLarge Language Model-Guided Optimization
AskPDF
Mar 7, 2026

RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States

Neural approaches to the Flexible Job Shop Scheduling Problem (FJSP), particularly those based on deep reinforcement learning (DRL), have gained growing attention in recent years. However, existing methods rely on complex feature-engineered state representations (i.e., often requiring more than 20 handcrafted features) and graph-biased neural architectures. To reduce modeling complexity and advance a more generalizable framework for FJSP, we introduce ReSched, a minimalist DRL framework that rethinks both the scheduling formulation and model design. First, by revisiting the Markov Decision Process (MDP) formulation of FJSP, we condense the state space to just four essential features, eliminating historical dependencies through a subproblem-based perspective. Second, we employ Transformer blocks with dot-product attention, augmented by three lightweight but effective architectural modifications tailored to scheduling tasks. Extensive experiments show that ReSched outperforms classical dispatching rules and state-of-the-art DRL methods on FJSP. Moreover, ReSched also generalizes well to the Job Shop Scheduling Problem (JSSP) and the Flexible Flow Shop Scheduling Problem (FFSP), achieving competitive performance against neural baselines specifically designed for these variants.

Xiangjie Xiao, Cong Zhang, Wen Song +1

School of Computing and Information Systems, Singapore Management University, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Marine Science and Technology, Shandong University, China

Flexible Job Shop SchedulingJob Shop SchedulingCombinatorial OptimizationRL for Combinatorial OptimizationTransformer-Based RLState Representation Learning
AskPDF
Mar 6, 2026

Learning to Solve Orienteering Problem with Time Windows and Variable Profits

The orienteering problem with time windows and variable profits (OPTWVP) is common in many real-world applications and involves continuous time variables. Current approaches fail to develop an efficient solver for this orienteering problem variant with discrete and continuous variables. In this paper, we propose a learning-based two-stage DEcoupled discrete-Continuous optimization with Service-time-guided Trajectory (DeCoST), which aims to effectively decouple the discrete and continuous decision variables in the OPTWVP problem, while enabling efficient and learnable coordination between them. In the first stage, a parallel decoding structure is employed to predict the path and the initial service time allocation. The second stage optimizes the service times through a linear programming (LP) formulation and provides a long-horizon learning of structure estimation. We rigorously prove the global optimality of the second-stage solution. Experiments on OPTWVP instances demonstrate that DeCoST outperforms both state-of-the-art constructive solvers and the latest meta-heuristic algorithms in terms of solution quality and computational efficiency, achieving up to 6.6x inference speedup on instances with fewer than 500 nodes. Moreover, the proposed framework is compatible with various constructive solvers and consistently enhances the solution quality for OPTWVP.

Songqun Gao, Zanxi Ruan, Patrick Floor +3

Department of Industrial Engineering, Università di Trento, Trento, Italy · Interdepartmental Robotics Labs (IDRA), Trento, Italy · Department of Engineering for Innovation Medicine, Università di Verona, Verona, Italy +2

Learning to OptimizeCombinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Mar 5, 2026

MIRACL: A Diverse Meta-Reinforcement Learning for Multi-Objective Multi-Echelon Combinatorial Supply Chain Optimisation

Multi-objective reinforcement learning (MORL) is effective for multi-echelon combinatorial supply chain optimisation, where tasks involve high dimensionality, uncertainty, and competing objectives. However, its deployment in dynamic environments is hindered by the need for task-specific retraining and substantial computational cost. We introduce MIRACL (Meta multI-objective Reinforcement leArning with Composite Learning), a hierarchical Meta-MORL framework that allows for a few-shot generalisation across diverse tasks. MIRACL decomposes each task into structured subproblems for efficient policy adaptation and meta-learns a global policy across tasks using a Pareto-based adaptation strategy to encourage diversity in meta-training and fine-tuning. To our knowledge, this is the first integration of Meta-MORL with such mechanisms in combinatorial optimisation. Although validated in the supply chain domain, MIRACL is theoretically domain-agnostic and applicable to broader dynamic multi-objective decision-making problems. Empirical evaluations show that MIRACL outperforms conventional MORL baselines in simple to moderate tasks, achieving up to 10% higher hypervolume and 5% better expected utility. These results underscore the potential of MIRACL for robust, efficient adaptation in multi-objective problems.

Rifny Rachman, Josh Tingey, Richard Allmendinger +3

The University of Manchester, United Kingdom · Peak AI, Ltd, United Kingdom

Supply Chain OptimizationMulti-Objective Reinforcement LearningMeta-Reinforcement LearningRL for Combinatorial OptimizationCombinatorial OptimizationHierarchical RL
AskPDF
Mar 5, 2026

Agentic Service Markets Across the Computing Continuum: A Polymatroidal Architecture

Autonomous AI agents are becoming economic actors. They compose deadline-bound services across the device-edge-cloud continuum and contend for capacity no single operator owns. This article asks when decentralised pricing can coordinate them exactly and truthfully, and what their service dependencies must satisfy. We model the pipelines as service-dependency graphs under governance constraints and identify the decisive property: laminarity of the induced leaf-block family. Where it holds, the feasible allocation space is a polymatroid and efficient incentive-compatible clearing exists per epoch; where a crossing breaks it, exactness and truthfulness can fail, while clearing prices survive on every totally unimodular family. The formal results instantiate polymatroid, gross-substitutes and Vickrey-Clarke-Groves theory; the contribution is the bridge from dependency structure to that machinery and an integrator architecture that exposes a laminar interface. The node-level evaluation (32,020 runs), at testbed-calibrated congestion, locates the boundary. One crossing costs exactness in 14.7% of high-load rounds and none on laminar instances, and truthfulness fails where exactness does, across contention. An integrator's inner exposure restores exactness at a cost in admitted volume, and before translation overhead it cuts median latency by 16 to 17 percent. Against truth-free posted prices the tuned market leads at medium load and trails a demand-responsive one in four of six high-load cells. Recorded and composed agent workloads drive the allocation. For platform designers, laminar pipelines admit exact decentralised pricing, truthful under the VCG mechanism, and a crossing needs an integrator's inner exposure.

Lauri Lovén, Alaa Saleh, Reza Farahani +5

Future Computing Group, University of Oulu, Finland · Distributed Systems Group, TU Wien, Vienna, Austria · Department of Mechatronics, University of Prishtina, Kosova +4

Mechanism DesignCombinatorial OptimizationDynamic Pricing
AskPDF
Mar 5, 2026

ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback

Designing effective heuristics for NP-hard combinatorial optimization problems remains challenging and often requires substantial domain expertise. Recent LLM-guided evolutionary methods have shown promise for automated heuristic generation, but most existing approaches refine heuristics independently or through limited pairwise feedback. We propose ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback, a framework for group-wise multi-turn heuristic refinement. ReVEL organizes heuristics into behavior-aware reflective groups, including similarity-driven groups for localized refinement and diversity-driven groups for exploratory search. Within each group, the LLM performs iterative multi-turn refinement using accumulated performance feedback, enabling related heuristics to be jointly analyzed and progressively improved across evolutionary iterations. Experiments on standard combinatorial optimization benchmarks show that ReVEL generally improves optimization performance over existing LLM-guided evolutionary baselines across multiple settings and LLM backbones. Additional analyses suggest that behavior-aware grouping contributes to more consistent refinement trajectories during iterative heuristic evolution.

Cuong Van Duc, Minh Nguyen Dinh Tuan, Tam Vu Duc +4

VinMotion · Hanoi University of Science and Technology · VinUniversity +2

Automated Heuristic DesignLarge Language Model-Guided OptimizationEvolutionary OptimizationCombinatorial OptimizationLLM Self-Refinement
AskPDF
Mar 3, 2026

Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling

The rise of smart manufacturing under Industry 4.0 introduces mass customization and dynamic production, demanding more advanced and flexible scheduling techniques. The flexible job-shop scheduling problem (FJSP) has attracted significant attention due to its complex constraints and strong alignment with real-world production scenarios. Current deep reinforcement learning (DRL)-based approaches to FJSP predominantly employ constructive methods. While effective, they often fall short of reaching (near-)optimal solutions. In contrast, improvement-based methods iteratively explore the neighborhood of initial solutions and are more effective in approaching optimality. However, the flexible machine allocation in FJSP poses significant challenges to the application of this framework, including accurate state representation, effective policy learning, and efficient search strategies. To address these challenges, this paper proposes a Memory-enhanced Improvement Search framework with heterogeneous graph representation--MIStar. It employs a novel heterogeneous disjunctive graph that explicitly models the operation sequences on machines to accurately represent scheduling solutions. Moreover, a memoryenhanced heterogeneous graph neural network (MHGNN) is designed for feature extraction, leveraging historical trajectories to enhance the decision-making capability of the policy network. Finally, a parallel greedy search strategy is adopted to explore the solution space, enabling superior solutions with fewer iterations. Extensive experiments on synthetic data and public benchmarks demonstrate that MIStar significantly outperforms both traditional handcrafted improvement heuristics and state-of-the-art DRL-based constructive methods.

Jiaqi Wang, Zhiguang Cao, Peng Zhao +4

Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University · College of Software, Jilin University · Singapore Management University +2

Flexible Job Shop SchedulingJob Shop SchedulingCombinatorial OptimizationRL for Combinatorial OptimizationHeterogeneous GNNs
AskPDF
Feb 28, 2026

Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity

The Moving Target Vehicle Routing Problem (MT-VRP) seeks trajectories for several agents that intercept a set of moving targets, subject to speed, time window, and capacity constraints. We introduce an exact algorithm, Branch-and-Price with Relaxed Continuity (BPRC), for the MT-VRP. The main challenge in a branch-and-price approach for the MT-VRP is the pricing subproblem, which is complicated by moving targets and time-dependent travel costs between targets. Our key contribution is a new labeling algorithm that solves this subproblem by means of a novel dominance criterion tailored for problems with moving targets. Numerical results on instances with up to 25 targets show that our algorithm finds optimal solutions more than an order of magnitude faster than a baseline based on previous work, showing particular strength in scenarios with limited agent capacities.

Anoop Bhat, Geordan Gutow, Zhongqiang Ren +2

Robotics Institute at Carnegie Mellon University, Pittsburgh, PA 15213 · Mechanical and Aerospace Engineering at Michigan Technological University, Houghton, MI 49931 · UM-SJTU Joint Institute and Department of Automation at Shanghai Jiao Tong University, Shanghai, China +1

Vehicle RoutingCombinatorial Optimization
AskPDF
Feb 27, 2026

Universal NP-Hardness of Clustering under General Utilities

Clustering is a central primitive in unsupervised learning, yet practice is dominated by heuristics whose outputs can be unstable and highly sensitive to representations, hyperparameters, and initialisation. Existing theoretical results are largely objective-specific and do not explain these behaviours at a unifying level. We formalise the common optimisation core underlying diverse clustering paradigms by defining the Universal Clustering Problem (UCP): the maximisation of a polynomial-time computable partition utility over a finite metric space. We prove the NP-hardness of UCP via two independent polynomial-time reductions from graph colouring and from exact cover by 3-sets (X3C). By mapping ten major paradigms -- including k-means, GMMs, DBSCAN, spectral clustering, and affinity propagation -- to the UCP framework, we demonstrate that each inherits this fundamental intractability. Our results provide a unified explanation for characteristic failure modes, such as local optima in alternating methods and greedy merge-order traps in hierarchical clustering. Finally, we show that clustering limitations reflect interacting computational and epistemic constraints, motivating a shift toward stability-aware objectives and interaction-driven formulations with explicit guarantees.

Angshul Majumdar

Indraprastha Institute of Information Technology, New Delhi, India

ClusteringUnsupervised ClusteringCombinatorial Optimization
AskPDF
Feb 25, 2026

Mamba Meets Scheduling: Learning to Solve Flexible Job Shop Scheduling with Efficient Sequence Modeling

The Flexible Job Shop Problem (FJSP) is a well-studied combinatorial optimization problem with extensive applications for manufacturing and production scheduling. It involves assigning jobs to various machines to optimize criteria, such as minimizing total completion time. Current learning-based methods in this domain often rely on localized feature extraction models, limiting their capacity to capture overarching dependencies spanning operations and machines. This paper introduces an innovative architecture that harnesses Mamba, a state-space model with linear computational complexity, to facilitate comprehensive sequence modeling tailored for FJSP. In contrast to prevalent graph-attention-based frameworks that are computationally intensive for FJSP, we show our model is more efficient. Specifically, the proposed model possesses an encoder and a decoder. The encoder incorporates a dual Mamba block to extract operation and machine features separately. Additionally, we introduce an efficient cross-attention decoder to learn interactive embeddings of operations and machines. Our experimental results demonstrate that our method achieves faster solving speed and surpasses the performance of state-of-the-art learning-based methods for FJSP across various benchmarks.

Zhi Cao, Cong Zhang, Yaoxin Wu +2

Dalian University of Technology, Dalian, China · Nanyang Technological University, Singapore · Eindhoven University of Technology, Eindhoven, the Netherlands

Flexible Job Shop SchedulingJob Shop SchedulingCombinatorial OptimizationNeural Combinatorial Optimization
AskPDF
Feb 25, 2026

Code World Models for Parameter Control in Evolutionary Algorithms

Can an LLM learn how an optimizer behaves -- and use that knowledge to control it? We extend Code World Models (CWMs), LLM-synthesized Python programs that predict environment dynamics, from deterministic games to stochastic combinatorial optimization. Given suboptimal trajectories of (1+1)(1{+}1)-RLSk\text{RLS}_k, the LLM synthesizes a simulator of the optimizer's dynamics; greedy planning over this simulator then selects the mutation strength kk at each step. On \lo{} and \onemax{}, CWM-greedy performs within 6% of the theoretically optimal policy -- without ever seeing optimal-policy trajectories. On \jump{k_k}, where a deceptive valley causes all adaptive baselines to fail (0% success rate), CWM-greedy achieves 100% success rate -- without any collection policy using oracle knowledge of the gap parameter. On the NK-Landscape, where no closed-form model exists, CWM-greedy outperforms all baselines across fifteen independently generated instances (36.9436.94 vs.\ 36.3236.32; p<0.001p<0.001) when the prompt includes empirical transition statistics. The CWM also outperforms DQN in sample efficiency (200 offline trajectories vs.\ 500 online episodes), success rate (100% vs.\ 58%), and generalization (k=3k{=}3: 78% vs.\ 0%). Robustness experiments confirm stable synthesis across 5 independent runs.

Camilo Chacón Sartori, Guillem Rodríguez Corominas

ICN2 – Catalan Institute of Nanoscience and Nanotechnology, Barcelona, Spain · Artificial Intelligence Research Institute (IIIA-CSIC), Barcelona, Spain · Universitat Politècnica de Catalunya (UPC), Barcelona, Spain

Code World ModelsLarge Language Model-Guided OptimizationLLMs for Evolutionary OptimizationWorld ModelsEvolutionary OptimizationCombinatorial Optimization
AskPDF
Feb 24, 2026

Precedence-Constrained Decision Trees and Coverings

This work considers a number of optimization problems and reductive relations between them. The two main problems we are interested in are the Optimal Decision Tree and Set Cover. We study these two fundamental tasks under precedence constraints, that is, if a test (or set) XX is a predecessor of YY, then in any feasible decision tree XX needs to be an ancestor of YY (or respectively, if YY is added to set cover, then so must be XX). For the Optimal Decision Tree we consider two optimization criteria: worst case identification time (height of the tree) or the average identification time. Similarly, for the Set Cover we study two cost measures: the size of the cover or the average cover time. Our approach is to develop a number of algorithmic reductions, where an approximation algorithm for one problem provides an approximation for another via a black-box usage of a procedure for the former. En route we introduce other optimization problems either to complete the `reduction landscape' or because they hold the essence of combinatorial structure of our problems. The latter is brought by a problem of finding a Maximum Density Precedence-Closed Subfamily, where the density is defined as the ratio of the number of items the family covers to its size. We provide O∗(m)\mathcal{O}^*(\sqrt{m})-approximation polynomial-time algorithms for all aforementioned problems. The picture is complemented by a number of hardness reductions that provide O(m1/12−ε)\mathcal{O}(m^{1/12-ε})-inapproximability results for the decision tree and covering problems. Besides giving a complete set of results for general precedence constraints, we also provide polylogarithmic approximation guarantees for two most typically studied and applicable graph types, outforests and inforests. By providing corresponding hardness results, we show most of these results to be tight.

Michał Szyfelbein, Dariusz Dereniowski

Gdańsk University of Technology, 80-233 Gdańsk, Poland

Combinatorial OptimizationConstrained OptimizationApproximation Algorithms
AskPDF
Feb 23, 2026

Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

We study the problem of maximizing a complex-valued quadratic form over the KthK^{\text{th}} roots of unity. We show that when the objective matrix Q⋆∈Cn×n\mathbf{Q}^\star \in \mathbb{C}^{n \times n} of the quadratic has rank rr, the global maximizer belongs to a candidate set of size O(rn2r−1)O(rn^{2r-1}). This set can be constructed deterministically in O(rn2r+1)O(rn^{2r+1}) time by enumerating the vertices of a hyperplane arrangement in R2r.\mathbb{R}^{2r}. The algorithm is embarrassingly parallel; with~PP processors, the time complexity drops to O(rn2r+1/P)O(r n^{2r+1}/P). For approximately low-rank settings, where the objective matrix is a noise-perturbed variant of a rank-rr matrix, we prove that applying our framework to a spectral truncation yields a multiplicative (1−O(∥H∥2/δ⋆))(1 - O(\left\|\mathbf{H}\right\|_2 / δ^{\star}))-approximation guarantee, where δ⋆δ^{\star} denotes the eigengap of the underlying rank-rr matrix and H\mathbf{H} represents the perturbation. To scale to high-dimensional problems, we establish a randomized sampling variant. We prove that uniformly sampling S≥O(1/εr−1)S \geq O(1/\varepsilon^{r-1}) candidates achieves a (1−ε)cos⁡2(π/K)(1-\varepsilon)\cos^2(π/ K)-approximation of the optimal rank-rr solution with high probability. Crucially, this sample size is entirely independent of nn, reducing the overall runtime to O(S⋅n2)O(S \cdot n^2). Computational experiments on synthetic benchmarks and large-scale graphs for Max-3-Cut confirm that our algorithms match or exceed semi-definite programming solution quality on structured instances while enabling massive parallelization across heterogeneous hardware and scaling seamlessly to problems where n≥106n \geq 10^6.

Ria Stevens, Fangshuo Liao, Barbara Su +3

Rice University

Combinatorial OptimizationQuadratic Programming
AskPDF
Feb 23, 2026

OptiRepair: Closed-Loop Diagnosis and Repair of Supply Chain Optimization Models with LLM Agents

Supply chain optimization models frequently become infeasible because of modeling errors. Diagnosis and repair require scarce OR expertise: analysts must interpret solver diagnostics, trace root causes across echelons, and fix formulations without sacrificing operational soundness. Whether AI agents can perform this task remains untested. We decompose this task into two phases: a domain-agnostic feasibility phase that iteratively repairs any LP using IIS-guided diagnosis, and a domain-specific validation phase that enforces five rationality checks grounded in inventory theory. We test 22 API models from seven families on 976 multi-echelon supply chain problems and train two 8B-parameter models with self-taught reasoning and solver-verified rewards. The trained models reach 81.7% Rational Recovery Rate (RRR) -- the fraction of problems resolved to both feasibility and operational rationality -- versus 42.2% for the best API model and 21.3% on average. The gap concentrates in Phase 1 repair, where API models average 27.6% recovery rate versus 97.2% for trained models. Two gaps separate current AI from reliable model repair: solver interaction, as API models restore only 27.6% of infeasible formulations; and operational rationale, as roughly one in four feasible repairs violate supply chain theory. Each gap requires a different intervention -- targeted training closes the solver interaction gap, while explicit specification as solver-verifiable checks closes the rationality gap. For organizations adopting AI in operational planning, formalizing what 'rational' means in their context is the higher-return investment.

Ruicheng Ao, David Simchi-Levi, Xinshang Wang

Massachusetts Institute of Technology. · Alibaba Group.

Supply Chain OptimizationLarge Language Model-Guided OptimizationLLM Agent ReliabilityLinear ProgrammingCombinatorial Optimization
AskPDF
Feb 19, 2026

Partial Optimality in the Preordering Problem

Preordering is a generalization of clustering and partial ordering with applications in bioinformatics and social network analysis. Given a finite set VV and a value cab∈Rc_{ab} \in \mathbb{R} for every ordered pair abab of elements of VV, the preordering problem asks for a preorder ≲\lesssim on VV that maximizes the sum of the values of those pairs abab for which a≲ba \lesssim b. Building on the state of the art in solving this NP-hard problem partially, we contribute new partial optimality conditions and efficient algorithms for deciding these conditions. In experiments with real and synthetic data, these new conditions increase, in particular, the fraction of pairs abab for which it is decided efficiently that a≴ba \not\lesssim b in an optimal preorder.

David Stein, Jannik Irmai, Bjoern Andres

Machine Learning for Computer Vision TU Dresden

Combinatorial Optimization
AskPDF
Feb 17, 2026

Heuristic Search as Language-Guided Program Optimization

Large Language Models (LLMs) have advanced Automated Heuristic Design (AHD) in combinatorial optimization (CO) in the past few years. However, existing discovery pipelines often require extensive manual trial-and-error or reliance on domain expertise to adapt to new or complex problems. This stems from tightly coupled internal mechanisms that limit systematic improvement of the LLM-driven design process. To address this challenge, we propose a structured framework for LLM-driven AHD that explicitly decomposes the heuristic discovery process into modular stages: a forward pass for evaluation, a backward pass for analytical feedback, and an update step for program refinement. This separation provides a clear abstraction for iterative refinement and enables principled improvements of individual components. We validate our framework across four diverse real-world CO domains, where it consistently outperforms baselines, achieving up to 0.170.17 improvement in QYI on unseen test sets. Finally, we show that several popular AHD methods are restricted instantiations of our framework. By integrating them in our structured pipeline, we can upgrade the components modularly and significantly improve their performance.

Mingxin Yu, Ruixiao Yang, Chuchu Fan

Massachusetts Institute of Technology, Cambridge, MA, USA

Automated Heuristic DesignLarge Language Model-Guided OptimizationCombinatorial OptimizationLLM-Based Program Synthesis
AskPDF
Feb 17, 2026

On inferring cumulative constraints

Cumulative constraints are central in scheduling with constraint programming, yet propagation is typically performed per constraint, missing multi-resource interactions and causing severe slowdowns on some benchmarks. I present a preprocessing method for inferring additional cumulative constraints that capture such interactions without search-time probing. This approach interprets cumulative constraints as linear inequalities over occupancy vectors and generates valid inequalities by (i) discovering covers, the sets of tasks that cannot run in parallel, (ii) strengthening the cover inequalities for the discovered sets with lifting, and (iii) injecting the resulting constraints back into the scheduling problem instance. Experiments on standard RCPSP and RCPSP/max test suites show that these inferred constraints improve search performance and tighten objective bounds on favorable instances, while incurring little degradation on unfavorable ones. Additionally, these experiments discover 25 new lower bounds and five new best solutions; eight of the lower bounds are obtained directly from the inferred constraints.

Konstantin Sidorov

Faculty of Electrical Engineering, Mathematics & Computer Science, Delft University of Technology, Delft, The Netherlands

Resource-Constrained Project SchedulingConstraint ProgrammingCombinatorial OptimizationConstraint Propagation
AskPDF
Feb 16, 2026

Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks

The Winner Determination Problem (WDP) in combinatorial auctions is NP-hard, and no existing method reliably predicts which instances will defeat fast greedy heuristics. The ML-for-combinatorial-optimization community has focused on learning to replace solvers, yet recent evidence shows that graph neural networks (GNNs) rarely outperform well-tuned classical methods on standard benchmarks. We pursue a different objective: learning to predict when a given instance is hard for greedy allocation, enabling instance-dependent algorithm selection. We design a 20-dimensional structural feature vector and train a lightweight MLP hardness classifier that predicts the greedy optimality gap with mean absolute error 0.033, Pearson correlation 0.937, and binary classification accuracy 94.7% across three random seeds. For instances identified as hard -- those exhibiting ``whale-fish'' trap structure where greedy provably fails -- we deploy a heterogeneous GNN specialist that achieves ≈0%{\approx}0\% optimality gap on all six adversarial configurations tested (vs.\ 3.75--59.24% for greedy). A hybrid allocator combining the hardness classifier with GNN and greedy solvers achieves 0.51% overall gap on mixed distributions. Our honest evaluation on CATS benchmarks confirms that GNNs do not outperform Gurobi (0.45--0.71 vs.\ 0.20 gap), motivating the algorithm selection framing. Learning when to deploy expensive solvers is more tractable than learning to replace them.

Sungwoo Kang

Department of Electrical and Computer Engineering Korea University Seoul 02841, Republic of Korea

Algorithm SelectionCombinatorial Optimization
AskPDF
Feb 16, 2026

A Bayesian Approach to Low-Discrepancy Subset Selection

Low-discrepancy designs play a central role in quasi-Monte Carlo methods and are increasingly influential in other domains such as machine learning, robotics and computer graphics, to name a few. In recent years, one such low-discrepancy construction method called subset selection has received a lot of attention. Given a large population, one optimally selects a small low-discrepancy subset with respect to a discrepancy-based objective. Versions of this problem are known to be NP-hard. In this text, we establish, for the first time, that the subset selection problem with respect to kernel discrepancies is also NP-hard. Motivated by this intractability, we propose a Bayesian Optimization procedure for the subset selection problem utilizing the recent notion of deep embedding kernels. We demonstrate the performance of the BO algorithm to minimize discrepancy measures and note that the framework is broadly applicable any design criteria.

Nathan Kirk

1*School of Mathematics and Statistics, University of St Andrews, Mathematical Institute, St Andrews, KY16 9SS, United Kingdom.

Combinatorial Optimization
AskPDF