Combinatorial Optimization

Follow this topic Ask about this topic

Momentum

33 papers in the last four weeks, up 83% on the four weeks before. 0.3% of all new papers.

Jul 13Week of Sep 28

Latest papers 277

Sep 16, 2026cs.AI

Designing Agentic AI Workflow Portfolios under Imperfect Selection and Compute Cost

Agentic AI systems often approach the same task through multiple workflows that differ in reasoning strategy, verification structure, and compute cost. A natural deployment policy is to use the workflow with the highest average performance, but this can be suboptimal because different workflows may succeed on different instances. We study a portfolio-and-selector paradigm in which a firm runs multiple workflow executions and selects the final answer after observing their outputs. Additional executions may uncover correct answers that the best standalone workflow misses, but they consume compute and introduce plausible distractors that complicate final selection. We formulate this as a workflow portfolio problem in which the firm jointly chooses run size and allocation across workflow types. We summarize selector quality through an odds-lift index and derive sharp bounds on the value of workflow variety. For finite workflow pools, we develop exact formulations, linear programming relaxations, randomized rounding procedures, and computable performance certificates. For large implicit workflow classes, we derive a finite-dimensional dual and an ellipsoid method using a pricing oracle to identify workflows with high weighted accuracy net of recurring compute cost. Under a weak condition, the method obtains a near-optimal solution to the relaxation with polynomially many oracle calls. We evaluate the framework on three datasets: ABCD, Schema-Guided Dialogue, and HotpotQA. Relative to the best standalone workflow, portfolio optimization improves held-out selector accuracy by 3.1, 7.5, and 0.9 percentage points, respectively. Dual-guided workflow generation adds 3.5 points on ABCD and 24.1 on HotpotQA, with no additional gain on Schema-Guided Dialogue.

Mojtaba Abdolmaleki, Stefanus Jasin, Boyu Wang

Ross School of Business, University of Michigan, United States

Cost-Aware Inference Agentic Workflows Combinatorial Optimization LLM Agent Workflow Optimization

Sep 16, 2026cs.LG

Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates

We study the maximum strong independent set problem in a finite hypergraph: find the largest vertex set that intersects every hyperedge in at most one vertex. This objective arises whenever each observed block is a local incompatibility constraint but transitive closure across overlapping blocks is not justified. A motivating example is multi-band LSH-MinHash deduplication, where each collision bucket gives local evidence, while connected-component contraction can impose spurious global equivalences. The paper develops an incidence-structural toolkit for this problem. We prove exact reductions for dominance, incidence twins, and weight-1 blocks; derive closed-form and low-weight upper bounds; introduce puncturing and covering certificates that sharpen those bounds; and analyze a layered greedy clustering algorithm driven by block weights and residual incidence. The algorithmic analysis includes feasibility, maximality, conditional optimality, a layered witness-matching upper bound, and incidence-local complexity bounds. The results give correctness, termination, fixed-point, and optimality certificates for broad incidence families, together with examples showing when different certificates separate or coincide.

Yingquan, Wu, Jason Cong

Cody · MBZUAI Institute of Foundation Models Sunnyvale, CA, USA · University of California, Los Angeles Los Angeles, CA, USA

Combinatorial Optimization

Sep 15, 2026math.OC

Intervention problems in the Linear Threshold Model: A general formulation and new results

We study an optimal intervention problem for linear threshold models. This is a popular class of dynamical network systems whereby a number of agents, identified with the nodes of a graph, strategically change their binary action (0 or 1) according to a threshold rule. Specifically, an agent adopts action 1 if and only if the fraction of its neighbors in the interaction graph that do so is greater than or equal to a prescribed threshold. Assuming that a planner can modify the agents' thresholds at a cost equal to the aggregate threshold increase, we study the minimum intervention cost needed to ensure global convergence to the all-1 configuration. Our main contribution is the introduction of a new graph-theoretic quantity, called oriented path number, that is the minimum number of disjoint paths needed to cover the graph that can be oriented to form a directed acyclic graph. When thresholds are all equal to 1/2, the optimal cost is shown to coincide with the oriented path number, whereas, in the general case, it turns out to be the main ingredient of a bound on the optimal intervention cost.

Giacomo Como, Fabio Fagnani, Stephane Durand

Department of Mathematical Sciences “G.L. Lagrange”, Politecnico di Torino, Italy · 2LISN, Universit´e Paris Saclay, France

Dynamical Systems Combinatorial Optimization

Sep 15, 2026cs.AI

One Color Preprocessing Improves DSATUR

The Graph Coloring Problem (GCP) is NP-hard and DSATUR stands as one of the fastest heuristics for it despite producing colorings that typically use more colors than state-of-the-art coloring algorithms. We propose SSLD (Semidefinite Spectral Learning with DSATUR), which improves DSATUR by preprocessing a first good color class before letting DSATUR complete coloring the rest of the given graph. We obtain this color class from a Semidefinite Programming (SDP), similar to an SDP used to compute the Lovász theta number. To the best of our knowledge, SSLD is the first approach to improve DSATUR by preprocessing through fixed color classes. We evaluate SSLD against DSATUR and against a naive 1-color-class preprocessing algorithm on DIMACS instances, random graphs (Erdős--Rényi, Watts-Strogatz, Barabási--Albert), Frequency Assignment and Job Shop Scheduling instances. SSLD matches or beats DSATUR in almost every case across over 1600 benchmark instances, and out performs the naive GISD baseline, allows us to confirm the value brought by the SDP-guided choice of the first color class. This quality comes at a runtime cost of roughly 195 times slower that DSATUR, but demonstrating that SDP-guided preprocessing of a first color class is a direction for future improvements.

