# Combinatorial optimization

Combinatorial optimization is a mathematical discipline focused on finding optimal solutions from finite sets using discrete variables, with connections to theoretical computer science, algorithm theory, and computational complexity.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## The Montparnasse Algorithm for RNA Design

DevFeed: [The Montparnasse Algorithm for RNA Design](<https://devfeed.tech/articles/the-montparnasse-algorithm-for-rna-design-145346.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2606.07562>)

Author: Tristan Cazenave

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [monte carlo tree search](<https://devfeed.tech/topics/monte-carlo-tree-search.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [benchmark](<https://devfeed.tech/tags/benchmark.md>), [biology](<https://devfeed.tech/tags/biology.md>), [budget](<https://devfeed.tech/tags/budget.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [design](<https://devfeed.tech/tags/design.md>), [diversity](<https://devfeed.tech/tags/diversity.md>), [energy](<https://devfeed.tech/tags/energy.md>), [evaluation](<https://devfeed.tech/tags/evaluation.md>), [faster](<https://devfeed.tech/tags/faster.md>), [first](<https://devfeed.tech/tags/first.md>), [fleet](<https://devfeed.tech/tags/fleet.md>), [folding](<https://devfeed.tech/tags/folding.md>), [framework](<https://devfeed.tech/tags/framework.md>), [median](<https://devfeed.tech/tags/median.md>), [medicine](<https://devfeed.tech/tags/medicine.md>), [monte-carlo](<https://devfeed.tech/tags/monte-carlo.md>), [nanotechnology](<https://devfeed.tech/tags/nanotechnology.md>), [parallel](<https://devfeed.tech/tags/parallel.md>), [q-bio-bm](<https://devfeed.tech/tags/q-bio-bm.md>), [rna](<https://devfeed.tech/tags/rna.md>), [solve](<https://devfeed.tech/tags/solve.md>)

### AI overview

Montparnasse combines Monte Carlo search with an energy-model structural prior, extended level-1 adaptation, lexicographic evaluation, local repair of incorrectly predicted base pairs, and parallel workers sharing a beam diversified by candidate faults. On Eterna100 V1, with both it and DesiRNA using ViennaRNA 1.8.5 and the Turner 1999 model, 100 workers, and a 30-minute per-puzzle budget, it solved a median of 96 puzzles across five passes, versus 90 for DesiRNA. It was faster on 88 of the 90 puzzles both solved, with median solving times of 0.9 seconds versus 5.6 seconds; 55 puzzles were solved within one second. The puzzle not solved in any pass was solved with a longer budget under the same model.

### Source excerpt

arXiv:2606.07562v2 Announce Type: replace-cross Abstract: Inverse RNA Folding consists of finding a nucleotide sequence that folds into a predefined secondary structure. It is useful for synthetic biology, medicine, and nanotechnology. We propose Montparnasse, a Monte Carlo search framework based on Generalized Nested Rollout Policy Adaptation, augmented with a structural prior derived from the energy model, slow and long adaptation at level 1, a lexicographic multicriteria evaluation, a local repair of the pairs the predicted folding gets wrong, and a fleet of parallel workers coupled through a shared beam whose diversity is maintained on the faults the candidates make rather than on the candidates themselves. On the Eterna100 V1 benchmark, with both solvers folding through the same ViennaRNA 1.8.5 library under the Turner 1999 model, with 100 parallel workers and a budget of 30 minutes per puzzle, Montparnasse solves a median of 96 of the 100 puzzles against a median of 90 for DesiRNA, the previous state of the art, each figure taken over five passes. It is faster on 88 of the 90 puzzles that both solve, with a median solving time of 0.9 s against 5.6 s, and it solves 55 puzzles within the first second. The one puzzle no pass reaches is solved under the same model with a longer budget, so every Eterna100 V1 target is solved by Montparnasse.

## Optimal algorithmic complexity of inference in quantum kernel methods

DevFeed: [Optimal algorithmic complexity of inference in quantum kernel methods](<https://devfeed.tech/articles/optimal-algorithmic-complexity-of-inference-in-quantum-kernel-methods-144886.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2604.15214>)

Author: Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi, Jens Eisert, Maximilian J. Kramer

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Inference](<https://devfeed.tech/topics/inference.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [amplitude](<https://devfeed.tech/tags/amplitude.md>), [bottleneck](<https://devfeed.tech/tags/bottleneck.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [encoding](<https://devfeed.tech/tags/encoding.md>), [gate](<https://devfeed.tech/tags/gate.md>), [inference](<https://devfeed.tech/tags/inference.md>), [kernel](<https://devfeed.tech/tags/kernel.md>), [lower-bound](<https://devfeed.tech/tags/lower-bound.md>), [quant-ph](<https://devfeed.tech/tags/quant-ph.md>), [quantum](<https://devfeed.tech/tags/quantum.md>), [quantum-advantage](<https://devfeed.tech/tags/quantum-advantage.md>), [query](<https://devfeed.tech/tags/query.md>), [sampling](<https://devfeed.tech/tags/sampling.md>), [supervised-learning](<https://devfeed.tech/tags/supervised-learning.md>)

### AI overview

Quantum kernel inference estimates a weighted sum of kernel values, and independently sampling each term has query complexity O(N‖α‖₂²/ε²). The abstract identifies two choices--sampling or quantum amplitude estimation for kernel values, and term-by-term estimation or encoding the full sum as one observable. Combining the single-observable encoding with amplitude estimation achieves O(‖α‖₁/ε) queries, with a matching lower bound up to logarithmic factors. This removes N from the query count and improves dependence on ‖α‖₁ and ε. The paper also analyzes gate costs: the query-optimal method is not always best in gate complexity, so the practical strategy depends on hardware. All described algorithms use amplitude estimation as a subroutine.

### Source excerpt

arXiv:2604.15214v3 Announce Type: replace-cross Abstract: Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum $\sum_{i=1}^N \alpha_i k(x,x_i)$ of $N$ kernel values to additive precision $\varepsilon$, where $\alpha$ is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of $O(N\lVert\alpha\rVert_2^2/\varepsilon^2)$. In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of $O(\lVert\alpha\rVert_1/\varepsilon)$, removing the dependence on $N$ from the query count and yielding a quadratic improvement in both $\lVert\alpha\rVert_1$ and $\varepsilon$. We prove a matching lower bound of $\Omega(\lVert\alpha\rVert_1/\varepsilon)$, establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.

## Beyond 4: Improved Competitive Traveling Repairperson

DevFeed: [Beyond 4: Improved Competitive Traveling Repairperson](<https://devfeed.tech/articles/beyond-4-improved-competitive-traveling-repairperson-146120.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.21943>)

Author: Bibek Maharjan, Gokarna Sharma

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [class](<https://devfeed.tech/tags/class.md>), [computer-science](<https://devfeed.tech/tags/computer-science.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [cs-dm](<https://devfeed.tech/tags/cs-dm.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-ma](<https://devfeed.tech/tags/cs-ma.md>), [data-structures-and-algorithms](<https://devfeed.tech/tags/data-structures-and-algorithms.md>), [metric](<https://devfeed.tech/tags/metric.md>), [online](<https://devfeed.tech/tags/online.md>), [problems](<https://devfeed.tech/tags/problems.md>), [ratio](<https://devfeed.tech/tags/ratio.md>), [residual](<https://devfeed.tech/tags/residual.md>), [state](<https://devfeed.tech/tags/state.md>), [zero](<https://devfeed.tech/tags/zero.md>)

### AI overview

For the online traveling repairperson problem on arbitrary metrics, the paper reports a deterministic algorithm with competitive ratio 3.877, improving on the stated 4-competitive state of the art. For zero-residual instances, it reports a ratio of 3+ε for every ε>0. The abstract also says these results extend to some variants of online dial-a-ride; it does not specify which variants or give further algorithmic details.

### Source excerpt

arXiv:2611.21943v1 Announce Type: cross Abstract: With $k\geq 1$ repairpersons starting initially from a depot, we present a 3.877-competitive deterministic algorithm for the fundamental online traveling repairperson problem on an arbitrary metric. For the special class of zero-residual instances, we improve the ratio to $3+\epsilon$ for every $\epsilon>0$. We also extend these results to some variants of the related so-called online dial-a-ride problem. The state-of-the-art is the 4-competitive deterministic algorithm for both problems.

## Convergence Rate of a Functional Learning Method for Conditional Stochastic Optimization

DevFeed: [Convergence Rate of a Functional Learning Method for Conditional Stochastic Optimization](<https://devfeed.tech/articles/convergence-rate-of-a-functional-learning-method-for-conditional-stochastic-optimization-144879.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2603.13048>)

Author: Noel Smith, Andrzej Ruszczynski

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [architectures](<https://devfeed.tech/tags/architectures.md>), [conditional](<https://devfeed.tech/tags/conditional.md>), [convergence](<https://devfeed.tech/tags/convergence.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [distribution](<https://devfeed.tech/tags/distribution.md>), [error](<https://devfeed.tech/tags/error.md>), [expectation](<https://devfeed.tech/tags/expectation.md>), [features](<https://devfeed.tech/tags/features.md>), [function](<https://devfeed.tech/tags/function.md>), [functional](<https://devfeed.tech/tags/functional.md>), [gradient](<https://devfeed.tech/tags/gradient.md>), [learning](<https://devfeed.tech/tags/learning.md>), [linear](<https://devfeed.tech/tags/linear.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [model](<https://devfeed.tech/tags/model.md>), [models](<https://devfeed.tech/tags/models.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [order](<https://devfeed.tech/tags/order.md>), [probability](<https://devfeed.tech/tags/probability.md>), [random-variables](<https://devfeed.tech/tags/random-variables.md>), [sampling](<https://devfeed.tech/tags/sampling.md>)

### AI overview

The method jointly learns a parametric approximation of the conditional expectation and optimizes an outer stochastic objective using only i.i.d. observed context-outcome pairs, when direct sampling from the conditional distribution is infeasible. Its stated non-optimality measure combines the squared objective-gradient norm with the auxiliary model's mean-square error. The convergence rate is O(1/√N), where N is the number of observed pairs: in expectation for linear auxiliary models (including bounded-feature linear architectures), and in probability for general smooth models.

### Source excerpt

arXiv:2603.13048v3 Announce Type: replace-cross Abstract: We consider a stochastic optimization problem involving two random variables: a context variable $X$ and a dependent variable $Y$. The objective is to minimize the expected value of a nonlinear loss functional applied to the conditional expectation $\mathbb{E}[f(X, Y,\beta) \mid X]$, where $f$ is a nonlinear function and $\beta$ represents the decision variables. We focus on the practically important setting in which direct sampling from the conditional distribution of $Y \mid X$ is infeasible, and only a stream of i.i.d. observation pairs $\{(X^k, Y^k)\}_{k=0,1,2,\ldots}$ is available. In our approach, the conditional expectation is approximated within a prespecified parametric function class. We analyze a simultaneous learning-and-optimization algorithm that jointly estimates the conditional expectation and optimizes the outer objective. Using a specially designed measure of non-optimality, combining the squared norm of the objective function's gradient and the mean square error of the auxiliary parametric model, we establish that the method achieves a convergence rate of order $\mathcal{O}\big(1/\sqrt{N}\big)$, where $N$ denotes the number of observed pairs. The rate holds in expectation when the auxiliary model is linear in its parameters, which includes linear architectures with bounded features, and in probability for general smooth models.

## Cost-Aware Agentic Feature Optimization System for Fleet-Scale Ranking Models

DevFeed: [Cost-Aware Agentic Feature Optimization System for Fleet-Scale Ranking Models](<https://devfeed.tech/articles/cost-aware-agentic-feature-optimization-system-for-fleet-scale-ranking-models-145193.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.26531>)

Author: Chang Yang, Yao Xuan, Wendan Yan, Nhat Le, Jiang Liu, Longhao Jin, Zhen Peggy Yao, Alireza Vahdatpour, Djordje Gligorijevic

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Feature Engineering](<https://devfeed.tech/topics/feature-engineering.md>), [AI Agent](<https://devfeed.tech/topics/ai-agent.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [agentic](<https://devfeed.tech/tags/agentic.md>), [asynchronous](<https://devfeed.tech/tags/asynchronous.md>), [blending](<https://devfeed.tech/tags/blending.md>), [budget](<https://devfeed.tech/tags/budget.md>), [candidate](<https://devfeed.tech/tags/candidate.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [entropy](<https://devfeed.tech/tags/entropy.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [feature](<https://devfeed.tech/tags/feature.md>), [feature-selection](<https://devfeed.tech/tags/feature-selection.md>), [features](<https://devfeed.tech/tags/features.md>), [fleet](<https://devfeed.tech/tags/fleet.md>), [large](<https://devfeed.tech/tags/large.md>), [llm](<https://devfeed.tech/tags/llm.md>), [models](<https://devfeed.tech/tags/models.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [ranking](<https://devfeed.tech/tags/ranking.md>), [ranking-models](<https://devfeed.tech/tags/ranking-models.md>), [scale](<https://devfeed.tech/tags/scale.md>), [system](<https://devfeed.tech/tags/system.md>)

### AI overview

The system optimizes features across fleets of ranking models while respecting shared and per-model resource limits, including pipeline cost and serving throughput. LLM agents generate and shortlist cross features, while deterministic tools run and verify experiments. Several importance rankings are blended, using Pareto fronts for multi-task models; a Researcher agent then tunes selections through 10-25 asynchronous trials under resource caps, followed by trimming to meet pipeline budgets. Across production models, normalized entropy rose by 0.31% on average within each model's budget. Trimming reduced pipeline cost by 2.3% with no regression beyond measurement noise, and online A/B tests reported a 0.20% gain in a primary metric.

### Source excerpt

arXiv:2611.26531v1 Announce Type: cross Abstract: Large Web platforms operate large fleets of ranking models, each selecting features from a shared pool of tens of thousands. We present an end-to-end agentic system that optimizes features across the fleet under resource constraints shared across models and those set per model, such as feature pipeline cost and serving throughput (QPS), respectively. In this system, LLM agents propose hypotheses, and deterministic tools execute experiments and verify them. For each model, an LLM generates and shortlists cross features from a combinatorial candidate space, and all features are then ranked by several importance methods. Feature blending mixes these rankings into a single selection, using Pareto fronts across tasks for multi-task models. An LLM Researcher agent then tunes the feature selection in 10--25 asynchronous trials under resource caps, and a trimming step keeps the pipeline cost within budget. Across production models, the system improves normalized entropy by 0.31% on average within each model's budget, and the trimming step cuts pipeline cost by 2.3% with no regression beyond measurement noise. The optimized models were launched, and in online A/B tests they improved a primary online metric by 0.20%.

## Silver Rate Is (Almost) Optimal for Gradient Descent

DevFeed: [Silver Rate Is (Almost) Optimal for Gradient Descent](<https://devfeed.tech/articles/silver-rate-is-almost-optimal-for-gradient-descent-144923.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2609.09152>)

Author: Yuhan Ye, Kaizhao Liu

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [checkpoint](<https://devfeed.tech/tags/checkpoint.md>), [convergence](<https://devfeed.tech/tags/convergence.md>), [convex](<https://devfeed.tech/tags/convex.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [gradient-descent](<https://devfeed.tech/tags/gradient-descent.md>), [local](<https://devfeed.tech/tags/local.md>), [lower-bound](<https://devfeed.tech/tags/lower-bound.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [optimization](<https://devfeed.tech/tags/optimization.md>)

### AI overview

For smooth convex objectives, the recursive silver stepsize schedule's convergence exponent, p_sil = log₂(1+√2) ~= 1.2716, is optimal among predetermined nonnegative gradient descent step schedules: the paper proves a matching Ω(n^(−p_sil−o(1))) lower bound. It also proves an anytime lower bound matching the known upper-bound exponent of about 1.1195. The proof selects iterations where the trajectory explores new coordinates, links them with local functions, and introduces a hard function that bends the trajectory between checkpoints. A recursive maximization over admissible checkpoint sets yields the lower bound for every prescribed schedule.

### Source excerpt

arXiv:2609.09152v3 Announce Type: replace-cross Abstract: Gradient descent (GD) is one of the most fundamental algorithms in optimization. Yet even for smooth convex objectives, the optimal rate among predetermined nonnegative stepsize schedules has remained unresolved. Altschuler and Parrilo [Mathematical Programming, 2025] showed that their recursive silver stepsize schedule achieves an $O(n^{-p_{\mathrm{sil}}})$ rate, where $p_{\mathrm{sil}}=\log_2(1+\sqrt2)\approx1.2716$, improving upon the classical $O(n^{-1})$ rate of constant-step GD. Although the optimality of $p_{\mathrm{sil}}$ has been well supported by numerical evidence for small $n$, a matching lower bound has remained missing. In this paper, we prove an $\Omega(n^{-p_{\mathrm{sil}}-o(1)})$ lower bound for GD, showing that $p_{\mathrm{sil}}$ is the optimal convergence exponent. Additionally, we prove an anytime lower bound that matches the exponent $2p_{\mathrm{sil}}/(1+p_{\mathrm{sil}})\approx1.1195$ of the known upper bound [Zhang, Lee, Du, and Chen, COLT 2025]. Building on the approaches of [Ma and Chen, 2026; Jung, Cho, and Yun, 2026], we select specific iterations as checkpoints at which the GD trajectory explores a new coordinate, and we couple these coordinates using a chain of local functions. Our main technical contribution is a local hard function that bends the GD trajectory between successive checkpoints, resulting in a sharpened lower bound. For each prescribed stepsize schedule, we maximize this bound over admissible checkpoint sets. A recursive analysis of this maximum then yields a lower bound matching the silver exponent for every such schedule.

## Learning with Local Search MCMC Layers

DevFeed: [Learning with Local Search MCMC Layers](<https://devfeed.tech/articles/learning-with-local-search-mcmc-layers-144853.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2505.14240>)

Author: Germain Vivier-Ardisson, Mathieu Blondel, Axel Parmentier

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Operations research and optimization](<https://devfeed.tech/topics/operations-research-and-optimization.md>), [Neural Network](<https://devfeed.tech/topics/neural-network.md>)

Tags: [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [layers](<https://devfeed.tech/tags/layers.md>), [learning](<https://devfeed.tech/tags/learning.md>), [local](<https://devfeed.tech/tags/local.md>), [mcmc](<https://devfeed.tech/tags/mcmc.md>), [search](<https://devfeed.tech/tags/search.md>)

### AI overview

The paper turns local search neighborhoods into proposal distributions for MCMC over feasible solutions, yielding differentiable, stochastic combinatorial layers and associated loss functions for learning with inexact solvers. The approach is motivated by NP-hard problems where exact solvers are costly; the abstract reports that replacing them with local search strongly reduces learning computation. Demonstrations include dynamic vehicle routing with time windows, binary vector and k-subset prediction, and decision-focused learning for multidimensional knapsack. The excerpt does not provide details on theoretical guarantees or comparative results.

### Source excerpt

arXiv:2505.14240v4 Announce Type: replace Abstract: Integrating combinatorial optimization layers into neural networks has recently attracted significant research interest. However, many existing approaches lack theoretical guarantees or fail to perform adequately when relying on inexact solvers. This is a critical limitation, as many operations research problems are NP-hard, often necessitating the use of neighborhood-based local search heuristics. In this paper, we introduce a principled approach for learning with such inexact solvers. Inspired by the connection between simulated annealing and Metropolis-Hastings, we transform the problem specific neighborhood systems used in local search heuristics into proposal distributions, implementing MCMC on the set of feasible solutions. This allows us to construct differentiable, stochastic combinatorial layers and associated loss functions. Replacing an exact solver with a local search strongly reduces the computational burden of learning on many applications. We demonstrate our approach on a dynamic vehicle routing problem with time windows, binary vector and k-subset prediction tasks, as well as a multi-dimensional knapsack decision-focused learning problem.

## Meta-RTL: Evolving Agent Harnesses for RTL Optimization

DevFeed: [Meta-RTL: Evolving Agent Harnesses for RTL Optimization](<https://devfeed.tech/articles/meta-rtl-evolving-agent-harnesses-for-rtl-optimization-145602.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.25891>)

Author: Xinzhuang Xiong, Yonghao Wang, Shengyao Sun, Chengxi Li, Evangeline Young

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Agent Harness](<https://devfeed.tech/topics/agent-harness.md>), [llm-reasoning](<https://devfeed.tech/topics/llm-reasoning.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [agent](<https://devfeed.tech/tags/agent.md>), [agent-harnesses](<https://devfeed.tech/tags/agent-harnesses.md>), [agents](<https://devfeed.tech/tags/agents.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ar](<https://devfeed.tech/tags/cs-ar.md>), [eda](<https://devfeed.tech/tags/eda.md>), [evolution](<https://devfeed.tech/tags/evolution.md>), [framework](<https://devfeed.tech/tags/framework.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [rtl](<https://devfeed.tech/tags/rtl.md>), [search](<https://devfeed.tech/tags/search.md>)

### AI overview

Meta-RTL evolves RTL optimization harnesses from a minimal loop, using EDA feedback while keeping the optimization model, EDA flow, and per-design budgets fixed. Compared with Dr. RTL, Meta-RTL* reduced aggregate WNS/TNS violations by 7.8%/11.0% across 20 development designs, with area reductions on 70%. Without further evolution, it transferred to 10 unseen IC-RTL designs, reducing aggregate WNS/TNS violations by 20.5%/14.0% and total synthesized area by 12.6%. The abstract also says it characterizes three search mechanisms and evaluates their contributions through ablations and a case study.

### Source excerpt

arXiv:2611.25891v1 Announce Type: new Abstract: Large language models enable agents to optimize RTL using EDA feedback, yet their executable search procedures remain largely hand- engineered. We present Meta-RTL, an EDA-grounded framework that evolves RTL optimization harnesses from a minimal loop while keeping the optimization model, EDA flow, and per-design budgets fixed. Compared with Dr. RTL, Meta-RTL* reduces aggregate WNS/TNS violations by 7.8%/11.0% across 20 development designs, with area reductions on 70% of them. Without further evolution, Meta-RTL* transfers to 10 unseen IC-RTL designs, reducing aggregate WNS/TNS violations by 20.5%/14.0% and total synthesized area by 12.6%. We further characterize three search mechanisms in the evolved harness and assess their contributions through ablations and a case study.

## Learning Generative Ranking Policies for Whole-Page Optimization

DevFeed: [Learning Generative Ranking Policies for Whole-Page Optimization](<https://devfeed.tech/articles/learning-generative-ranking-policies-for-whole-page-optimization-145066.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.25527>)

Author: Chen Qiu, Zhigang Hua, Qi Xu, Jizhe Zhang, Sha Hua, Ren Mao, Luke Simon

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [recommendation systems](<https://devfeed.tech/topics/recommendation-systems.md>), [information retrieval](<https://devfeed.tech/topics/information-retrieval.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [generative](<https://devfeed.tech/tags/generative.md>), [improvement](<https://devfeed.tech/tags/improvement.md>), [learning](<https://devfeed.tech/tags/learning.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [pages](<https://devfeed.tech/tags/pages.md>), [policies](<https://devfeed.tech/tags/policies.md>), [ranking](<https://devfeed.tech/tags/ranking.md>), [recommendation](<https://devfeed.tech/tags/recommendation.md>)

### AI overview

The paper proposes whole-page policy improvement for recommendation ranking, choosing and ordering items jointly because items can compete for attention or complement one another. Its local page-level objective repeatedly moves the generator toward higher-scoring pages and splits into a target for each position: at the same partial page, candidates are compared by the scores of the complete pages they lead to. This aims to train each choice for its contribution to the whole page. The authors report better results than evaluated generative re-ranking baselines on KuaiRand-1K, RL4RS-SeqSlate, and an industrial logged-page dataset, and performance closest to the known optimum on a synthetic benchmark. The supplied text does not provide metric values or experimental details.

### Source excerpt

arXiv:2611.25527v1 Announce Type: cross Abstract: A recommendation page is consumed as a whole: the items on it compete for attention and complement one another, so the best page is not simply the individually best items placed side by side. We study whole-page optimization, which selects and orders the items on a page jointly to maximize the score of the page. The number of possible pages grows combinatorially, so good pages must be generated rather than enumerated. Some generative re-ranking methods use the same page-level training signal for every choice in a sampled page. Others imitate target pages built before training, which remain largely fixed as the generator improves. We address both limitations with one local page-level objective, which repeatedly moves the current generator toward pages with higher score. This objective splits exactly into one training target per position, and each target compares candidates at the same partial page by the scores of the complete pages they lead to. Every position therefore learns to choose the item that is better for the whole page, rather than the item that looks best on its own. We call this procedure whole-page policy improvement. On two public datasets, KuaiRand-1K and RL4RS-SeqSlate, which cover multi-objective item selection and constrained ordering, and on an industrial dataset of logged pages, our method outperforms the evaluated generative re-ranking baselines. On a synthetic benchmark with a known optimal page, it also comes closest to the optimum, showing that its improvements come from better whole-page decisions.

## Scone: Symmetry-aware Neural Combinatorial Optimization for Graph Coloring

DevFeed: [Scone: Symmetry-aware Neural Combinatorial Optimization for Graph Coloring](<https://devfeed.tech/articles/scone-symmetry-aware-neural-combinatorial-optimization-for-graph-coloring-145032.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.25273>)

Author: Paolo Pellizzoni, Melanie Weber

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Neural Network](<https://devfeed.tech/topics/neural-network.md>), [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>)

Tags: [combinatorial-optimization](<https://devfeed.tech/tags/combinatorial-optimization.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [general](<https://devfeed.tech/tags/general.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graph-coloring](<https://devfeed.tech/tags/graph-coloring.md>), [inference](<https://devfeed.tech/tags/inference.md>), [information](<https://devfeed.tech/tags/information.md>), [learning](<https://devfeed.tech/tags/learning.md>), [model](<https://devfeed.tech/tags/model.md>), [neural-network](<https://devfeed.tech/tags/neural-network.md>), [node](<https://devfeed.tech/tags/node.md>), [np-hard](<https://devfeed.tech/tags/np-hard.md>), [permutations](<https://devfeed.tech/tags/permutations.md>), [policy](<https://devfeed.tech/tags/policy.md>), [quality](<https://devfeed.tech/tags/quality.md>), [space](<https://devfeed.tech/tags/space.md>), [structure](<https://devfeed.tech/tags/structure.md>), [symmetry](<https://devfeed.tech/tags/symmetry.md>), [tasks](<https://devfeed.tech/tags/tasks.md>), [times](<https://devfeed.tech/tags/times.md>), [training](<https://devfeed.tech/tags/training.md>)

### AI overview

Scone uses a color-equivariant graph neural network to build graph colorings sequentially. It exploits the fact that permuting color labels does not change coloring validity, reducing the effective state space, while propagating earlier assignments so the model can break node symmetries when adjacent nodes need different colors. The abstract reports perfect solution quality with low inference times across several tasks, including sudoku_extreme and register allocation, and generalization to graph families absent from training. It provides no benchmark details or quantitative comparisons.

### Source excerpt

arXiv:2611.25273v1 Announce Type: new Abstract: Graph coloring, which entails assigning colors to nodes such that no adjacent nodes have the same color, is a fundamental combinatorial optimization problem. In general, however, finding a node coloring with no monochromatic edges given a fixed palette is NP-hard. This motivates learning-based methods that can learn to exploit recurring structure across instances to efficiently produce high-quality colorings. Crucially, the validity of a coloring is invariant to permutations of the colors, and we show that exploiting this symmetry reduces the size of the effective state space over which the model has to learn its policy. At the same time, the coloring algorithm must be able to break some symmetries, for example to assign different colors to two adjacent nodes belonging to the same automorphism orbit. In this paper, we introduce Scone, a model that uses a color-equivariant graph neural network to construct colorings sequentially, allowing information from previous assignments to propagate and break node symmetries. Scone achieves perfect solution quality with low inference times across several graph coloring tasks, including on sudoku_extreme and register allocations, and showcases generalization to graph families not encountered during training.

## QUBO-based feature selection for MRI undersampling pattern design

DevFeed: [QUBO-based feature selection for MRI undersampling pattern design](<https://devfeed.tech/articles/qubo-based-feature-selection-for-mri-undersampling-pattern-design-145080.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.25625>)

Author: Xiaoxin Huang, Masayuki Ohzeki

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Feature Engineering](<https://devfeed.tech/topics/feature-engineering.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [eess-sp](<https://devfeed.tech/tags/eess-sp.md>), [error](<https://devfeed.tech/tags/error.md>), [feature-selection](<https://devfeed.tech/tags/feature-selection.md>), [imaging](<https://devfeed.tech/tags/imaging.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [quantum](<https://devfeed.tech/tags/quantum.md>), [sampling](<https://devfeed.tech/tags/sampling.md>), [similarity](<https://devfeed.tech/tags/similarity.md>), [simulation](<https://devfeed.tech/tags/simulation.md>)

### AI overview

The study designs Cartesian MRI undersampling masks by treating each sampling line as a binary feature. It estimates mutual information and conditional mutual information from candidate masks and training evaluations, combines them with a sampling-count penalty in a QUBO, and uses simulated and quantum annealing to select a mask. In zero-filled Fourier undersampling simulations on fastMRI knee magnitude images with patient-disjoint splits, the selected masks achieved lower mean RMSE than four conventional methods at all six tested rates (15%-40%) and higher mean SSIM than univariate mutual-information ranking at every rate. These findings are limited to the reported simulation settings.

### Source excerpt

arXiv:2611.25625v1 Announce Type: new Abstract: We formulate undersampling mask design for Cartesian magnetic resonance imaging (MRI) as a feature subset selection problem. Each sampling line is represented by a binary feature indicating whether it is included in each candidate mask. Using candidate masks and their training-set evaluations, we estimate mutual information (MI) and conditional mutual information (CMI). These estimates and a sampling-count penalty define a quadratic unconstrained binary optimization (QUBO) model. The model is solved using simulated annealing and quantum annealing to determine a feature subset and its corresponding sampling mask. We assess the selected subsets on the test set through zero-filled reconstruction in Fourier undersampling simulations using fastMRI knee magnitude reference images, with patient-disjoint training and test sets. At all six tested target sampling rates from 15% to 40%, the resulting reconstructions have lower mean root mean square error than those obtained with four conventional sampling methods. They also have higher mean structural similarity than those obtained using univariate mutual-information ranking at all tested rates. These results support information-theoretic feature selection as an approach to MRI undersampling mask design under the tested zero-filled simulation settings.

## SailSearch: Agent-Assisted Discovery in Combinatorial Optimization

DevFeed: [SailSearch: Agent-Assisted Discovery in Combinatorial Optimization](<https://devfeed.tech/articles/sailsearch-agent-assisted-discovery-in-combinatorial-optimization-145465.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.25087>)

Author: Dhriti Verma, Kanthi Sarpatwar, Vinicius Lima, Dzung Phan, Jayant Kalagnanam

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [agent](<https://devfeed.tech/tags/agent.md>), [agents](<https://devfeed.tech/tags/agents.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [basis](<https://devfeed.tech/tags/basis.md>), [benchmark](<https://devfeed.tech/tags/benchmark.md>), [best](<https://devfeed.tech/tags/best.md>), [combinatorial-optimization](<https://devfeed.tech/tags/combinatorial-optimization.md>), [cpu](<https://devfeed.tech/tags/cpu.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [discovery](<https://devfeed.tech/tags/discovery.md>), [enumeration](<https://devfeed.tech/tags/enumeration.md>), [first](<https://devfeed.tech/tags/first.md>), [found](<https://devfeed.tech/tags/found.md>), [generator](<https://devfeed.tech/tags/generator.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [independent](<https://devfeed.tech/tags/independent.md>), [language](<https://devfeed.tech/tags/language.md>), [language-model](<https://devfeed.tech/tags/language-model.md>), [optimization](<https://devfeed.tech/tags/optimization.md>)

### AI overview

SailSearch is a human-guided algorithmic research workflow using two language-model agents. On Market Split, its randomized method searches multiple lattice bases while dividing computation between enumeration and continued basis reduction. Across ten seeds per instance, it found the first reported CPU-only solutions for 18 of 33 previously open QOBLIB instances; each seed solved 130-133 of 156 benchmark instances within 24 hours on two CPU cores. For maximum independent set, the authors generated graphs from planted XOR constraints with certified optima. On seven graphs of 1,752-3,996 vertices, the best results from tested solvers after eight hours remained 5-15 vertices below optimum.

### Source excerpt

arXiv:2611.25087v1 Announce Type: new Abstract: We present SailSearch, a human-guided workflow for algorithmic research with two language-model agents, and report results on Market Split and maximum independent set (MIS). For Market Split, our randomized algorithm searches across multiple lattice bases, dividing computation between enumeration and continued basis reduction. Across ten random seeds per instance, it found the first reported CPU-only solutions to 18 of 33 previously open QOBLIB instances, solving 130 to 133 of the 156 benchmark instances per seed with a 24-hour cutoff on two CPU cores. For MIS, our generator encodes planted XOR constraints as graphs with certified optima; on seven instances with 1,752 to 3,996 vertices, the best solutions returned by the tested solvers in eight-hour runs were 5 to 15 vertices below the optimum.

## From Data to Action: Accelerating Refinery Optimization with AI

DevFeed: [From Data to Action: Accelerating Refinery Optimization with AI](<https://devfeed.tech/articles/from-data-to-action-accelerating-refinery-optimization-with-ai-143263.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2605.15085>)

Author: D\\'aniel Pfeifer, \\'Abrah\\'am Papp, Tibor Bern\\'ath, Tam\\'as Zolt\\'an Varga, M\\'ark Czifra, Botond Szil\\'agyi, Edith Alice Kov\\'acs

Published: 2026-11-19T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [ai](<https://devfeed.tech/tags/ai.md>), [anomaly-detection](<https://devfeed.tech/tags/anomaly-detection.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [data](<https://devfeed.tech/tags/data.md>), [linear-programming](<https://devfeed.tech/tags/linear-programming.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [stat-ap](<https://devfeed.tech/tags/stat-ap.md>), [stat-me](<https://devfeed.tech/tags/stat-me.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>)

### AI overview

The paper describes an anomaly-detection layer that helps refinery teams assess and improve large linear-programming (LP) models by surfacing potential input-data errors and unusual relationships in LP inputs and outputs. It combines a transformed ECOD method with methods for selecting informative pairs in high-dimensional data and two 2D anomaly-detection algorithms. The system learns relationships from past data, ranks unusual connections by importance, and runs automatically alongside optimization; decision makers then review relevant anomalies and can use them to improve later LP solutions. The authors report that it revealed business opportunities and data-supply errors in MOL's refinery scheduling and planning architecture. Periodic retraining is built in.

### Source excerpt

arXiv:2605.15085v2 Announce Type: replace-cross Abstract: Nowadays refinery optimization utilizes sheer amounts of data, which can be handled with modern Linear Programming (LP) software, but the interpreting and applying the results remains challenging. Large petrochemical companies use massive models, with hundreds of thousands of input matrix elements. The LP solution is mathematically correct, but simplifications are made in the model, and data supply errors may occur. Therefore, further insight is needed to trust the results. The novelty of the paper consists of enhancing the LP solver with a memory, which makes possible to find potential errors in the input data, finding unusual relations in the data on different decision levels, by introducing an anomaly detection tool. Analyzing the potential "anomalies" in the input and output of LP, the subsequent LP solutions can be improved. The Anomaly Detection tool proposed comprises three methodologies. A transformed version of the popular ECOD methodology is applied. New methods are proposed to handle high-dimensional data: choosing the most informative pairs. Then, this is used alongside two 2D Anomaly Detection algorithms, revealing several business opportunities and data supply errors in the MOL refinery scheduling and planning architecture. The proposed tool learns connections in past data and runs very efficiently on present data revealing unusual connections sorted by their importance. Up to this step, optimization and Anomaly Detection happened automatically, and thereafter, decision makers may take a look at the most relevant anomalies found, and decide how to further improve the subsequent LPs. The tool also has periodic retraining built in.

## Optimal Development Path: An Empirical Evaluation of Tiered Dependency-Aware Sequencing

DevFeed: [Optimal Development Path: An Empirical Evaluation of Tiered Dependency-Aware Sequencing](<https://devfeed.tech/articles/optimal-development-path-an-empirical-evaluation-of-tiered-dependency-aware-sequencing-142164.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.23303>)

Author: Azzeddine Ihsine, Sara Ihsine

Published: 2026-11-19T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Software Engineering](<https://devfeed.tech/sources/arxiv-software-engineering.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [jira](<https://devfeed.tech/topics/jira.md>)

Tags: [alternatives](<https://devfeed.tech/tags/alternatives.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [block](<https://devfeed.tech/tags/block.md>), [calendar](<https://devfeed.tech/tags/calendar.md>), [completion](<https://devfeed.tech/tags/completion.md>), [cs-se](<https://devfeed.tech/tags/cs-se.md>), [dependency](<https://devfeed.tech/tags/dependency.md>), [development](<https://devfeed.tech/tags/development.md>), [evaluation](<https://devfeed.tech/tags/evaluation.md>), [jira](<https://devfeed.tech/tags/jira.md>), [open-source](<https://devfeed.tech/tags/open-source.md>), [operational](<https://devfeed.tech/tags/operational.md>), [optimum](<https://devfeed.tech/tags/optimum.md>), [orders](<https://devfeed.tech/tags/orders.md>), [ratio](<https://devfeed.tech/tags/ratio.md>), [reference](<https://devfeed.tech/tags/reference.md>), [rework](<https://devfeed.tech/tags/rework.md>), [risk](<https://devfeed.tech/tags/risk.md>), [scheduling](<https://devfeed.tech/tags/scheduling.md>), [sequences](<https://devfeed.tech/tags/sequences.md>), [synthetic](<https://devfeed.tech/tags/synthetic.md>)

### AI overview

ODP (L0) sequences prerequisite-eligible feature blocks by choosing the lowest effort-and-risk-to-value ratio. On synthetic dependency graphs, unlocked-value (L2) and one-step rollout (L4) come closer to the surrogate optimum than L0, especially at larger sizes; on 373 Jira sprint proxies with sparse recorded dependencies, L0 reaches 0.998 of the surrogate optimum and is exactly optimal in 69% of sprints. Synthetic-calibrated unlock bonuses yield no significant average gain on the Jira-derived instances and can worsen the surrogate. Although L4 never worsens that surrogate relative to L0, retrospective calendar replays show surrogate gains do not reliably improve value-weighted completion. The evidence supports L0 as the default, with rollout and exact references as auditable alternatives. Effects on interruptions, rework, costs, and delivery times remain unmeasured.

### Source excerpt

arXiv:2611.23303v1 Announce Type: new Abstract: The Optimal Development Path (ODP) in D-POAF orders Feature Blocks in a Wave Candidate by choosing the eligible block with the lowest effort-and-risk-to-value ratio (ERS/BVS), while respecting declared prerequisites. We evaluate native ODP (L0) against four dependency-aware strategies: unlock count (L1), unlocked value (L2), multi-hop potential (L3), and one-step rollout (L4), alongside local search, Sidney decomposition, and an exact reference. On held-out synthetic graphs with about one prerequisite per block, L0 attains 0.978 of the surrogate optimum at 12 blocks, versus 0.993 for L2 and 0.994 for L4. At 100 blocks, L0 attains 0.942 and L2 0.983. In contrast, 373 historical Jira sprints from 21 open-source projects in TAWOS, used as scheduling proxies rather than D-POAF Waves, contain sparse recorded dependencies. On these instances, L0 attains 0.998 of the surrogate optimum and is exactly optimal in 69% of sprints. Unlock bonuses calibrated on synthetic graphs do not deliver significant average gains on these sprint-derived instances and can worsen the surrogate. L4 never worsens the declared surrogate relative to L0, but this guarantee does not extend to operational outcomes. Retrospective calendar replays using recorded Jira durations show that surrogate improvements do not reliably improve value-weighted completion. The findings support keeping L0 as the default and presenting rollout and exact references as auditable alternatives. Dependency-valid sequences expose prerequisite readiness, but their effects on interruptions, rework, costs, and delivery times remain unmeasured.

## Programmable Probabilistic Computer with 1,000,000 p-bits

DevFeed: [Programmable Probabilistic Computer with 1,000,000 p-bits](<https://devfeed.tech/articles/programmable-probabilistic-computer-with-1-000-000-p-bits-142961.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2606.25313>)

Author: Navid Anjum Aadit, Xiuqi Zhang, Shuvro Chowdhury, Kevin Callahan-Coray, Kyle Lee, Saleh Bunaiyan, Sanjay Seshan, Clayton Thomas, Jason Twigg, Andrew Seawright, Forrest Brewer, Tathagata Srimani, Kerem

Published: 2026-11-19T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [fpga](<https://devfeed.tech/topics/fpga.md>), [Distributed Systems & Parallel Computing](<https://devfeed.tech/topics/distributed-systems-parallel-computing.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Supercomputing](<https://devfeed.tech/topics/supercomputing.md>)

Tags: [architecture](<https://devfeed.tech/tags/architecture.md>), [bits](<https://devfeed.tech/tags/bits.md>), [boundary](<https://devfeed.tech/tags/boundary.md>), [computer](<https://devfeed.tech/tags/computer.md>), [cs-ar](<https://devfeed.tech/tags/cs-ar.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [energy](<https://devfeed.tech/tags/energy.md>), [exchange](<https://devfeed.tech/tags/exchange.md>), [field](<https://devfeed.tech/tags/field.md>), [gate](<https://devfeed.tech/tags/gate.md>), [gpu](<https://devfeed.tech/tags/gpu.md>), [graph](<https://devfeed.tech/tags/graph.md>), [interaction](<https://devfeed.tech/tags/interaction.md>), [interconnect](<https://devfeed.tech/tags/interconnect.md>), [learning](<https://devfeed.tech/tags/learning.md>), [limit](<https://devfeed.tech/tags/limit.md>), [local](<https://devfeed.tech/tags/local.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [memory](<https://devfeed.tech/tags/memory.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [probabilistic](<https://devfeed.tech/tags/probabilistic.md>), [sampling](<https://devfeed.tech/tags/sampling.md>)

### AI overview

The computer scales to one million interacting p-bits across 18 FPGAs, sustaining 10¹² probabilistic updates per second. Coupling weights stay in on-chip memory beside the update circuits, while devices exchange only single-bit boundary states. In spin-glass experiments, the ratio of boundary-exchange frequency to local-update frequency determines how communication delays affect optimization. A graph-partition and interconnect bound identifies conditions that recover the residual-energy decay of an unpartitioned GPU reference. Infrequent exchange lowers the decay exponent, though faster local updates can still reduce the time to reach a target energy. A cluster mean-field model reproduces the dependence, and ferromagnetic sampling shows a corresponding effect on magnetization relaxation. The abstract presents this frequency ratio as a design principle for larger probabilistic computers.

### Source excerpt

arXiv:2606.25313v2 Announce Type: replace Abstract: Many problems in physics and machine learning require sampling the collective states of large numbers of interacting variables. On modern graphics processors, repeated movement of interaction data between memory and compute units can limit how efficiently these calculations can scale. Here we demonstrate a programmable probabilistic computer with one million interacting probabilistic bits (p-bits) across 18 field-programmable gate arrays, sustaining $10^{12}$ probabilistic updates per second. Coupling weights remain beside the update circuits in on-chip memory, and only single-bit boundary states pass between devices. Experiments on three-dimensional and quasi-two-dimensional spin glasses show that the ratio of boundary-exchange frequency to local update frequency controls the effect of communication delays on optimization. A bound derived from the graph partition and interconnect identifies operating conditions that recover the residual-energy decay of an unpartitioned GPU reference. Infrequent exchange reduces the decay exponent, although faster local updates can shorten the time to reach a target energy. A cluster mean-field model reproduces this dependence, while ferromagnetic sampling experiments reveal a corresponding dependence of magnetization relaxation on the same frequency ratio. These results establish a million-p-bit computing architecture in which processing and local memory scale together, and provide a quantitative design principle for exploiting tolerance to communication delays in larger probabilistic computers.

## Infinity-Wasserstein Distributionally Robust Principal Component Analysis: Exact Reformulation, Finite-Sample Guarantee, and Efficient Algorithm

DevFeed: [Infinity-Wasserstein Distributionally Robust Principal Component Analysis: Exact Reformulation, Finite-Sample Guarantee, and Efficient Algorithm](<https://devfeed.tech/articles/infinity-wasserstein-distributionally-robust-principal-component-analysis-exact-reformulation-finite-sample-guarantee-and-efficient-algorithm-143459.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.23877>)

Author: Zhouxing Luo, Lei Wang, Xin Liu

Published: 2026-11-19T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Representation learning](<https://devfeed.tech/topics/representation-learning.md>), [Optimization](<https://devfeed.tech/topics/optimization.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [convergence](<https://devfeed.tech/tags/convergence.md>), [covariance](<https://devfeed.tech/tags/covariance.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [dimension-reduction](<https://devfeed.tech/tags/dimension-reduction.md>), [distribution](<https://devfeed.tech/tags/distribution.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [math-st](<https://devfeed.tech/tags/math-st.md>), [performance](<https://devfeed.tech/tags/performance.md>), [principal-component-analysis](<https://devfeed.tech/tags/principal-component-analysis.md>), [robust](<https://devfeed.tech/tags/robust.md>), [stat-me](<https://devfeed.tech/tags/stat-me.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [stat-th](<https://devfeed.tech/tags/stat-th.md>), [subspace](<https://devfeed.tech/tags/subspace.md>)

### AI overview

The paper proposes an infinity-Wasserstein distributionally robust PCA model that can reshape the nominal principal subspace while admitting an exact finite-dimensional reformulation and an explicitly identified worst-case distribution. Its objective retains samplewise residual information beyond empirical covariance. Assuming the true distribution has a finite fourth moment, the authors establish a uniform finite-sample performance guarantee. They also develop an iteratively reweighted majorization-minimization algorithm for the resulting nonconvex, nonsmooth problem and analyze its convergence. Numerical experiments are reported to support the algorithm's computational efficiency and the model's effectiveness in downstream applications.

### Source excerpt

arXiv:2611.23877v1 Announce Type: cross Abstract: Principal component analysis (PCA) is a fundamental and ubiquitous technique for dimension reduction and representation learning, yet its empirical formulation remains vulnerable to distributional uncertainty. While distributionally robust optimization (DRO) offers a natural remedy, existing order-2 Wasserstein models of PCA either preserve the nominal PCA subspace or lack an exact reformulation. This paper demonstrates how the infinity-Wasserstein distance can reconcile these two desirable properties. For the resulting DRO model of PCA, we derive an exact finite-dimensional reformulation and explicitly identify a worst-case distribution attaining the inner maximum. Crucially, the reformulated objective retains samplewise residual information beyond the empirical covariance matrix, revealing a mechanism through which distributional robustness can reshape the learned principal subspace. Under the mild assumption that the true distribution has a finite fourth moment, we further establish a uniform finite-sample performance guarantee for the proposed model. An iteratively reweighted majorization-minimization algorithm is also developed to solve the resulting nonconvex and nonsmooth optimization problem, with a rigorous analysis of its convergence properties. Numerical experiments substantiate the computational efficiency of the proposed algorithm and the practical effectiveness of the infinity-Wasserstein model in downstream applications.

## Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets

DevFeed: [Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](<https://devfeed.tech/articles/spatiotemporal-and-multi-robot-motion-planning-on-graphs-of-space-time-convex-sets-139786.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2607.00444>)

Author: Jingtao Tang, Zining Mao, Lufan Yang, Hang Ma

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Robot Navigation](<https://devfeed.tech/topics/robot-navigation.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>)

Tags: [continuous](<https://devfeed.tech/tags/continuous.md>), [convex](<https://devfeed.tech/tags/convex.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ro](<https://devfeed.tech/tags/cs-ro.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [motion](<https://devfeed.tech/tags/motion.md>), [motion-planning](<https://devfeed.tech/tags/motion-planning.md>), [planning](<https://devfeed.tech/tags/planning.md>), [pruning](<https://devfeed.tech/tags/pruning.md>), [quality](<https://devfeed.tech/tags/quality.md>), [robot](<https://devfeed.tech/tags/robot.md>), [robots](<https://devfeed.tech/tags/robots.md>), [route](<https://devfeed.tech/tags/route.md>), [scalability](<https://devfeed.tech/tags/scalability.md>), [search](<https://devfeed.tech/tags/search.md>), [simulations](<https://devfeed.tech/tags/simulations.md>), [space](<https://devfeed.tech/tags/space.md>), [temporal](<https://devfeed.tech/tags/temporal.md>), [time](<https://devfeed.tech/tags/time.md>), [timing](<https://devfeed.tech/tags/timing.md>), [velocity](<https://devfeed.tech/tags/velocity.md>)

### AI overview

The framework plans continuous robot motion in space and time by representing collision-free regions as convex sets, jointly optimizing the route and piecewise-linear trajectory timing under velocity limits. Exact Convex Decomposition removes swept space occupied by moving obstacles and previously planned robots while preserving a convex decomposition for later queries. A best-first solver uses temporal reachability for dominance pruning and admissible heuristics; heuristic bounds can be reused after reservation updates. The authors combine these methods with prioritized planning and dynamically adjusted coordination windows to limit graph growth. Experiments report improved scalability and competitive solution quality against optimization-based and sampling-based planners; simulations coordinate up to 100 robots within a minute, with real-robot demonstrations also reported.

### Source excerpt

arXiv:2607.00444v2 Announce Type: replace-cross Abstract: Decoupled multi-robot motion planning avoids the high-dimensional joint configuration space but requires repeated single-robot planning among moving obstacles, where route choice and timing are coupled. We develop a framework based on graphs of space-time convex sets (ST-GCSs) for continuous spatiotemporal planning and multi-robot coordination. An ST-GCS represents collision-free space-time by convex sets, allowing the sequence of regions and the geometry and timing of piecewise-linear trajectories to be optimized jointly under velocity limits. To incorporate moving obstacles and previously planned robots, we develop Exact Convex Decomposition (ECD), which removes their swept occupancies while maintaining a convex decomposition for subsequent planning queries. Building on path-based GCS search, we develop a best-first solver tailored to the ST-GCS motion model, exploiting temporal reachability for dominance pruning and using admissible heuristics with separate or joint search-key evaluation. Precomputed heuristic bounds can also be reused across reservation-updated graphs. We integrate ST-GCS planning and ECD into prioritized multi-robot planning and introduce windowed coordination with dynamic window adjustment to limit reservation-induced graph growth. Experiments demonstrate improved scalability and competitive solution quality against optimization-based and sampling-based planners on challenging spatiotemporal and multi-robot problems. Large-scale simulations coordinate up to $100$ robots within a minute, while real-robot demonstrations showcase the practical applicability of the framework. Project homepage: https://sites.google.com/view/stgcs.

## Balancing Exploration and Exploitation in Constrained Combinatorial Optimization with U(1)-Symmetric Tensor Trains

DevFeed: [Balancing Exploration and Exploitation in Constrained Combinatorial Optimization with U(1)-Symmetric Tensor Trains](<https://devfeed.tech/articles/balancing-exploration-and-exploitation-in-constrained-combinatorial-optimization-with-u-1-symmetric-tensor-trains-141787.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.22557>)

Author: Sergei Iudin, Mikhail Podobrii, Dmitry Zheltkov, Stanislav Moiseev

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>)

Tags: [combinatorial-optimization](<https://devfeed.tech/tags/combinatorial-optimization.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>)

### AI overview

The paper presents a U(1)-symmetric tensor-train framework for constrained combinatorial optimization, addressing scarce feasible points with sparse-tensor expressibility enhancement and graph-based diversity guidance for training sample selection. On assignment benchmarks, both techniques improve mean solution quality over their respective baselines. The assignment-selected diversity strategy also improves results on nonpolynomial Set Partitioning, with larger relative gains in higher-tensor-rank data families. Runtime benchmarks report substantial speedups over ConstrainTNet and PROTES on non-degenerate assignment workloads. Comparisons with simulated annealing vary with available constraint information and computational budget.

### Source excerpt

arXiv:2611.22557v1 Announce Type: cross Abstract: Tensor Train (TT) decomposition has emerged as a powerful tool for mitigating the curse of dimensionality in a variety of machine learning and combinatorial optimization tasks. Recent advances show that TT-based generative models can efficiently represent and explore high-dimensional discrete spaces, even when the cost function structure is unknown. However, incorporating hard linear constraints into TT-based optimization remains challenging, as existing interpolation and sampling approaches often fail when feasible points are rare. In this work, we develop a general TT-based framework for constrained combinatorial optimization built upon U(1)-symmetric tensor networks. Our method introduces an expressibility-enhancement mechanism for constructing sparse symmetric tensors and a graph-based diversity measure that guides sample selection during training. On assignment benchmarks, expressibility enhancement and diversity-aware selection improve mean solution quality over their respective baselines. The assignment-selected diversifying strategy also extends to nonpolynomial Set Partitioning, with larger relative gains observed in the higher-tensor-rank data families. Separate runtime benchmarks show substantial speedups over ConstrainTNet and PROTES on non-degenerate assignment workloads; comparisons with simulated annealing depend on constraint information and computational budget, but, overall, support the practicality of the current implementation.

## Graph neural networks and the energetic cavity method for combinatorial optimization

DevFeed: [Graph neural networks and the energetic cavity method for combinatorial optimization](<https://devfeed.tech/articles/graph-neural-networks-and-the-energetic-cavity-method-for-combinatorial-optimization-141604.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2609.07456>)

Author: Joe Bacchus George, George T. Cantwell

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>), [Deep learning](<https://devfeed.tech/topics/deep-learning.md>), [Neural Network](<https://devfeed.tech/topics/neural-network.md>)

Tags: [combinatorial-optimization](<https://devfeed.tech/tags/combinatorial-optimization.md>), [cond-mat-dis-nn](<https://devfeed.tech/tags/cond-mat-dis-nn.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [graph-neural-networks](<https://devfeed.tech/tags/graph-neural-networks.md>)

### AI overview

The study evaluates graph neural networks (GNNs) for approximating ground states of Ising models, which can represent many combinatorial optimization problems. Unmodified GNNs perform worse than two mean-field-based heuristics: a leading-eigenvector method and min-sum, also called the energetic cavity method. Incorporating these heuristics through small GNN modifications considerably improves performance and makes the approach stronger than other deep-learning methods. However, at the same computational cost, simulated annealing is generally as good. These findings are reported in the abstract; implementation details are not included in the supplied text.

### Source excerpt

arXiv:2609.07456v2 Announce Type: replace-cross Abstract: 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 much stronger than other deep learning approaches, we still find that simulated annealing is generally as good for the same computational cost.

## Colombo: A Frontier-to-Frontier Autoresearch System for Oracle-Based Optimization

DevFeed: [Colombo: A Frontier-to-Frontier Autoresearch System for Oracle-Based Optimization](<https://devfeed.tech/articles/colombo-a-frontier-to-frontier-autoresearch-system-for-oracle-based-optimization-140116.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.23080>)

Author: Haihan Zhang, Wendao Wu, Chenheng Zhang, Chunyuan Zheng, Yanyi Li, Cong Fang, Haoxuan Li, Zhouchen Lin

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [AI for science](<https://devfeed.tech/topics/ai-for-science.md>), [Operations research and optimization](<https://devfeed.tech/topics/operations-research-and-optimization.md>)

Tags: [adaptive](<https://devfeed.tech/tags/adaptive.md>), [adversarial](<https://devfeed.tech/tags/adversarial.md>), [ai](<https://devfeed.tech/tags/ai.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [atlas](<https://devfeed.tech/tags/atlas.md>), [autoresearch](<https://devfeed.tech/tags/autoresearch.md>), [certification](<https://devfeed.tech/tags/certification.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [formal](<https://devfeed.tech/tags/formal.md>), [frontier](<https://devfeed.tech/tags/frontier.md>), [independent](<https://devfeed.tech/tags/independent.md>), [lean](<https://devfeed.tech/tags/lean.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [memory](<https://devfeed.tech/tags/memory.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [oracle](<https://devfeed.tech/tags/oracle.md>), [research](<https://devfeed.tech/tags/research.md>), [science](<https://devfeed.tech/tags/science.md>), [system](<https://devfeed.tech/tags/system.md>)

### AI overview

Colombo is a self-organizing AI research system instantiated in oracle-based optimization. It maps gaps between achievable guarantees and unavoidable costs in a Complexity Atlas, then turns unresolved gaps into adaptive research programmes. Its Adversarial Co-Ascent develops algorithms alongside hard problem families to test information use and expose unavoidable costs. Independent review and Lean-based certification check claims, while long-term memory carries supported findings across settings. The abstract reports optimal or near-optimal rates for more than fifty Atlas settings; it does not provide details of those settings or the underlying proofs.

### Source excerpt

arXiv:2611.23080v1 Announce Type: new Abstract: Science advances from frontier to frontier as discoveries reshape what is known and create the basis for further discovery. We present Colombo, a self-organizing AI researcher that drives this renewal, first instantiated in oracle-based optimization. Here, the central question is how efficiently a problem class can be solved through a prescribed information interface and what costs no admissible algorithm can avoid. The gap between achievable guarantees and unavoidable limits defines the frontier recorded in its Complexity Atlas, a living map of frontier settings and the current state of knowledge. Self-Organization turns unresolved gaps into adaptive research programmes, coordinating conjecture formation, mathematical investigation, and replanning as evidence accumulates. Adversarial Co-Ascent develops algorithms and hard families through reciprocal challenge, exposing mechanisms of information use and concealment that guide stronger methods and proofs of unavoidable costs. Independent review and Lean-based formal certification check mathematical claims, while the Long-Term Memory carries supported findings and research experience across settings. To date, Colombo has established optimal or near-optimal rates for more than fifty settings in the Atlas. Colombo thus takes a concrete step toward Autopoietic Science: a scientific process whose validated advances regenerate the conditions of its own progress, continually reshaping how inquiry is organized and what it can discover.

## ASCEND: Automated Shockproof Cost-Efficient Network Design

DevFeed: [ASCEND: Automated Shockproof Cost-Efficient Network Design](<https://devfeed.tech/articles/ascend-automated-shockproof-cost-efficient-network-design-140398.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.21824>)

Author: Taha ValizadehAslani, Vaibhav Phatarpekar, Cameron Brackmann, Bala Ramachandran

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Networking](<https://devfeed.tech/sources/arxiv-networking.md>)

Topics: [Network design](<https://devfeed.tech/topics/network-design.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [ascend](<https://devfeed.tech/tags/ascend.md>), [automated](<https://devfeed.tech/tags/automated.md>), [based](<https://devfeed.tech/tags/based.md>), [candidate](<https://devfeed.tech/tags/candidate.md>), [circuits](<https://devfeed.tech/tags/circuits.md>), [combinatorial-optimization](<https://devfeed.tech/tags/combinatorial-optimization.md>), [core](<https://devfeed.tech/tags/core.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cs-ni](<https://devfeed.tech/tags/cs-ni.md>), [customer](<https://devfeed.tech/tags/customer.md>), [design](<https://devfeed.tech/tags/design.md>), [designing](<https://devfeed.tech/tags/designing.md>), [designs](<https://devfeed.tech/tags/designs.md>), [edge](<https://devfeed.tech/tags/edge.md>), [effective](<https://devfeed.tech/tags/effective.md>), [existing](<https://devfeed.tech/tags/existing.md>), [experimental](<https://devfeed.tech/tags/experimental.md>), [network](<https://devfeed.tech/tags/network.md>), [network-design](<https://devfeed.tech/tags/network-design.md>)

### AI overview

ASCEND uses a two-level optimization pipeline to design IP core networks over existing infrastructure, balancing resilience to probabilistic failures against implementation cost. Its outer Multi-Objective Particle Swarm Optimization (MOPSO) selects core sites and circuits; an inner integral Multi-Commodity Flow (MCF) model chooses edge circuits and maps both circuit types onto optical paths, prioritizing resource disjointness and latency. The performance objective includes an exponentially weighted vulnerability metric that penalizes infeasible designs. Experiments on multiple real-world networks report that ASCEND outperformed a manually engineered baseline on both resilience and implementation cost.

### Source excerpt

arXiv:2611.21824v1 Announce Type: new Abstract: Designing resilient and cost-effective IP network topologies over an existing physical infrastructure is a challenging combinatorial optimization problem, particularly at large scale and under extensive failure modeling assumptions. Traditional deterministic approaches struggle to jointly address resiliency against shock (large customer-impact outages) and implementation cost objectives when the number of candidate circuits grows quadratically with the number of sites to be interconnected. In this paper, we propose Automated Shockproof Cost-Efficient Network Design (ASCEND), a systematic design pipeline for IP core network optimization based on a two-level optimization framework. At the outer level, ASCEND uses Multi-Objective Particle Swarm Optimization (MOPSO) to select core sites and core circuits. Given a core design, the inner-level integral Multi-Commodity Flow (MCF) formulation selects edge circuits and maps both core and edge circuits onto optical (fiber/transport) paths while prioritizing resource disjointness and latency. Network designs are evaluated using two competing objectives: a performance cost capturing resiliency under probabilistic failure scenarios and an implementation cost. The performance cost incorporates an exponentially weighted vulnerability metric that explicitly penalizes infeasible configurations. Experimental results on multiple real-world networks demonstrate that ASCEND consistently identifies designs that outperform a manually engineered baseline in both resiliency and implementation cost.

## Multistage Contextual Optimization for Vehicle Repositioning

DevFeed: [Multistage Contextual Optimization for Vehicle Repositioning](<https://devfeed.tech/articles/multistage-contextual-optimization-for-vehicle-repositioning-140014.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.22330>)

Author: Jinyu Zhang, Di Huang, Zhiyuan Liu, Nikolas Geroliminis

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [benefit](<https://devfeed.tech/tags/benefit.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [gradient](<https://devfeed.tech/tags/gradient.md>), [new-york](<https://devfeed.tech/tags/new-york.md>), [new-york-city](<https://devfeed.tech/tags/new-york-city.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [parallel](<https://devfeed.tech/tags/parallel.md>), [ride-hailing](<https://devfeed.tech/tags/ride-hailing.md>), [stage](<https://devfeed.tech/tags/stage.md>), [vehicle](<https://devfeed.tech/tags/vehicle.md>)

### AI overview

The proposed multistage contextual optimization trains demand forecasts for ride-hailing vehicle repositioning using downstream decision performance. Its LP links vehicle accumulation to trip completion through a macroscopic fundamental diagram, while forecasts affect the objective and constraints and earlier decisions affect later stages through inherited state. The exact gradient accounts for these coupled effects; an adjoint based on reverse vector-Jacobian products avoids full solution and state-parameter Jacobians. To speed sequential stage evaluation, the authors introduce parallel blocks, proving finite-pass recovery of the serial trajectory and bounded gradient error with early stopping. On New York City data, the method reports 7.7-9.1% greater business benefit than the same predictor trained by mean squared error, beats the compared baselines, and exceeds the same policy supplied with realized demand. Eight workers reduced training time by 1.86x without reducing decision performance.

### Source excerpt

arXiv:2611.22330v1 Announce Type: new Abstract: Ride-hailing platforms reposition idle vehicles to improve spatial supply-demand balances. This problem is prediction-driven and multistage: at each stage, the platform forecasts future demand, executes current decisions, and uses the resulting state to initialize the next stage. We formulate a multistage linear program (LP) with a macroscopic fundamental diagram (MFD) linking accumulation to trip completion. We then develop a multistage contextual optimization approach that uses decision performance to train the prediction model. The learning problem combines multiple coupled stages, context that depends on earlier decisions, and predictions that affect the objective, the constraint matrix, and the right-hand side of the LP. We derive the exact gradient, which has three parts: parameters change forecasts and hence decisions; earlier decisions change the current decision through the inherited state; and this state also changes forecasts as context. An equivalent adjoint uses reverse vector-Jacobian products, avoiding full solution and state-parameter Jacobians. Finally, forward propagation solves many stage LPs one after another, which makes training slow. We propose a parallel block evaluation algorithm that solves blocks of consecutive stages in parallel and repeatedly feeds each block output to the next block. We prove that the algorithm recovers the serial trajectory within a finite number of passes and that its gradient error remains bounded when it stops early. On New York City ride-hailing data, multistage contextual optimization yields 7.7% to 9.1% more business benefit than the same predictor trained by mean squared error, outperforms all compared baselines from five paradigms, and even outperforms realized demand fed to the same policy. With eight workers, parallel block evaluation shortens training by a factor of 1.86 without loss of decision performance.

## AutoPBO: LLM-powered Optimization for Local Search PBO Solvers

DevFeed: [AutoPBO: LLM-powered Optimization for Local Search PBO Solvers](<https://devfeed.tech/articles/autopbo-llm-powered-optimization-for-local-search-pbo-solvers-139748.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2509.04007>)

Author: Yi Chu, Jinyuan Li, Yiwen Sun, Mengchuan Zou, Shaowei Cai

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Large Language Model](<https://devfeed.tech/topics/llm.md>), [LLM evaluation / benchmarking](<https://devfeed.tech/topics/llm-evaluation-benchmarking.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [application](<https://devfeed.tech/tags/application.md>), [benchmarks](<https://devfeed.tech/tags/benchmarks.md>), [boolean](<https://devfeed.tech/tags/boolean.md>), [competition](<https://devfeed.tech/tags/competition.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [framework](<https://devfeed.tech/tags/framework.md>), [integer-programming](<https://devfeed.tech/tags/integer-programming.md>), [language-models](<https://devfeed.tech/tags/language-models.md>), [llm](<https://devfeed.tech/tags/llm.md>), [local](<https://devfeed.tech/tags/local.md>), [mixed-integer-programming](<https://devfeed.tech/tags/mixed-integer-programming.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [search](<https://devfeed.tech/tags/search.md>)

### AI overview

AutoPBO uses large language models to automatically improve the heuristics of local search solvers for pseudo-Boolean optimization, a design task that often requires expert effort and manual tuning. The authors evaluate it on four public benchmarks, including a real-world benchmark, and compare it with six tools: local search solvers NuPBO and OraSLS, complete PB solvers PBO-IHS and RoundingSat, and MIP solvers Gurobi and SCIP. They report significant gains over prior local search approaches and competitive performance against the broader set of solvers. The supplied abstract does not specify the optimization mechanism or quantitative results.

### Source excerpt

arXiv:2509.04007v2 Announce Type: replace Abstract: Pseudo-Boolean Optimization (PBO) provides a powerful framework for modeling combinatorial problems through pseudo-Boolean (PB) constraints. Local search solvers have shown excellent performance in PBO solving, and their efficiency is highly dependent on their internal heuristics to guide the search. Still, their design often requires significant expert effort and manual tuning in practice. While Large Language Models (LLMs) have demonstrated potential in automating algorithm design, their application to optimizing PBO solvers remains unexplored. In this work, we introduce AutoPBO, a novel LLM-powered framework to automatically enhance PBO local search solvers. We conduct experiments on a broad range of four public benchmarks, including one real-world benchmark, a benchmark from PB competition, an integer linear programming optimization benchmark, and a crafted combinatorial benchmark, to evaluate the performance improvement achieved by AutoPBO and compare it with six state-of-the-art competitors, including two local search PBO solvers NuPBO and OraSLS, two complete PB solvers PBO-IHS and RoundingSat, and two mixed integer programming (MIP) solvers Gurobi and SCIP. AutoPBO demonstrates significant improvements over previous local search approaches, while maintaining competitive performance compared to state-of-the-art competitors. The results suggest that AutoPBO offers a promising approach to automating local search solver design.

## Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR

DevFeed: [Polylogarithmic Regret via Certainty Equivalence in Degenerate LQR](<https://devfeed.tech/articles/polylogarithmic-regret-via-certainty-equivalence-in-degenerate-lqr-141699.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.21927>)

Author: Luca Vignola, Melanie Zeilinger, Bruce D. Lee

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [control](<https://devfeed.tech/tags/control.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [cs-sy](<https://devfeed.tech/tags/cs-sy.md>), [eess-sy](<https://devfeed.tech/tags/eess-sy.md>), [exploration](<https://devfeed.tech/tags/exploration.md>), [feedback](<https://devfeed.tech/tags/feedback.md>), [input](<https://devfeed.tech/tags/input.md>), [lower-bound](<https://devfeed.tech/tags/lower-bound.md>), [math-oc](<https://devfeed.tech/tags/math-oc.md>), [minimax](<https://devfeed.tech/tags/minimax.md>), [online](<https://devfeed.tech/tags/online.md>), [range](<https://devfeed.tech/tags/range.md>), [state](<https://devfeed.tech/tags/state.md>), [systems](<https://devfeed.tech/tags/systems.md>), [variance](<https://devfeed.tech/tags/variance.md>)

### AI overview

Singular input penalties broaden when certainty equivalence can achieve polylogarithmic regret in online linear quadratic control. The paper proves that, when controller identifiability holds, a certainty-equivalence algorithm with a short initial exploration phase has expected regret O(log² T) over T interactions. A complementary Ω(√T) minimax lower bound applies to a family that includes a system where controller identifiability fails. For minimum variance control, knowing the range of the input matrix is sufficient for controller identifiability, a weaker requirement than knowing the full matrix under prior work with positive definite input penalties; the condition also covers underactuated systems, illustrated by a cart-pole example.

### Source excerpt

arXiv:2611.21927v1 Announce Type: cross Abstract: Singular input penalties, as in minimum variance control, can reduce what must be identified to control an unknown linear system. In online linear quadratic control, certainty equivalence can achieve polylogarithmic regret when the optimal controller is identifiable from data collected under optimal feedback. With a positive definite input penalty, however, this condition is restrictive, since for an invertible state matrix it requires all unknown parameters to be identifiable under optimal feedback. We show that singular input penalties relax this requirement, expanding the class of problems in which certainty equivalence achieves polylogarithmic regret. Specifically, we prove that a certainty-equivalence algorithm with a short initial exploration phase achieves $O(\log^2 T)$ expected regret over $T$ interactions whenever controller identifiability holds. We complement this guarantee with an $\Omega(\sqrt{T})$ minimax lower bound for a family containing a system where controller identifiability fails. For minimum variance control, knowing the range of the input matrix suffices for controller identifiability, a weaker requirement than knowing the full input matrix, as assumed in prior work with positive definite input penalties. This condition also covers underactuated systems, as we illustrate with a cart-pole example.

[Next page](<https://devfeed.tech/topics/combinatorial-optimization.md?cursor=WyIyMDI2LTExLTE4VDA1OjAwOjAwKzAwOjAwIiwgIjg4ZWIxMzBjLWNmZmEtNDA3MC04N2I4LTE4MTA2ZjJiNDI2ZSJd>)