Combinatorial Optimization

Follow this topic Ask about this topic

Momentum

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

Jul 13Week of Sep 28

Latest papers 277

All topics

Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers
May 12, 2026Haoyu Wang, Yuliang Song, Tao Li +5Large Language Model-Guided Optimization LLM-Based Program Synthesis
University of Pennsylvania · University of Toronto · Google DeepMind +1
QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning
May 12, 2026Kien X. Nguyen, Ankit Kulshrestha, Ilya Safro +1Quantum Circuit Compilation Combinatorial Optimization
Department of Computer and Information Sciences, University of Delaware, USA · Quantum Lab, Fujitsu Research of America, USA
Optimal Policy Learning under Budget and Coverage Constraints
May 12, 2026Giovanni CerulliPolicy Optimization Combinatorial Optimization
CNR-IRCrES · National Research Council of Italy · Research Institute on Sustainable Economic Growth
Network-Based Interventions for HIV Prevention via Cascade-Aware Suppression of Transmission
May 11, 2026Akseli Kangaslahti, Davin Choo, Milind Tambe +2Healthcare Combinatorial Optimization
Harvard University · University of Witwatersrand · Wits Health Consortium +1
Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver
May 11, 2026Canhong Yu, Changliang Zhou, Rongsheng Chen +2Neural Network Optimization Combinatorial Optimization
College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, China · School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China · Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University of Science and Technology, Shenzhen, China +1
A cell-decomposition based path planner for 3D navigation in constrained workspaces
May 11, 2026João P. L. Morais, Luciano C. A. Pimenta, Marcelo A. Santos +1Combinatorial Optimization Motion Planning
Graduate Program in Electrical Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil · Department of Management, Information and Production Engineering, University of Bergamo, Dalmine, BG, Italy · Department of Electronic Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil
Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
May 10, 2026Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed +2Neural Network Optimization Combinatorial Optimization
Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.
Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits
May 10, 2026Zhiming Huang, Bingshan Hu, Jianping PanThompson Sampling Multi-Armed Bandits
Paul G. Allen School of Computer Science & Engineering, University of Washington, WA, USA · Department of Computer Science, University of British Columbia, BC, Canada · Department of Computer Science, University of Victoria, BC, Canada
Omni-scale Learning-based Sequential Decision Framework for Order Fulfillment of Tote-handling Robotic Systems
May 9, 2026Jiaxin Liu, Peng Yang, Yuping Li +1Combinatorial Optimization Robotics
Institution of Data and Information, Shenzhen International Graduate School, Tsinghua University, Nanshan District, Shenzhen 518055, China
AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design
May 9, 2026Haoze Lv, Ning Lu, Ziang Zhou +1Agentic RL Automated Heuristic Design
Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology · Zhongguancun Academy · The Hong Kong University of Science and Technology
HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization
May 8, 2026Yuping Yan, Jirui Han, Fei Ming +2Multi-Agent LLM Systems Multi-Agent System Optimization
School of Engineering Westlake University
Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks
May 8, 2026Hao Chen, Chendi Qian, Christopher Morris +2Semidefinite Programming Graph Neural Networks
1Davidson School of Chemical Engineering, Purdue University · Faculty of Computer Science, RWTH Aachen University · 3Jacobs Technion-Cornell Institute, Cornell Tech
Optimal Counterfactual Search in Tree Ensembles: A Study Across Modeling and Solution Paradigms
May 7, 2026Awa Khouna, Youssouf Emine, Julien Ferry +1Counterfactual Explanations Mixed-Integer Linear Programming
Polytechnique Montréal · Ivey Business School
Back to the Beginning of Heuristic Design: Bridging Code and Knowledge with LLMs
May 7, 2026Nguyen Viet Tuan Kiet, Bui Dinh Pham, Dao Van Tung +2Automated Heuristic Design Large Language Model-Guided Optimization
Hanoi University of Science and Technology, Hanoi, Vietnam · University of Sydney, Sydney, Australia
Graph Normalization: Fast Binarizing Dynamics for Differentiable MWIS
May 6, 2026Laurent GuiguesDynamical Systems Replicator Dynamics
Exact and Evolutionary Algorithms for Sequential Multi-Objective Transmission Topology Planning
May 5, 2026Job Groeneveld, Miguel Muñoz, Jan Viebahn +1Multi-Objective Evolutionary Optimization Combinatorial Optimization
TenneT TSO B.V., Arnhem, The Netherlands · Artelys, Paris, France · Department of Mathematics, Vrije Universiteit Amsterdam, The Netherlands
Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS
May 5, 2026Tong Guo, Caishun Chen, Yew Soon OngAutomated Algorithm Discovery Large Language Model-Guided Optimization
College of Computing and Data Science, Nanyang Technological University, Singapore
Computing Thiele Rules on Interval Elections and their Generalizations
May 4, 2026Dimitris Avramidis, Alexandra Lassota, Ulrike Schmidt-Kraepelin +1Social Choice Theory Combinatorial Optimization
Department of Mathematics and Computer Science Eindhoven University of Technology Eindhoven, Netherlands · School of Computer Science, and Department of Mathematics and Statistics McGill University Montréal, Canada
Hybrid Quantum Reinforcement Learning with QAOA for Improved Vehicle Routing Optimization
May 2, 2026T. Satyanarayana Murthy, B. Swathi Sowmya, Santhosh Voruganti +3Quantum Machine Learning Combinatorial Optimization
Chaitanya Bharathi Institute of Technology Hyderabad, India
Matroid Algorithms Under Size-Sensitive Independence Oracles
Apr 30, 2026Kiarash Banihashem, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz +1Query Complexity Oracle Complexity
*Equal contribution 1Department of Computer Science, University of Maryland, College Park, USA.
Design Structure Matrix Modularization with Large Language Models
Apr 30, 2026Shuo Jiang, Jianxi LuoLarge Language Model-Guided Optimization Combinatorial Optimization
Department of Systems Engineering City University of Hong Kong, Hong Kong
Online combinatorial optimization with stochastic decision sets and adversarial losses
Apr 28, 2026Gergely Neu, Michal ValkoMulti-Armed Bandits Exploration-Exploitation Tradeoff
SequeL team, INRIA Lille – Nord Europe, France
An Analysis of the Coordination Gap between Joint and Modular Learning for Job Shop Scheduling with Transportation Resources
Apr 27, 2026Moritz Link, Jonathan Hoss, Noah KlarmannMulti-Agent Coordination Combinatorial Optimization
Faculty of Management and Engineering, University of Applied Sciences, 83024 Rosenheim, Germany
A2DEPT: Large Language Model-Driven Automated Algorithm Design via Evolutionary Program Trees
Apr 27, 2026Bin Chen, Shouliang Zhu, Beidan Liu +4Automated Algorithm Discovery Automated Heuristic Design
The Institute of Intelligent Computing, University of Electronic Science and Technology of China, Chengdu 611731, China · College of Systems Engineering, National University of Defense Technology, Changsha 410073, China · Academy of Military Medical Sciences, Beijing 100071, China
Query-Efficient Quantum Approximate Optimization via Graph-Conditioned Trust Regions
Apr 27, 2026Molena HuynhBlack-Box Optimization Combinatorial Optimization
North Carolina State University
Crystal structure prediction using graph neural combinatorial optimization
Apr 27, 2026Stavros Gerolymatos, J. Kyle Brubaker, Martin J. A. Schuetz +1Graph Neural Networks Crystal Structure Prediction
School of Computer Science and Informatics, University of Liverpool, Liverpool, England, UK · Amazon Advanced Solutions Lab, Seattle, Washington 98170, USA · Arm Inc., San Jose, California 95134
ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs
Apr 24, 2026Weimin Huang, Natalie M. Isenberg, Ján Drgoňa +2Combinatorial Optimization Mixed-Integer QP
University of Southern California, USA · Pacific Northwest National Laboratory, USA · Johns Hopkins University, USA
Fast and Effective Redistricting Optimization via Composite-Move Tabu Search
Apr 24, 2026Hai Jin, Diansheng GuoCombinatorial Optimization Constrained Optimization
Department of Land Surveying and Geo-Informatics, The Hong Kong Polytechnic University, Kowloon, Hong Kong, China
A general optimization solver based on OP-to-MaxSAT reduction
Apr 23, 2026Yuxin Zhao, Han Huang, Zhifeng HaoCombinatorial Optimization Maximum Satisfiability
School of Software Engineering, South China University of Technology, Guangzhou, 510006, China. · School of Software Engineering, Sun Yat-sen University, Zhuhai, 519082, China. · Department of Mathematics, College of Science, Shantou University, Shantou, 515063, China.
The CriticalSet problem: Identifying Critical Contributors in Bipartite Dependency Networks
Apr 23, 2026Sebastiano A. Piccolo, Andrea TagarelliCombinatorial Optimization
University of Calabria, DeMaCS – Dept. Mathematics and Computer Science · University of Calabria, DIMES – Dept. Computer Engineering, Modeling, Electronics, and Systems Engineering