Adam Nouira, Lucas Isenmann

Universit´e de Strasbourg

Combinatorial Optimization

Sep 14, 2026econ.EM

Eigenvalue-Decomposition Cost Denoising as an Alternative to Predict-then-Optimize for Shortest-Path Problems

Predict-then-optimize methods such as Smart "Predict, then Optimize" (SPO+) of Elmachtoub and Grigas (2022) learn a mapping from contextual features to unknown edge costs and then solve the induced combinatorial problem on the predicted costs. This approach is powerful but relies on the predictive model being well specified: when the true cost-generating process is nonlinear in the features and the predictor is linear, SPO+'s performance degrades as the misspecification grows. We propose and evaluate a structurally different remedy for a specific but common setting: when the decision-maker observes many noisy realizations of the same underlying cost process, the realized cost vectors themselves can be treated as a noisy signal and denoised directly, via eigenvalue decomposition (equivalently, Principal Component Analysis) of their covariance matrix, before ever invoking a predictive model. We instantiate this idea on the

5\times5

grid shortest-path benchmark introduced by Elmachtoub and Grigas (2022), retaining only the top-

k

eigenvectors of the training cost covariance matrix and projecting new noisy cost observations onto that subspace prior to solving with Dijkstra's (1959) algorithm. We find that the choice of

k

is decisive: keeping only

k{=}2

eigenvectors discards real signal and underperforms even the naive noisy-cost baseline, while setting

k{=}5

to match the true latent feature dimension makes eigenvalue-denoised Dijkstra the best-performing method at every misspecification level tested, outperforming SPO+ by a wide margin under high misspecification.

Henry Aldridge-Krawciw, Irene Aldridge

Predict-Then-Optimize Combinatorial Optimization

Sep 14, 2026cs.AI

T-GADE: Thermodynamical Generative-AI-Driven Evolution of LLM Artifacts

Integrating evolutionary computation and large language models (LLMs) requires control of population diversity as well as generative capability. Among LLM outputs, those with explicit structure, such as a description paired with code, are structured artifacts; we use artifact for short. We propose T-GADE, which evolves these artifacts by extending thermodynamical genetic algorithms through LLM-based genetic operators and artifact-level diversity evaluation. A common free-energy objective supports generational and steady-state updates, with Fermi-type occupancy excluding repeated genotypes and Bose-type occupancy permitting them. We establish exact one-member removal and conditions for recovering the zero-temperature survival rule of Evolution of Heuristics (EoH). On the online bin-packing task studied in the EoH paper, excess measures relative bin-count overhead above a volume lower bound. Training excess uses search instances; transfer excess uses instances with another bin capacity. Generational Bose-type T-GADE at

T=0.003

reduced median training excess by approximately 29%, from 1.152% to 0.815%, over 20 runs per configuration (two-sided Mann-Whitney

p=0.042

, Cliff's

\delta=0.378

). Validation selection among its two highest-ranked final candidates reached the same median transfer excess as EoH, 0.496%. These results demonstrate the utility of thermodynamical selection and validation-based use of retained artifacts.

Kyoko Ogawa, Naoki Mori

Graduate School of Informatics, Osaka Metropolitan University, Osaka, Japan

Evolutionary Optimization Large Language Model-Guided Optimization Combinatorial Optimization Genetic Algorithms

Sep 10, 2026math.OC

Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow

The fixed-charge network flow problem (FCNFP) couples continuous flow allocation with discrete arc-activation decisions, making it a canonical but computationally challenging model for a variety of network design and resource allocation problems. Exact mixed-integer linear programming formulations capture the fixed-charge structure faithfully, but often become difficult to solve on large networks. We propose a scalable continuous-optimization algorithm for large-scale single-commodity FCNFP based on an iteratively reweighted least-squares (IRLS) framework. The method replaces the discontinuous fixed-charge and linear arc cost objective with a smooth nonconvex Lasry--Lions surrogate and solves a sequence of weighted quadratic flow subproblems. Each subproblem is solved by a warm-started dual semismooth Newton method whose Newton systems have weighted graph-Laplacian structure, enabling the use of modern Laplacian solvers. To further improve the discovered arc supports of the challenging underlying combinatorial problem, we also develop an algorithmic variant that incorporates objective-driven perturbation restarts and an anchor-union restricted search that jointly leverages supports discovered by IRLS and by complementary FCNFP heuristics. Computational experiments on 410 benchmark, synthetic, and large-scale instances show that our method obtains the best objective quality among the evaluated scalable FCNFP algorithms, with a mean gap of

1.316\%

to a time-limited MILP reference and a win-or-tie rate of

90.0\%

among the non-MILP methods. The results indicate that combining smooth continuous optimization with support-level search is an effective strategy for producing high-quality feasible solutions to large-scale FCNFP.

Sindura Saraswathi, Christian Kümmerle

University of Central Florida

Combinatorial Optimization

Sep 8, 2026cs.RO

Coverage Path Planning for Redundant Manipulators using Generalized Spanning Trees

