论文检索

Optimization · Discrete and Combinatorial Optimization

Bin Chen, Shouliang Zhu, Beidan Liu, Yong Zhao, Tianle Pu, Huichun Li, Zhengqiu Zhu

Designing heuristics for combinatorial optimization problems (COPs) is a fundamental yet challenging task that traditionally requires extensive domain expertise. Recently, Large Language Model (LLM)-based Automated Heuristic Design (AHD) has shown promise in autonomously generating heuristic components with minimal human intervention. However, most existing LLM-based AHD methods enforce fixed algorithmic templates to ensure executability, which confines the search to component-level tuning and limits system-level algorithmic expressiveness. To enable open-ended solver synthesis beyond rigid templates, we propose Automated Algorithm Design via Evolutionary Program Trees (A$_2$DEPT), which treats LLMs as system-level algorithm architects. A$_2$DEPT explores the vast program space via a tree-structured evolutionary search with \textit{hybrid selection} and \textit{hierarchical operators}, enabling iterative refinement of complete algorithms. To make open-ended generation practical, we enforce executability with a lightweight program-maintenance loop that performs feedback-driven repair. In experiments, A$_2$DEPT consistently outperforms state-of-the-art baselines across standard and highly constrained benchmarks, reducing the optimality gap by an average of 9.8\%. Our work implies that system-level algorithm synthesis is a viable and scalable paradigm for LLM-driven optimization.

Optimization · Discrete and Combinatorial Optimization

Morteza Monemizadeh, Kiarash Banihashem, Peyman Jabbarzade, MohammadTaghi Hajiaghayi, Samira Goudarzi

Non-monotone submodular maximization is a fundamental problem in machine learning and combinatorial optimization, with a range of applications including text and video summarization, recommendation systems, feature selection, Max Cut problems in graphs, and viral marketing strategies. In this work, we study non-monotone submodular maximization under a cardinality constraint $k$ in the fully dynamic setting, and obtain results that improve upon the previously established approximation guarantees of $(0.125 - \epsilon)$ using $\tilde{O}(\epsilon^{-1}k^2)$ oracle queries per update (NeurIPS'20) and $0.171$ using $\tilde{O}(\epsilon^{-3}k^4)$ oracle queries per update (NeurIPS'25). We present a dynamic algorithm that achieves a $0.262$-approximation with worst-case expected update time $O(\epsilon^{-3}\log(k)\log(\epsilon^{-1}k) + \epsilon^{-2}k^2\log(k))$, where $0 < \epsilon \leq 1$ is the error parameter. We also obtain another dynamic algorithm with update time bounded by $\text{poly}(\epsilon^{-1}, k)$ that achieves a $0.277$-approximation guarantee.

Deep Learning · Large Language Models

Ruijie Shi, Houbin Zhang, Yuecheng Han, Yuheng Wang, Jingru Fan, Runde Yang, Yufan Dang, Huatao Li, Dewen Liu, Yuan Cheng 等

Large Language Models have shown strong capabilities in complex problem solving, yet many agentic systems remain difficult to interpret and control due to opaque internal workflows. While some frameworks offer explicit architectures for collaboration, many deployed agentic systems operate as black boxes to users. We address this by introducing Agentic Workflow Reconstruction (AWR), a new task aiming to synthesize an explicit, interpretable stand-in workflow that approximates a black-box system using only input--output access. We propose AgentXRay, a search-based framework that formulates AWR as a combinatorial optimization problem over discrete agent roles and tool invocations in a chain-structured workflow space. Unlike model distillation, AgentXRay produces editable white-box workflows that match target outputs under an observable, output-based proxy metric, without accessing model parameters. To navigate the vast search space, AgentXRay employs Monte Carlo Tree Search enhanced by a scoring-based Red-Black Pruning mechanism, which dynamically integrates proxy quality with search depth. Experiments across diverse domains demonstrate that AgentXRay achieves higher proxy similarity and reduces token consumption compared to unpruned search, enabling deeper workflow exploration under fixed iteration budgets.

Optimization · Discrete and Combinatorial Optimization

Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Danny Mittal

