Tag
The paper introduces Scone, a symmetry-aware model using a color-equivariant graph neural network to sequentially construct graph colorings, exploiting permutation symmetry of colors while breaking automorphism orbit symmetries. Scone achieves perfect solution quality with low inference times on tasks like sudoku_extreme and register allocation, generalizing to unseen graph families.
The paper explains how Dmitry Rybin used ChatGPT to find a seven-vertex counterexample to Goemans's long-standing unsplittable-flow conjecture, and develops a theory-guided forward construction pipeline based on a conflict polytope that characterizes all counterexamples on the topology and generalizes to 93 other arborescence shapes via ChatGPT.
A technical report on a hybrid exact-heuristic solver for the SOICT 2026 Integrated Passenger and Parcel Transportation contest, combining greedy insertion, ALNS with simulated annealing, and a branch-and-bound set-packing engine strengthened by Lagrangian bounds, achieving a total benefit of 487,237 on 38 scored instances.
A paper proposing ILP, GRASP, LBBD, and a novel Branch-and-Benders-Cut approach for the Minimum Red–Blue Separating Set Problem, with an application to distinguishing human- and AI-generated text via vocabulary-based graph features.
该论文提出一种融合空间启发式策略的扩散强化学习方法用于在线3D装箱问题,通过启发式动作预筛、图神经网络建模空间结构以及包含平整度的复合奖励函数,提升了布局优化能力与泛化性。
Evo-B&B提出一个由LLM引导的进化框架,联合演化混合整数线性规划中分支与节点选择策略,并通过行为感知的多岛屿机制保持种群多样性,在多个标准基准上取得有竞争力的求解性能与良好泛化能力。
该论文提出一种基于学习的列预填充方法来加速分支定价切割(BPC)精确求解器:用神经网络边打分器生成普通列池并配合Wentges平滑的预测初始中心,在RouteOpt中将根节点定价时间降至原来的13.2%,并在无关并行机调度问题上实现12倍加速。
FDE-Bench 是首个基于真实客户项目构建的基准,用于评估 AI 代理在需求不明确的真实商业请求下进行端到端交付的能力,涵盖 49 个组合优化与机器学习案例。结果显示,18 种代理配置中最高平均交付分仅为 0.5510(FDE 参考为 1.0),最高交付成功率仅 6.12%,表明代理尚未达到 FDE 级别的端到端交付水平。
Qualcomm AI Research 展示了将 Combinatorial Multigrid 图粗化作为热启动与 Particle Polynomial Relaxation 非凸连续重构相结合,能在计算受限条件下更有效地逃离 MAX-CUT 的局部最优,在 Biq Mac 和 G-set 基准上取得接近最优的结果并大幅降低内存占用。
A Nature Machine Intelligence paper showing that large language models can discover complementary heuristics for combinatorial optimization problems, improving solution quality by combining LLM-generated strategies.
HeurEvo introduces an automated plan–code–component co-evolution framework in which AI agents jointly evolve algorithmic structure, executable implementations, and a shared pool of reusable components for hybrid solver-augmented heuristics. Across combinatorial optimization benchmarks and MIPLIB instances, it matches or surpasses state-of-the-art solvers under tight runtime budgets and sets new results on problems such as hexagon packing.
该论文通过行为分析、表示探查和因果干预,研究了AM、POMO和LEHD等神经组合优化(NCO)路由求解器的内部决策机制,揭示了不同架构在构造解决方案时的差异化模式,例如LEHD依赖当前节点表示进行局部决策、起始节点提供全局导航参考。
The paper proposes a general self-supervised learning framework for combinatorial optimization using Frank-Wolfe methods to handle constraints, with strong empirical results on problems like TSP, Maximum Coverage, and QAP.
This paper introduces a graph-based deep reinforcement learning framework for the one-dimensional bin packing problem, reducing optimality gaps compared to existing methods and enabling zero-shot generalization across instance sizes.
The paper proposes a Dual-GNN Multilevel Coarsening framework to solve the maximum independent set problem efficiently by combining graph neural networks with combinatorial search, achieving near-optimal solutions with significant speedup on benchmark graphs.
This paper presents an unsupervised graph neural network framework for solving the Minimum Dominating Set problem, achieving significant speed improvements and generalization for influence maximization in social networks.
This paper introduces hLLM, a decoding strategy for generative reranking that uses the Hungarian algorithm to achieve single-pass decoding, resulting in a 64x speed-up while maintaining ranking quality.
This paper investigates hybrid quantum-classical neural networks for the vehicle routing problem, finding that encoder feed-forward replacement can reduce model parameters by 56.6% while maintaining near-baseline performance for small to medium instances.
This paper proposes a data-driven framework using graph neural networks to enhance Tabu search by predicting candidate moves' quality, improving efficiency in tactical wireless network design problems.
This paper investigates why standard neural architectures fail to generalize to longer inputs in dynamic programming, using geometric analysis with tropical semiring theory to reveal structural limitations in compositions.