Surface coverage with task-redundant manipulators is challenging because each surface point may admit multiple inverse kinematics (IK) solutions, and configuration choices strongly affect motion quality. This paper extends the classical Spanning Tree Coverage (STC) method to redundant manipulators through offline and online Joint Spanning Tree Coverage (JSTC) algorithms. Offline JSTC samples multiple Inverse Kinematics (IK) solutions per grid cell and formulates the problem as a Generalized Minimum Spanning Tree (GMST), selecting one configuration per cell and tracing the resulting tree to obtain a non-revisiting coverage path. Online JSTC incrementally expands and backtracks a spanning tree with feasibility and cost evaluation while handling dynamic grid updates. Simulation results show that offline JSTC reduces computation time, reconfigurations, and joint motion compared to other methods, while online JSTC achieves fast per-step planning in dynamic scenarios.

Raksi Kopo, Kostas J. Kyriakopoulos

Center for AI & Robotics (CAIR) and the Electrical Eng. Program, Engineering Division, New York University Abu Dhabi, Abu Dhabi, United Arab Emirates

Combinatorial Optimization Motion Planning Coverage Path Planning

Sep 7, 2026cond-mat.dis-nn

Graph neural networks and the energetic cavity method for combinatorial optimization

We study the use of graph neural networks (GNNs) for finding approximate ground states of Ising models. Efficiently finding these ground states is of broad significance because many combinatorial optimization problems can be formulated as an Ising model with the appropriate choice of couplings and fields. Exactly solving these problems is hard but there are many good heuristic methods. A lineage of these heuristics build from mean-field approximations: one approach uses the leading eigenvector of an appropriately defined matrix, another is the min-sum algorithm, also known as the energetic cavity method. Without modification, GNNs perform worse than both of these methods. We consider small modifications to the GNN to incorporate these heuristics and find that this considerably improves performance. While the modified approach is competitive against other deep-learning approaches, we still find that simulated annealing is reliably at least as good as deep learning methods for the same computational cost.

Joe Bacchus George, George T. Cantwell

Department of Engineering, University of Cambridge, CB2 1PZ, United Kingdom

Graph Neural Networks Combinatorial Optimization Neural Combinatorial Optimization

Sep 7, 2026cs.AI

Agentic Algorithm Engineering: Improving Shared-Memory Exact Minimum Cuts

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. Over the last years, we engineered a range of fast algorithms for this problem. Our fastest exact algorithm uses an inexact algorithm to obtain a better bound for the problem, reductions that depend on this bound, improved data structures and parallel contraction routines. It is available in the open-source package VieCut and, on real-world instances, outperformed the previously fastest solvers by a factor of up to 2.5 sequentially and up to 12.9 when run in parallel. We improve this algorithm using agentic algorithm engineering (AAE), a methodology that we introduce here, in which autonomous large language model agents run the algorithm engineering cycle on an existing code base: they form hypotheses about where running time is lost, implement them, benchmark the result on a fixed instance set and keep or discard the change. Even though we had already tuned our algorithm by hand extensively, the agent finds significant optimizations, in particular on the DIMACS core instances: factors of 1.28 (sequential) and 1.63 (32 threads) on real-world k-cores, and 6.26 and 127 on the DIMACS core instances.

David A. Bader, Adil Chhabra, Ernestine Großmann +3

New Jersey Institute of Technology, Newark, NJ, USA · Heidelberg University, Heidelberg, Germany. · Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria +1

High-Performance Computing Combinatorial Optimization

Sep 6, 2026cs.DS

A Group-Based Resource Allocation Model for the Fractional Knapsack Problem

To solve the fractional knapsack problem, Dantzig's greedy rule orders items according to their value-to-cost ratio. This ordering introduces priority issues. An arbitrarily small perturbation to the input can change the allocation if the budget is exhausted between two items with very similar ratios. To mitigate that problem, we introduce a two-stage rule. We group items sharing attributes within a radius

δ

. We then evaluate these groups in descending order of ratio and divide their group's budget share without further ranking. Consider a group featuring an aggregate capacity

U_G

, unit costs contained in

[w^-,w^+]

, and a representative value

\widehat{v}

. The group's loss relative to the exact optimum is bounded by

\widehat{v}\, U_G\frac{w^+-w^-}{w^++w^-}+\varepsilon_v U_G

, where

\varepsilon_v

limits the group's internal value variation. Moreover, this harmonic factor remains tight for any group size. The overall loss becomes restricted to the single budget-binding group whenever the grouping remains order-compatible; thus, groups containing at most

K

items suffer a per-item loss of

\mathcal{O}(\frac{K}{n})

. Should group ratio intervals exhibit an overlap of at most

ω

, an additive term

ωC

degrades this bound. Within the separation margin between adjacent groups, the grouped allocation remains Lipschitz continuous with respect to cost data, exhibiting a modulus of

\frac{K}{w_{\min}}

. Computing this allocation takes

\mathcal{O}(n+m\log m+|Γ|\log|Γ|)

time given

m

groups and a boundary group

Γ

. Alternatively, the time complexity drops to

\mathcal{O}(n+m\log m)

if a linear-time selection method identifies the boundary group's allocation.

Abhinaba Chakraborty

ID Lab, University of Ghent-imec, Ghent, Belgium

Combinatorial Optimization Sensitivity Analysis

Sep 3, 2026cs.AI

Counterfactual Routing Using Integer Programming with Constraint Generation

We present our submission to the IJCAI 2025 'Counterfactual Routing Competition' (CRC 25). The goal of the competition is to find counterfactual explanations for the shortest path problem. This requires deciding what the minimal changes to a road network would make a route chosen by the user the optimal route. This enables explanations such as "Your suggested route would indeed have been optimal, if road X were not a bicycle path." Our solution models the problem as an integer program, iteratively incorporating constraints until an exact solution is found. In the final evaluation on held-out test instances, our method ranked fourth in solution quality and obtained its solution fastest on every instance, with an average runtime of 9.0 seconds compared to 118.8 seconds for the next-fastest submission.