The standard oracle model for matroid algorithms assumes that each independence query can be answered in constant time, regardless of the size of the queried set. While this abstraction has underpinned much of the theoretical progress in matroid optimization, it masks the true computational effort required by these algorithms. In particular, for natural and widely studied classes such as graphic matroids, even a single independence query can require work linear in the size of the set, making the constant-time assumption implausible. We address this gap by introducing a size-sensitive cost model where the cost of a query $Q$ scales with $|Q|$. Nearly linear-time oracle implementations exist for broad families of matroids, and this refined abstraction therefore captures the true cost of query evaluation while allowing for a more faithful comparison between general matroids and their natural special cases. Within this framework we study three fundamental algorithmic tasks: finding a basis of a matroid, approximating its rank, and approximating its partition size. We establish tight results, proving nearly matching upper and lower bounds that show the optimal query cost is (up to logarithmic factors) quadratic in the size of the matroid. On the algorithmic side, our upper bounds are realized by explicit procedures that construct the desired solution. On the complexity side, our lower bounds are unconditional and already hold even for weaker distinguishing formulations of the problems. Finally, for matroids with maximum circuit size at most $c$, we show that the quadratic barrier can be broken, providing an algorithm that calculates the maximum-weight basis with expected query cost $\mathcal{O}(n^{2-1/c} \log n)$.

Optimization · Discrete and Combinatorial Optimization

Stefan Clarke, Bartolomeo Stellato

Mixed-integer optimization solvers often find optimal solutions early in the search, yet spend the majority of computation time proving optimality. We exploit this by learning when to terminate solvers early on distributions of similar problem instances. Our method trains a neural network to estimate the true optimality gap from the solver state, then uses conformal prediction to calibrate a stopping threshold with rigorous probabilistic guarantees on solution quality. On five problem families from the distributional MIPLIB library, our method reduces solve time by over 60% while guaranteeing 0.1%-optimal solutions with 95% probability.

Deep Learning · Generative Models and Autoencoders

Sizhuang He, Yangtian Zhang, Shiyang Zhang, David van Dijk

The finite symmetric group $S_n$ provides a natural domain for permutations, yet learning probability distributions on $S_n$ is challenging due to its factorially growing size and discrete, non-Euclidean structure. Recent permutation diffusion methods define forward noising via shuffle-based random walks (e.g., riffle shuffles) and learn reverse transitions with Plackett–Luce (PL) variants, but the resulting trajectories can be abrupt and increasingly hard to denoise as $n$ grows. We propose *Soft-Rank Diffusion*, a discrete diffusion framework that replaces shuffle-based corruption with a structured soft-rank forward process: we lift permutations to a continuous latent representation of order by relaxing discrete ranks into soft ranks, yielding smoother and more tractable trajectories. For the reverse process, we introduce *contextualized generalized Plackett–Luce (cGPL)* denoisers that generalize prior PL-style parameterizations and improve expressivity for sequential decision structures. Experiments on sorting and combinatorial optimization benchmarks show that Soft-Rank Diffusion consistently outperforms prior diffusion baselines, with particularly strong gains in long-sequence and intrinsically sequential settings.

Optimization · Discrete and Combinatorial Optimization

Ilay Yavlovich, Jad Agbaria, Jose Yallouz, Muhamed Mhamed, Nir Weinberger

The Linear Assignment Problem (LAP) is a fundamental combinatorial optimization task with applications ranging from computer vision to logistics. Classical exact solvers such as the Hungarian and Jonker--Volgenant (LAPJV) algorithms guarantee optimality, but their cubic time complexity $\mathcal{O}(N^3)$ becomes a bottleneck for large-scale instances. Recent learning-based approaches aim to replace these solvers with neural models, often sacrificing exactness or failing to scale due to memory constraints. We propose a *learning-augmented* framework that accelerates exact assignment solvers while maintaining optimality and worst-case guarantees. Our method predicts dual variables to warm-start a classical solver, with a fallback that prevents asymptotic runtime degradation when the learned advice is unreliable. We introduce **RowDualNet**, a lightweight row-independent architecture that avoids the $\mathcal{O}(N^2)$ memory bottleneck of graph-based models, enabling neural warm-starting at large scale ($N=16{,}384$). Feasibility is ensured via a constructive mechanism based on LP duality (namely, the *Min-Trick*), eliminating costly iterative projection. Empirically, our approach reduces the search effort of LAPJV and achieves over $2{\times}$ speedups on challenging synthetic distributions, in addition to improving over $1.25{\times}$ and $1.5{\times}$ on real-world tracking (MOT) and transportation (LPT) datasets, respectively, while strictly maintaining full optimality, effectively yielding a robust zero-shot generalization to real-world tasks.

Deep Learning · Generative Models and Autoencoders

Mingkun Lei, Tong Zhao, Liangyu Yuan, Chi Zhang