May 12, 2026, cs.AIJ/K move · Enter open · S save

Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers

Haoyu Wang, Yuliang Song, Tao Li, Zhiwei Deng+4

University of Pennsylvania · University of Toronto · Google DeepMind+1

Large Language Model-Guided Optimization LLM-Based Program Synthesis Combinatorial Optimization Natural Language to Optimization Modeling Constraint Programming

Open paper AskPDF arXiv

Large Language Models (LLMs) struggle to solve complex combinatorial problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers. A central design question is how the LLM should represent the solver, and whether it should also attempt to optimize search. We introduce CP-SynC-XL, a benchmark of 100 combinatorial problems (4,577 instances), and evaluate three solver-construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling (MiniZinc + OR-Tools). We find a consistent representational divergence: Python + OR-Tools attains the highest correctness across LLMs, while MiniZinc + OR-Tools has lower absolute coverage despite using the same OR-Tools back-end. Native Python is the most likely to return a schema-valid solution that fails verification, whereas solver-backed paths preserve higher conditional fidelity. On the heuristic axis, prompting for search optimization yields only small median speed-ups (1.03-1.12x) and a strongly bimodal effect: many instances slow down, and correctness drops sharply on a long tail of problems. A paired code-level audit traces these regressions to a recurring heuristic trap. Under an efficiency-oriented prompt, the LLM may replace complete search with local approximations (Python), inject unverified bounds (Python + OR-Tools), or add redundant declarative machinery that overwhelms or over-constrains the model (MiniZinc + OR-Tools). These findings support a conservative design principle for LLM-generated combinatorial solvers: use the LLM primarily to formalize variables, constraints, and objectives for verified solvers, and separately check any LLM-authored search optimization before use.

Momentum

Related topics

Latest papers 277