Daniël Vos, Sterre Lutz

Delft University of Technology

Counterfactual Explanations Combinatorial Optimization

Sep 2, 2026cs.LG

Frontier LLMs are effective batch optimizers: Assessing reasoning models in continuous and discrete settings

Frontier large language models (LLMs) have become attractive priors for optimization due to their large-scale pretraining that enables them to navigate a variety of optimization settings. However, the effectiveness of modern reasoning LLMs in batch optimization settings remains underexplored. Here we investigate the performance of the current generation of frontier LLMs as batch optimizers in both continuous and discrete settings. We find that while LLMs are competitive zero-shot batch optimizers for numerical test functions, their performance is brittle compared to classical non-LLM optimization approaches. However, LLM priors are significantly better in semantically rich settings, indicating that their batch optimization behavior is highly effective when navigating and reasoning over the discrete spaces most similar in structure to their pretraining data.

Frank Hu, Shriram Chennakesavalu, David Graff

Prescient Design, Genentech South San Francisco, CA, USA

Black-Box Optimization Large Language Model-Guided Optimization Combinatorial Optimization Ising Optimization

Sep 2, 2026cs.DM

frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study

For more than 20 years, the Model-RB benchmark frb100-40 remained an open challenge; since 2014, its public record had stood at 99 of 100 variables. We give a directly checkable 100-vertex independent set for its 4,000-vertex graph. Together with a verified partition into 100 cliques of size 40, the witness proves that the maximum independent-set size is 100 and the minimum vertex-cover size is 3,900. The stochastic run that found the witness is kept separate from this proof. We evaluated its added pair and triple repair operators in a preregistered campaign comprising 8,668 valid runs. The primary comparison found no detectable acceleration over base ULSA (hazard ratio 0.967, 95% confidence interval 0.915-1.023; p=0.248), and the factorial ablation reached the same conclusion. On a smaller FRB suite, the group-aware CSP pipeline solved 2,500/2,500 runs, compared with 2,391/2,500 for LibMVC-NuMVC. On frb100-40, full ULSA, base ULSA, and NuMVC each produced 0/56 new certificates. With no events, the planned cross-solver hazard ratios remain unidentified. NuMVC ended with cover size 3,902 in 40 runs and 3,903 in 16. Exhaustive enumeration showed that none of the 108 unique recorded conflict-two states had a strictly improving group-aware CSP neighbor within Hamming radius three. The certificate settles the instance. The experiments characterize the search barrier, and the preregistered comparisons show no heuristic advantage.

Onur Uğurlu

İzmir Bakırçay University

Combinatorial Optimization Metaheuristic Optimization Constraint Programming

Sep 1, 2026cs.LG

GeoPAR: Large-Scale Multi-Agent Combinatorial Optimization with Geometry-Guided Parallel Autoregressive Learning

Multi-agent combinatorial optimization problems are notoriously challenging due to their NP-hard nature. Recent parallel autoregressive neural solvers improve inference efficiency by allowing agents to make decisions simultaneously, but their performance often degrades on large-scale instances. This is largely attributable to weak modeling of local geometric structures and the fact that conflicting task selections are handled only after action generation. To address these limitations, we propose GeoPAR, a geometry-guided parallel autoregressive reinforcement learning framework for scalable multi-agent combinatorial optimization. GeoPAR integrates three key components: (1) a projection-window sparse geometry mechanism that builds lightweight local candidate neighborhoods through multi-directional projections, (2) sparse edge-biased attention that injects these geometric relations into node representations, and (3) cache-guided conflict-aware assignment that reuses the geometric cache during decoding to suppress duplicate selections of exclusive tasks. Experiments on heterogeneous vehicle routing and open multi-depot pickup-and-delivery problems show that GeoPAR improves large-scale zero-shot generalization while substantially reducing rollout steps and maintaining efficient inference.

Wenjian Wu, Zesheng Jia, Jiaying Tang +2

School of Future Science and Engineering, Soochow University, Suzhou, China

Combinatorial Optimization Vehicle Routing Autoregressive Decoding RL for Combinatorial Optimization Neural Combinatorial Optimization

Aug 31, 2026cs.IT

Strengthening Recursive Constructions for Zero-Error Shannon Capacity

The exact Shannon capacity is unknown for every odd cycle beyond the five-cycle

C_5

, making odd cycles a central open problem in zero-error information theory. Improving the known lower bounds requires constructing large independent sets in strong powers of these graphs. Recent AI-assisted work has produced a rapid sequence of improvements: building on the construction of Itty et al., Gao developed a recursive product construction for combining structured independent sets, and Buys, Polak, and Zuiddam (BPZ) subsequently strengthened this through a richer recursion framework. We continue this line of AI-assisted exploration and introduce a heterogeneous refinement of these constructions. The central observation is that the usefulness of an intermediate construction depends not only on the size of its current main independent set, but also on the auxiliary structure it carries into subsequent recursion. Consequently, different parts of that auxiliary structure need not use the same independent set, and different occurrences in a recursion need not use the same intermediate representation. We formalize this for Gao's binary product and derive explicit propagation rules showing how heterogeneous choices strengthen the resulting gadget while leaving its current code size unchanged, then extend the principle to the more general BPZ framework, tailoring constructions to the distinct roles they play within the recursion. Applying these refinements to the seven-cycle

C_7

, we obtain an independent set in

C_7^{\boxtimes 500}

yielding

Θ(C_7)\ge 3.25883262\ldots