Step-level caching offers a promising avenue for accelerating diffusion models by exploiting temporal redundancy. However, existing strategies predominantly rely on heuristic, threshold-based metrics to trigger cache updates. This reactive paradigm is inherently myopic as it optimizes only for local feature consistency, and yields unpredictable deployment latency. In this work, we propose BudCache, a budget-constrained optimization framework that inverts this standard: instead of letting error thresholds dictate the cost, we enforce a strict computational budget and globally search for the caching policy that maximizes generation fidelity. To tackle the combinatorial complexity of step selection, we employ a hybrid strategy combining Simulated Annealing with deterministic Hill Climbing. This approach efficiently escapes local optima to locate globally optimized cache masks within minutes, incurring zero inference overhead. Crucially, to address the trajectory drift induced by aggressive caching, we introduce a cache-aware schedule alignment mechanism. By refining the time discretization via a lightweight, data-free distillation, we significantly enhance performance in low-NFE regimes. Extensive experiments on FLUX.1-dev and Wan2.1 demonstrate that BudCache consistently outperforms heuristic baselines, achieving superior perceptual quality under rigid latency constraints.

Optimization · Discrete and Combinatorial Optimization

Rongsheng Jia, Yifan Zhang, Jun Zhang, Jian Cheng

Recent decomposition-based approaches have achieved significant success in Multi-Objective Combinatorial Optimization (MOCO). However,existing methods typically rely exclusively on node-centric representations, failing to capture the complementary representations provided by edge features for problem instances, resulting in a persistent optimality gap. To address this , we propose a Preference-Modulated Structural Attention mechanism to enhance problem representation by synergizing node and edge features. It includes: (1) Utilizing preference-modulated edge features as explicit structural biases during attention calculation, enabling model to perceive sub-problem structures conditioned on specific preferences,and (2) an edge feature aggregation strategy that dynamically incorporates node-specific context into edge representations to enhance the perception of preference-aware structures. Experiments on classic MOCOP benchmarks demonstrate the superiority of our approach in terms of both performance and generalization capabilities.

Optimization · Discrete and Combinatorial Optimization

Samson Gourevitch, Alain Oliviero Durmus, Jimmy Olsson, Eric Moulines, Yazid Janati

Learning models with categorical variables requires optimizing expectations over discrete distributions, a setting in which stochastic gradient-based optimization is challenging due to the non-differentiability of categorical sampling. A common workaround is to replace the discrete distribution with a continuous relaxation, yielding a smooth surrogate that admits reparameterized gradient estimates via the reparameterization trick. Building on this idea, we introduce ReDGE, a novel and efficient diffusion-based soft reparameterization method for categorical distributions. Our approach defines a flexible class of gradient estimators that includes the Straight-Through estimator as a special case. Experiments spanning latent variable models and inference-time reward guidance in discrete diffusion models demonstrate ReDGE consistently matches or outperforms existing gradient-based methods.

Optimization · Discrete and Combinatorial Optimization

Cheng-Han Huang, Yongliang Sun, Chaoyan Huang, Ismail Alkhouri, Rongrong Wang

Many combinatorial optimization problems admit quadratic unconstrained binary formulations (QUBO) which can often be relaxed to the box $[0,1]^n$ and optimized using scalable gradient-based methods. However, the resulting non-convex landscape can often contain local optima that are spurious or infeasible. In this paper, we establish sufficient structural conditions on quadratic penalties that rule out these failures, guaranteeing that every local minimizer of the relax problem is both binary and feasible. For each problem we study, we examine existing QUBO formulations when available, identify why they fail when they do, and propose alternative relaxed QUBOs that satisfy our conditions. We show for several common combinatorial problems, including open-pit mining, knapsack, and traveling salesman formulations, that these constructions allow gradient-based methods such as projected gradient descent and Adam to be safely applied to obtain valid binary solutions. Our results clarify when differentiable optimization is a reliable local solver for quadratic combinatorial objectives.

Optimization · Discrete and Combinatorial Optimization

Josia John, Simon Meierhans, Maximilian Probst Gutenberg

In the graph label selection problem, one is given an $n$-vertex graph and a budget $k$, and seeks to select $k$ vertices whose labels enable accurate prediction of the labels on the remaining vertices. This problem formalizes distilling a small representative set from the whole graph. We present the first $\tilde{O}(\log^{1.5} n)$-approximation algorithm for graph label selection under the standard budget constraint. Prior work either relies on resource augmentation, allowing substantially more than $k$ labeled vertices, or consists primarily of heuristics without provable guarantees. Finally, we demonstrate that practical heuristic variants of our algorithm scale to significantly larger graphs than previous methods, while essentially retaining their quality.

Optimization · Discrete and Combinatorial Optimization

Pritish Chakraborty, Indradyumna Roy, Soumen Chakrabarti, Abir De

In recent years, there has been a surge in the application of neural approaches to NP-hard combinatorial problems such as subgraph isomorphism, maximum clique and the travelling salesman problem in graphs. These approaches are often evaluated as complete replacements of established combinatorial solver tools, with emphasis on solution quality and runtime. In this position paper, we argue that such wholesale replacements for touted faster inference or better solution quality should not be considered the primary motivation for neural surrogates, and a systematic evaluation of when neural methods are appropriate is required. Given our observations, we contend that in the absence of system-level requirements dictated by the task at hand, such as vector indexing and retrieval, or without the need for end-to-end differentiability, neural surrogates rarely offer compelling advantages over the standard combinatorial solver. In this vein, we develop a comprehensive report of where current neural methods fall short, and subsequently devise a diagnostic checklist for when neural methods are truly applicable.

Optimization · Discrete and Combinatorial Optimization

Dian Meng, Zhiguang Cao, Yaoxin Wu, Yaqing Hou

Multi-task vehicle routing solvers via deep reinforcement learning have attracted broad attention and achieved significant progress in handling multiple constraints. However, existing neural solvers still face critical challenges, including insufficient representation, unstable training, and inefficient exploration in large combinatorial action spaces, which often prevents performance from meeting its full potential. To address these issues, we propose PoMtVRS (Preference-Optimized Multi-Task Vehicle Routing Solver with Preference Gating), a plug-and-play framework that jointly improves decoder representations and exploration efficiency through a synergistic combination of decoder-side augmentation and preference-driven optimization. Specifically, we introduce the preference optimization objective to learn relative comparisons among candidate solutions for different routing tasks, encouraging a higher generation probability of better solutions. Meanwhile, we design a preference-gated block that adaptively modulates decoder representations via sparse gated attention and nonlinear residual refinement. Extensive experiments demonstrate that PoMtVRS elevates state-of-the-art unified neural VRP backbones, achieving leading performance in multi-task benchmarks and stronger generalization.

Optimization · Discrete and Combinatorial Optimization

Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

Large Language Models (LLMs) have enabled automated heuristic design (AHD) for combinatorial optimization problems (COPs), but existing frameworks' reliance on fixed evolutionary rules and static prompt templates often leads to myopic heuristic generation, redundant evaluations, and limited reasoning about how new heuristics should be derived. We propose a novel multi-agent reasoning framework, referred to as Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (PathWise), which formulates heuristic generation as a sequential decision process over an entailment graph serving as a compact, stateful memory of the search trajectory. This approach allows the system to carry forward past decisions and reuse or avoid derivation information across generations. A policy agent plans evolutionary actions, a world model agent generates heuristic rollouts conditioned on those actions, and critic agents provide routed reflections summarizing lessons from prior steps, shifting LLM-based AHD from trial-and-error evolution toward state-aware planning through reasoning. Experiments across diverse COPs show that PathWise converges faster to better heuristics, generalizes across different LLM backbones, and scales to larger problem sizes.

Optimization · Discrete and Combinatorial Optimization

Florian Adriaens, Nikolaj Tatti

Correlation clustering is a classic approach for summarizing signed graphs, where the goal is to cluster the graph while minimizing positive inter-cluster edges plus negative intra-cluster edges. On complete signed graphs, correlation clustering is closely related to the bad triangle traversal (BTT) problem of finding the smallest number of edges that need to be removed such that the remaining graph does not have a bad triangle. Here, a bad triangle is a triangle with exactly one negative edge. A known result states that a feasible bad triangle cover $F$ on a complete signed graph can be transformed into a correlation clustering with at most $2|F|$ mistakes. In this paper we improve this ratio to $\frac{3}{2}|F|$ mistakes using a pivot-based method. We also propose novel 2-approximations for BTT. Using a recent result on approximating the bad triangle cover LP, we obtain an $(2+\epsilon)$ approximation in time almost equal to the time needed to find a maximal set of edge-disjoint bad triangles (which would give a standard 3-approximation). Additionally, several inapproximability results are provided. For general signed graphs, a better than 2-approximation is unlikely as our problem can be used to approximate vertex cover. For complete signed graphs, it is NP-hard to approximate with factor better than $\frac{2137}{2136}$. This result also holds for several other related problems.

Optimization · Discrete and Combinatorial Optimization

Wenzheng Pan, Jiale Ma, Nuoyan Chen, Yang Li, Junchi Yan