, improving the best known lower bound. Beyond the numerical gain, the results illustrate a general principle for recursive zero-error constructions: intermediate structures with the same dimension and current code size can have different downstream value depending on where and how they are used in the recursion.

Ravi Tandon

School of Electrical, Computing and Software Engineering, University of Arizona, Tucson, AZ 85721, USA.

Combinatorial Optimization Information-Theoretic Lower Bounds

Aug 31, 2026cs.LG

Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization

Bilevel mixed-integer linear optimization problems model hierarchical decision processes in which a leader anticipates the optimal response of a follower. Although expressive, these problems are computationally challenging because lower-level optimality is embedded in the leader's feasible region. Value-function reformulations replace the nested follower optimization with a constraint involving the follower's optimal value, but evaluating this value function exactly can itself be expensive. This paper introduces Graph4BiLO, a graph neural network (GNN) approach for learning bilevel value functions from variable--constraint graph representations. In contrast to fixed-length multilayer perceptron (MLP) representations, the GNN uses shared message-passing parameters and can therefore be applied across multiple problem sizes with a single trained model. The learned ReLU network is encoded exactly as mixed-integer linear constraints and embedded in an approximate single-level formulation. A repair step subsequently re-solves the follower problem for the selected leader decision to recover a bilevel-feasible follower response. We evaluate Graph4BiLO on knapsack interdiction instances with 20--100 items against the exact MibS solver and the learning-based Neur2BiLO method. Graph4BiLO obtains objective values comparable to Neur2BiLO across all tested sizes while avoiding size-specific neural networks. An additional out-of-distribution experiment demonstrates zero-shot transfer from 20-item training instances to previously unseen 40- and 60-item instances. However, embedding message passing at every graph node substantially increases the resulting mixed-integer formulation size and solve time. These results identify a central tradeoff between size-generalizable graph representations and the computational cost of embedding GNNs within optimization models.

Jessica D. Elrefaei, Kaixun Hua, Seungbae Kim +2

Graph Neural Networks Value Function Estimation Mixed-Integer Linear Programming Combinatorial Optimization Bilevel Optimization

Aug 30, 2026math.OC

Transformer-Based Flow Shop Scheduling Using MILP-Generated Training Data

Advances in machine learning (ML) have created new opportunities to complement traditional operations research (OR) methods. In particular, transformer models can capture complex interactions in token sequences by mapping tokens into a high-dimensional embedding space and propagating contextual information via attention. This makes them a candidate to model non-permutation flow shop scheduling with secondary resources as a next-token prediction task, where tokens represent job-machine-secondary resource tuples. For training, mixed-integer linear programming (MILP)-generated schedules are tokenized and used as next-token prediction data. During inference, partial token sequences (prefixes) are randomly generated and completed by the trained transformer through constrained decoding. A computational study is conducted on a flow shop with 8 jobs, 4 machines, and 3 secondary resources, where jobs are selected from a fixed pool of 20 jobs that is sampled during training and provides the candidates during prefix completion. The transformer achieves better solution quality (smaller makespans) compared to a genetic algorithm (GA), the NEH heuristic, and random search. It is outperformed only by the MILP model and the iterated greedy (IG) heuristic. The study concludes that transformer models can, to some extent, learn patterns from MILP-optimized non-permutation flow shop schedules and that transformer-based scheduling represents an interesting direction for future research, particularly in settings with a fixed, recurring job set.

Roderich Wallrath

University of Twente, Faculty of Science and Technology, Sustainable Process Technology, Process Design and Optimization, Drienerlolaan 5, 7522 NB Enschede, The Netherlands

Transformer Combinatorial Optimization Neural Combinatorial Optimization

Aug 25, 2026cs.RO

Sequential Object Placement Optimization with Convex Decomposition

Robotic object packing has been a core challenge for robotic deployment in logistics, industry, etc., due to the curse of dimensionality in combinatorial search and the difficulty of dealing with dynamic collision constraints for irregularly shaped objects. Current heuristic and learning-based methods mainly assume a limited spatial discretization resolution of space, and computation becomes extremely inefficient as discretization accuracy increases. In this work, we eliminate this assumption by introducing SOPO-CD, which frames sequential object placement as a differentiable nonlinear optimization problem with hard constraints in a decomposed free space. We formulate the constraints of placing a convex object inside a convex hull as constraining the vertices of the object to lie inside the convex hull. The constraints and their derivatives can be written in closed form and calculated efficiently. We implement a custom solver that achieves local-optimal placements within tightly constrained space in milliseconds; a

50 \times

speedup compared to a fine-grained grid search method. We evaluate our framework on 2D Tangram, 2D Tetris, and 3D Bin Packing, and have demonstrated strong computational performance and packing utility. We also demonstrate its real-world applicability for solving the Tangram puzzle using a robot equipped with a dexterous hand.

Yuezhe Zhang, Xiangyu Lyu, Sohan Rudra +2

Interactive Robot Perception & Learning, Technical Univsersity of Darmstadt, Germany · Intelligent Autonomous Systems, Technical Univsersity of Darmstadt, Germany · Robotics and Semantic Systems, Lund University, Sweden +1

Combinatorial Optimization Robotic Manipulation

Aug 13, 2026cs.DC

TEMPO: Makespan-Aware Expert-Parallel Load Balancing Across Memory- and Compute-Bound Regimes

In expert-parallel (EP) MoE serving, every layer synchronizes at the slowest GPU. Dispatchers balance token counts (EPLB, LPLB, UltraEP) or activated-expert counts (METRO), assuming expert time is linear in one. Measurements on two datacenter GPU generations show it is neither: below

\nstar\!\approx\!156

--

168

tokens, HBM weight streaming dominates---cost attaches to \emph{activated replicas}, not tokens; above it, grouped GEMM rounds tokens to 128-tile

M

-tiles, so \emph{splitting} an expert adds padded compute. A max-affine profile

t=\max(a+bG,\,c+βN)

captures both regimes. Realistic decode batches hold hot experts in the linear regime and cold in the flat \emph{simultaneously}; recorded batches show proxy dispatches differ by

1.4

--

1.6\times

in modeled block time (p95 up to

1.7\times

), and \emph{which} proxy wins flips with the regime. We formalize per-batch dispatch as a fixed-charge makespan problem---NP-hard on two fully replicated GPUs, polynomial in degenerate limits---and present \sys{}, a makespan-aware dispatcher solving it in milliseconds off the critical path; its SGLang integration runs out-of-process and fuses dispatch with count collection into one in-graph kernel. Anchored by an 8-GPU Testbed~~A microbenchmark, \sys{} stays within 1% of the best fixed baseline everywhere and wins by up to $15.5\%$ where regimes mix. End-to-end on Testbed~~B, Qwen3-235B (inside the win region) gains

4

--

6\%

throughput and cuts p99 latency by

{\sim}15.6\%

; DeepSeek-V3 (outside, communication-dominated) shows only mechanism cost. A phase diagram, not a universal win, is the claim: it predicts both outcomes before deployment.

Jie Li, Chenxin Jia, Jinliang Shen +5

KlingAI Research

Expert Parallelism Expert Load Balancing LLM Inference Scheduling Mixture-of-Experts Inference Combinatorial Optimization

Aug 12, 2026stat.ML

SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization

Neural combinatorial optimization (NCO) relies on parallel solution sampling for training, yet existing methods fail to fully exploit the rich information latent in a co-sampled solution group. Preference-optimization methods anchor on the single best solution and discard fine-grained quality and structural signal from all other peers-a failure we term gradient signal polarization. Mean-based baselines instead weight peers uniformly, so structurally near-identical peers flood the baseline with redundant information and keep gradient variance high-a failure we term baseline redundancy. We propose SSPO (Structure-Aware Similarity-Weighted Preference Optimization), which scores all

B

sampled solutions jointly through a dissimilarity-weighted leave-one-out baseline: structurally distinct peers receive higher weight, resolving both failures in a single mechanism. The baseline uses zero-parameter, problem-adaptive solution embeddings built from the encoder's existing node representations. Experiments on TSP, EFL, and JSP benchmarks show consistent gains over prior best-anchor and uniform-weight baselines. A direct comparison against uniform RLOO on TSP and EFL confirms that structure-aware weighting is the primary driver of improvement. The SSPO-trained EFL policy has been deployed in a production facility-location system at JD

\mathord{.}

com, confirming practical viability at scale.

Yuanyu Li, Jintao Xu, Zijiang Liu +6

Supply Chain Tech Team Y, JD.com, Beijing, China · Department of Industrial Engineering, Tsinghua University, Beijing, China · Faculty of Engineering and Faculty of Business and Economics, The University of Hong Kong, Hong Kong, China

Combinatorial Optimization Preference Optimization Importance Weighting RL for Combinatorial Optimization Neural Combinatorial Optimization

Aug 11, 2026cs.LG

Diffusion-Based Data-Driven Assortment Optimization

Assortment optimization is a fundamental problem in revenue management, typically addressed using parametric choice models such as the multinomial logit (MNL) and its variants. While these models enable tractable formulations, their performance is sensitive to model misspecification and often struggles to capture complex customer behavior. In this paper, we propose a model-agnostic framework for assortment optimization based on guided discrete diffusion. We represent assortments as binary vectors and perform stochastic search via a learned reverse diffusion process, avoiding explicit combinatorial enumeration. To incorporate decision objectives, we introduce a reward-guided mechanism that biases local transitions using estimates of expected revenue. This allows the method to effectively balance exploration and exploitation during generation. Empirically, we show that the proposed approach consistently identifies high-quality assortments and remains robust under model misspecification, often recovering near-optimal solutions in high-dimensional settings. Moreover, the generative nature of diffusion enables the production of diverse high-performing assortments, offering flexibility beyond a single deterministic solution. These results highlight the potential of generative modeling as a scalable and robust paradigm for combinatorial optimization in data-driven decision-making.

Junyi Liao, Xiaohui Jiang, Zhengwei Tong +2

Department of Electrical and Computer Engineering, Duke University · Department of Biostatistics and Bioinformatics, Duke University · Department of Computer Science, Duke University

Diffusion Model Guidance Combinatorial Optimization Diffusion Models Assortment Optimization

Aug 11, 2026cs.AI

Decision-Aware Approximation of Belief Functions for Evidential Combinatorial Optimization

Reducing the number of focal elements of a mass function is classically driven by an intrinsic distance, such as Jaccard or Jousselme, that keeps the approximation close to the original as a body of evidence. We consider instead the case where the mass function feeds a linear combinatorial optimisation problem with evidential costs. What should then be preserved is not the closeness of the two mass functions, but the quality of the decision they induce. We introduce a decision-aware approximation that targets the regret of the decision: one decides with the cheaper approximation and is evaluated under the true mass function. On a minimal shortest path, the distance-optimal approximation flips the decision while a decision-aware merge preserves it, and this occurs on a non-negligible fraction of random instances. We prove a one-point bound that localises the regret at the true optimum, turn it into an exact dynamic program for the scalar case, and extend it to an online version that prunes focal elements before the final cost is known. In experiments the decision-aware compressor flips the decision less often than representation-aware compression, for both the linear criterion and a non-linear proxy read-out.