Despite the fast progress of Neural Combinatorial Optimization (NCO) on graphs, existing solvers mainly learn a narrow task (e.g., uniform TSP) at a time and hardly handle instances over diverse distributions. This paper proposes M$^2$GenCO, a Multi-task learning framework that pioneers the instantiation of the Meta-learning mechanism with diffusion-based Generative solving for CO Problems (COPs) on graphs, first formulating "tasks" in meta-learning as distinct problem types instead of instances of the same problem. With a tailored lightweight graph neural network, our framework performs effective joint pre-training on a variety of problem types and efficient fine-tuning to adapt for out-of-distribution scenarios. Further, we establish a benchmark comprising 5 classic graph COPs with varying scales and multiple distributions, forming 38 distinct test datasets that facilitate standard evaluation of generalizability and adaptability for NCO solvers. Empirically, M$^2$GenCO with greedy decoder yields an overall 9.16% performance gain with an average 95.6$\times$ acceleration for inference, and achieves concrete state-of-the-arts on all test sets with simple local searchers, maintaining superior solving time against previous neural methods. The computational resource and time consumption for training are saved by up to 82% and 91%, respectively.

Optimization · Discrete and Combinatorial Optimization

Tongkai Lu, Shuai Ma, Chongyang Tao

Mixed Integer Linear Programming (MILP) is a fundamental NP-hard problem that has garnered significant attention from both academia and industry. The Branch-and-Bound (B&B) algorithm is the dominant approach for solving MILPs, where branching decisions play a critical role and have recently been enhanced by neural methods. However, these methods still struggle with semantic variation across depths, the scarcity of upstream nodes, and the costly collection of strong branching samples. To address these issues, we propose SC-MILP, a Dynamic Stratified Contrastive Training Framework for MILP Branching. Our method groups B&B nodes based on their feature distributions and learns depth-aware, fine-grained node representations through dynamic stratified contrastive training. To address data scarcity and imbalance at upstream nodes, we introduce an upstream-augmented MILP derivation procedure that generates both theoretically equivalent and perturbed instances. Experiments on both synthetic and real-world MILP benchmarks, including large-scale instances, show that SC-MILP significantly improves branching accuracy, reduces solving time, with particularly strong gains at upstream nodes.

Optimization · Discrete and Combinatorial Optimization

Zhen Liu, Yuhan Liu, Jinjun Wang, Wei Song, Jianyi Liu, Jingwen Fu

This paper focuses on a key challenge in Neural Architecture Search (NAS): integrating established architectural knowledge while exploring new designs under expensive evaluations. Large language models (LLMs) are a promising assistant for NAS because they can translate rich architectural and coding priors into executable code edits. However, in practice, seemingly local revisions often propagate into non-local behavioral and performance shifts because a single edit can inadvertently couple multiple interacting functional factors, a phenomenon we refer to as functional entanglement. To make LLM knowledge usable under such entanglement, we propose Structured Progressive Knowledge Activation (SPARK), which activates relevant priors by explicitly selecting the functional factor to modify and conditioning the edit on that factor. This factor-conditioned editing reduces entangled side effects and yields more targeted, reliable architecture modifications. On CLRS-DFS, SPARK reduces the number of training evaluations by {28.1$\times$} over EvoPrompting and improves OOD accuracy by {+15.6} points, with essentially unchanged compute ({$\sim$453K MACs}).

Optimization · Discrete and Combinatorial Optimization

Junhao Qiu, Xin Chen, LiangGE, Liyong Lin, Zhichao Lu, Qingfu Zhang

Neighborhood search operators are critical to the performance of Multi-Objective Evolutionary Algorithms (MOEAs) and rely heavily on expert design. Although recent LLM-based Automated Heuristic Design (AHD) methods have made notable progress, they primarily optimize individual heuristics or components independently, lacking explicit exploration and exploitation of dynamic coupling relationships between operators. In this paper, multi-operator optimization in MOEAs is formulated as a Markov decision process, enabling the improvement of interdependent operators through sequential decision-making. To address this, we propose the Evolution of Operator Combination (E2OC) framework for MOEAs, which achieves the co-evolution of design strategies and executable codes. E2OC employs Monte Carlo Tree Search to progressively search combinations of operator design strategies and adopts an operator rotation mechanism to identify effective operator configurations while supporting the integration of mainstream AHD methods as the underlying designer. Experimental results across AHD tasks with varying objectives and problem scales show that E2OC consistently outperforms state-of-the-art AHD and other multi-heuristic co-design frameworks, demonstrating strong generalization and sustained optimization capability.