Sohaib Afifi

Univ. Artois, UR 3926, Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), Béthune, France

Dempster-Shafer Theory Combinatorial Optimization Decision-Making under Uncertainty

Aug 10, 2026cs.NE

A Graph Neural Network--Guided Genetic Algorithm for Physical Internet Supply Chain Optimization under Cost Uncertainty

Inventory and distribution planning in Physical Internet networks requires coordinating factory-hub assignments, factory supply, lateral transshipment among collaborative hubs, retailer deliveries, and shortages. The problem combines discrete assignment decisions with interdependent continuous flows, while uncertain operating costs make robust planning more difficult. This study formulates deterministic and min-max regret models for a three-echelon network of factories, hubs, and retailers and develops a graph neural network-guided genetic algorithm (GNN-GA) for the assignment decisions. The GNN estimates hub-specific factory-selection probabilities that are used to construct the initial GA population and adapt mutation according to prediction uncertainty. Each previously unseen candidate assignment is evaluated by solving the remaining continuous-flow problem to LP optimality. Simulated annealing, a standard GA, and GNN-GA are compared on 15 instances using matched random seeds and fixed limits on distinct assignment evaluations. Because the evaluation budgets for test Instances 13-15 are smaller than the nominal population size, these experiments primarily assess the quality of learned initialization rather than multi-generation evolutionary search. A separate 400-evaluation experiment on exact test Instance 13 permits three complete offspring generations and a partial fourth pass, with GNN-GA outperforming GA in all 10 matched runs. Three independently generated exact-solvable instances provide a separate test of transfer. Ablation results show that learned initialization provides most of the improvement, while entropy-guided mutation has a smaller, instance-dependent effect. Per-instance solution times include GNN inference and search but exclude model training and one-time model setup.

Faezeh Ardali, Gerald M. Knapp

Department of Mechanical and Industrial Engineering Louisiana State University, Baton Rouge, LA, USA

Graph Neural Networks Evolutionary Optimization Combinatorial Optimization Robust Optimization Genetic Algorithms

Aug 10, 2026cs.DS

Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas

We introduce the \emph{Safe Bicycle Network with Bounded Detours} (\emph{SBNBD}) problem, motivated by upgrading rural road networks for bicycle traffic. Given an undirected graph with safe and unsafe edges, edge lengths, upgrade costs, terminal pairs, a budget, and a detour factor

α

, the task is to upgrade unsafe edges so that each terminal pair is connected by a safe path of length at most

α

times its shortest-path distance in the original network. We study SBNBD from a parameterized perspective. We prove strong NP-hardness on restricted graph classes, including planar graphs of treewidth two, graphs with feedback vertex set number one, and graphs of maximum degree three, and complement these lower bounds with polynomial-time algorithms for trees and graphs of maximum degree two. We show fixed-parameter tractability for the number of unsafe edges and prove matching SETH-based lower bounds, a polynomial-kernel lower bound, and W-hardness for natural parameters. Our main structural result maps any instance to an equivalent instance with

O(\mathrm{fes}+p)

vertices and edges, where

\mathrm{fes}

is the feedback edge number and

p

the number of terminal pairs; this yields fixed-parameter tractability for

\mathrm{fes}+p

. Finally, we evaluate ILP-based algorithms on OpenStreetMap road networks for small German municipalities and their surroundings. The instances have small treewidth upper bounds and moderate feedback edge structure. Preprocessing based on the

\mathrm{fes}+p

reduction and tree-decomposition-based cut generation both improve exact solving, especially on harder instances. Experiments with different detour factors show that increasing

α

can reduce the upgraded-edge length, revealing trade-offs between upgrade cost and allowed relative detours. Overall, structural graph parameters provide a useful algorithmic lens for safe bicycle-network design.

Till Fluschnik

Humboldt-Universität zu Berlin, Department of Computer Science, Algorithm Engineering Group, Germany

Combinatorial Optimization Parameterized Complexity

Aug 10, 2026cs.AI

LLM-Guided Heuristic Design from Simulation Traces: A Case Study in Dynamic Production and AGV Scheduling

Simulation-based optimization (SBO) evaluates executable policies under stochastic dynamics, but most methods treat the simulator as a black box: aggregate scores rank candidates without revealing why they fail or which policy logic should change. We present an LLM-guided heuristic design framework that uses repeated simulation for selection and event-level traces for diagnosis. Each incumbent is assessed through multiple replications, while replaying its lowest-scoring one produces a queryable trace. A manager agent formulates bottleneck hypotheses from this evidence, and editing agents implement parallel code-level revisions. After execution checks and repeated evaluation, best-so-far selection retains only improvements. LLM revision occurs between evaluation batches, while a fixed policy controls each simulation run. We evaluate the framework in a discrete-event simulation of dynamic production and automated guided vehicle (AGV) scheduling. Across five independent optimization runs with Gemini-3.1-Pro, final mean scores averaged 77.51 on the simulator's 0-100 scale. In the highest-scoring run, trace-based diagnoses motivated proactive charging, distance-aware AGV assignment, and rebalanced dispatch priorities, raising the best-so-far mean score from 62.49 to 78.61. On 100 matched seeds, the best final policy outscored representative rolling-MILP, rule-based, and metaheuristic policies on every seed and retained its advantage under random faults without re-optimization. After separate re-optimization for a longer horizon and variable order interarrival times, the resulting policies again outscored all baselines. Ablations with two LLM backbones showed that removing either parallel candidate generation or trace-database access reduced final mean scores. These results show that simulation traces can guide targeted code-level policy improvement in complex simulation-based scheduling.

Jinbo Li, Chuanhao Li

Department of Industrial Engineering, Tsinghua University

Automated Heuristic Design Large Language Model-Guided Optimization Combinatorial Optimization

Aug 10, 2026cs.AI

ASPaeroFlow: Decomposition Heuristics for Joint Air Traffic Flow & Capacity Management

While mathematical models act as vital decision support systems for operational Air Traffic Flow and Capacity Management (ATFCM), existing approaches isolate Air Traffic Flow Management (ATFM) from Dynamic Airspace Configuration (DAC). This separation introduces an unresolved circular dependency between fixed-demand and fixed-capacity assumptions. Although joint optimization resolves this gap, the enlarged search space renders exact models computationally intractable for medium- to large-scale instances. To bridge this gap, we propose ASPaeroFlow: a heuristic for the joint ATFCM; it combines instance-space decomposition heuristics with a local exact approach using Answer Set Programming. We benchmark ASPaeroFlow from small to industry-sized instances and compare it with exact and alternative approaches. The results indicate that (1) the heuristic provides a computational middle ground between exact methods and operational baselines; (2) simultaneous optimization can outperform sequential optimization on joint ATFCM; and (3) an ablation study indicates that DAC has a larger impact on solution quality than flow measures.

Alexander Beiser, Markus Hecher, Nysret Musliu +2

TU Wien, Vienna, Austria · University of Potsdam, Potsdam, Germany · CNRS, Artois University (CRIL), Artois, France +1

Air Traffic Management Combinatorial Optimization

Aug 10, 2026cs.GT

Decision-Focused Learning in Network Interdiction Games

We study decision-focused learning (DFL) in shortest-path network interdiction (SPNI) games, a Stackelberg game where an interdictor (leader) strengthens the networks' arcs against attacks, while an evader (follower) who is uncertain about costs of attacking network arcs relies on a machine-learned predictor to identify the shortest path. While DFL is highly effective as an end-to-end optimization framework, we show that it faces a fundamental structural failure when employed in this game setting: its training objective admits a broad decision-equivalence class of cost estimators that achieve zero nominal loss yet fail under interdiction, reversing DFL's usual advantage over a naive prediction-focused learning (PFL) approach. To address this, we propose Adversarial DFL (A-DFL), which replaces nominal training samples with interdicted scenarios to collapse the harmful equivalence class. Experiments on synthetic and real-world networks confirm that A-DFL restores DFL's advantage in this game setting, enabling effective end-to-end optimization.

Luca M. Hartmann, Parinaz Naghizadeh

ECE Department, UC San Diego

Adversarial Training Stackelberg Games Combinatorial Optimization Decision-Focused Learning

Aug 9, 2026cs.LG

Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm for 0/1 Knapsack Solving in PyTorch

Activation checkpointing minimizes the runtime of neural networks under a given memory budget, by selecting which intermediate tensors to store and which to recompute. PyTorch solves this as a 0/1 knapsack problem, where operations from a joint forward-backward computation graph are items with a memory cost (weight) and a runtime saving (value). The default solver, dp_knapsack, allocates a full dynamic programming (DP) table of shape

(n+1) \times (W+1)

, where

n

is the number of operations and

W

is the quantized memory budget. This method is resource-hungry and crashes at

n = 100

items on a machine with 64 GB RAM. In this paper, we introduce dp_knapsack_sliding_hirschberg, which combines the sliding window trick and Hirschberg's algorithm to reduce peak memory from

O(nW)

to

O(W)

while preserving the exact optimal solution. Our experiments show successful knapsack execution at

n = 2000

, where dp_knapsack fails at

n = 100

, a 20

\times

increase in computable problem size. In addition, our benchmarks show a consistent 25-28% runtime speedup over dp_knapsack. The implementation is merged into PyTorch and released in version 2.10.

Jędrzej Maczan

Cohere Labs Community Poland

Dynamic Programming Memory-Efficient Optimization Combinatorial Optimization Memory-Efficient Training

Aug 8, 2026cs.LG

PRISM: A Predictive Protocol for Permutation Optimization via Landscape Diagnostics

Permutation optimization arises whenever the components of a system are fixed but their ordering affects performance. We introduce PRISM, a predictive protocol for permutation optimization that measures a fitness landscape before selecting a search strategy. PRISM uses inexpensive landscape diagnostics, including one-step move autocorrelation and fitness-distance correlation, to predict useful mutation operators, identify when structured search is likely to outperform random sampling, and detect regimes in which search provides little advantage. Across synthetic permutation landscapes, neural architecture benchmarks, scientific machine learning pipelines, and large-language-model instruction ordering, the protocol makes testable predictions about search behavior before optimization begins. Exhaustive instruction-ordering experiments reveal substantial performance variation induced solely by permutation, while cross-model experiments show that useful ordering structure can transfer across model families and task difficulty. Additional experiments demonstrate that instruction ordering remains consequential after prompt wording is optimized, indicating that content optimization and ordering optimization are complementary. The results position PRISM not as a universally superior optimizer, but as a framework for determining when permutation search is useful, which representation and operator should be used, and when simpler alternatives are preferable.

Blessings Mambwe

ML Collective

Algorithm Selection Combinatorial Optimization Prompt Optimization