Combinatorial Optimization

Ask about this topic

Overview

Combinatorial optimization studies how to choose the best arrangement, assignment, route, or schedule when decisions are discrete and constraints interact. Exact methods such as integer programming, constraint programming, SAT, dynamic programming, and branch-and-bound can certify optimality, while approximation algorithms and metaheuristics trade guarantees for speed on larger instances. Learning methods—including graph neural networks, reinforcement learning, and language-model-guided heuristic design—are increasingly paired with classical search to propose solutions, warm-start solvers, or select algorithms. A central challenge is making these methods scale and generalize without sacrificing feasibility, solution quality, or the guarantees that exact and approximation methods provide.

Latest papers

CardsList

386 papers47 papers in the last four weeks, up 47% on the four weeks before. 0.3% of all new papers.

  1. Scalable Inspection Planning via Flow-based Mixed Integer Linear Programming

    Mar 17, 2026Adir Morgan, Kiril Solovey, Oren SalzmanRobotic InspectionCombinatorial Optimization

    Technion–Israel Institute of Technology, Haifa, Israel

  2. Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling

    Mar 17, 2026Yuan Tian, Yi Mei, Mengjie ZhangResource-Constrained Project SchedulingGenetic Programming

    Centre for Data Science and Artificial Intelligence & School of Engineering and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New Zealand

  3. A General Deep Learning Framework for Wireless Resource Allocation under Discrete Constraints

    Mar 17, 2026Yikun Wang, Yang Li, Yik-Chung Wu +1Wireless Resource AllocationWireless Communications

    Department of Electrical and Electronic Engineering, The University of Hong Kong, Hong Kong · School of Computing and Information Technology, Great Bay University, Dongguan 523000, China · Department of Electrical and Computer Engineering, National University of Singapore, Singapore

  4. Towards Solving Polynomial-Objective Integer Programming with Hypergraph Neural Networks

    Mar 16, 2026Minshuo Li, Yaoxin Wu, Pavel Troubil +2Combinatorial OptimizationNeural Combinatorial Optimization

    Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, the Netherlands · Eindhoven Artificial Intelligence Systems Institute, Eindhoven University of Technology, Eindhoven, the Netherlands · Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, Eindhoven, the Netherlands +1

  5. UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization

    Mar 12, 2026Kien X. Nguyen, Ilya SafroCombinatorial OptimizationNeural Combinatorial Optimization

    Department of Computer and Information Sciences, University of Delaware, Newark DE 19716, USA

  6. Algebraic Structure Discovery for Real World Combinatorial Optimisation Problems: A General Framework from Abstract Algebra to Quotient Space Learning

    Mar 10, 2026Min Sun, Federica Storti, Valentina Martino +2Combinatorial Optimization

    F. Hoffmann-La Roche AG, Roche Pharma Research and Early Development

  7. Cluster-Aware Attention-Based Deep Reinforcement Learning for Pickup and Delivery Problems

    Mar 9, 2026Wentao Wang, Lifeng Han, Guangyu ZouVehicle RoutingRL for Combinatorial Optimization

    Leicester International Institute, Dalian University of Technology, Panjin, 124221, Liaoning, China. · Department of Electronic and Information Technology, Dalian University of Technology, Panjin, 124221, Liaoning, China.

  8. Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions

    Mar 9, 2026Xuanfeng Li, Shengcai Liu, Wenjie Chen +2Chance-Constrained OptimizationCombinatorial Optimization

    Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China · School of Information Management, Central China Normal University, Wuhan 430079, China · Centre for Frontier AI Research, Institute of High Performance Computing, Agency for Science Technology and Research, Singapore 138632 +1

  9. Column Generation for the Micro-Transit Zoning Problem

    Mar 8, 2026Hins Hu, Rishav Sen, Jose Paolo Talusan +3Combinatorial OptimizationUrban Planning

    Cornell University · Vanderbilt University · Pennsylvania State University

  10. Large Language Model for Discrete Optimization Problems: Evaluation and Step-by-step Reasoning

    Mar 8, 2026Tianhao Qian, Guilin Qi, Z. Y. Wu +3LLM EvaluationLarge Language Model-Guided Optimization

    School of Mathematics, Southeast University, Nanjing, China · School of Computer Science and Engineering, Southeast University, Nanjing, China · School of Mathematical Sciences, Chongqing Normal University, Chongqing, China

  11. CDEoH: Category-Driven Automatic Algorithm Design With Large Language Models

    Mar 8, 2026Yu-Nian Wang, Shen-Huan Lyu, Ning Chen +3Automated Heuristic DesignAutomated Algorithm Discovery

    Key Laboratory of Water Big Data Technology of Ministry of Water Resources, College of Computer Science and Software Engineering, Hohai University, Nanjing, China · Department of Computer Science, City University of Hong Kong, Hong Kong, China · State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China

  12. DyACE: Dynamic Algorithm Co-evolution for Online Automated Heuristic Design with Large Language Model

    Mar 7, 2026Guidong Lu, Yiping Liu, Xiangxiang ZengAutomated Heuristic DesignCombinatorial Optimization

  13. RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States

    Mar 7, 2026Xiangjie Xiao, Cong Zhang, Wen Song +1Flexible Job Shop SchedulingJob Shop Scheduling

    School of Computing and Information Systems, Singapore Management University, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore · Institute of Marine Science and Technology, Shandong University, China

  14. Learning to Solve Orienteering Problem with Time Windows and Variable Profits

    Mar 6, 2026Songqun Gao, Zanxi Ruan, Patrick Floor +3Learning to OptimizeCombinatorial Optimization

    Department of Industrial Engineering, Università di Trento, Trento, Italy · Interdepartmental Robotics Labs (IDRA), Trento, Italy · Department of Engineering for Innovation Medicine, Università di Verona, Verona, Italy +2

  15. MIRACL: A Diverse Meta-Reinforcement Learning for Multi-Objective Multi-Echelon Combinatorial Supply Chain Optimisation

    Mar 5, 2026Rifny Rachman, Josh Tingey, Richard Allmendinger +3Supply Chain OptimizationMulti-Objective Reinforcement Learning

    The University of Manchester, United Kingdom · Peak AI, Ltd, United Kingdom

  16. Agentic Service Markets Across the Computing Continuum: A Polymatroidal Architecture

    Mar 5, 2026Lauri Lovén, Alaa Saleh, Reza Farahani +5Mechanism DesignCombinatorial Optimization

    Future Computing Group, University of Oulu, Finland · Distributed Systems Group, TU Wien, Vienna, Austria · Department of Mechatronics, University of Prishtina, Kosova +4

  17. ReVEL: Multi-Turn Reflective LLM-Guided Heuristic Evolution via Structured Performance Feedback

    Mar 5, 2026Cuong Van Duc, Minh Nguyen Dinh Tuan, Tam Vu Duc +4Automated Heuristic DesignLarge Language Model-Guided Optimization

    VinMotion · Hanoi University of Science and Technology · VinUniversity +2

  18. Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling

    Mar 3, 2026Jiaqi Wang, Zhiguang Cao, Peng Zhao +4Flexible Job Shop SchedulingJob Shop Scheduling

    Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University · College of Software, Jilin University · Singapore Management University +2

  19. Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity

    Feb 28, 2026Anoop Bhat, Geordan Gutow, Zhongqiang Ren +2Vehicle RoutingCombinatorial Optimization

    Robotics Institute at Carnegie Mellon University, Pittsburgh, PA 15213 · Mechanical and Aerospace Engineering at Michigan Technological University, Houghton, MI 49931 · UM-SJTU Joint Institute and Department of Automation at Shanghai Jiao Tong University, Shanghai, China +1

  20. Universal NP-Hardness of Clustering under General Utilities

    Feb 27, 2026Angshul MajumdarClusteringUnsupervised Clustering

    Indraprastha Institute of Information Technology, New Delhi, India

  21. Mamba Meets Scheduling: Learning to Solve Flexible Job Shop Scheduling with Efficient Sequence Modeling

    Feb 25, 2026Zhi Cao, Cong Zhang, Yaoxin Wu +2Flexible Job Shop SchedulingJob Shop Scheduling

    Dalian University of Technology, Dalian, China · Nanyang Technological University, Singapore · Eindhoven University of Technology, Eindhoven, the Netherlands

  22. Code World Models for Parameter Control in Evolutionary Algorithms

    Feb 25, 2026Camilo Chacón Sartori, Guillem Rodríguez CorominasCode World ModelsLarge Language Model-Guided Optimization

    ICN2 – Catalan Institute of Nanoscience and Nanotechnology, Barcelona, Spain · Artificial Intelligence Research Institute (IIIA-CSIC), Barcelona, Spain · Universitat Politècnica de Catalunya (UPC), Barcelona, Spain

  23. Precedence-Constrained Decision Trees and Coverings

    Feb 24, 2026Michał Szyfelbein, Dariusz DereniowskiCombinatorial OptimizationConstrained Optimization

    Gdańsk University of Technology, 80-233 Gdańsk, Poland

  24. Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization

    Feb 23, 2026Ria Stevens, Fangshuo Liao, Barbara Su +3Combinatorial OptimizationQuadratic Programming

    Rice University

  25. OptiRepair: Closed-Loop Diagnosis and Repair of Supply Chain Optimization Models with LLM Agents

    Feb 23, 2026Ruicheng Ao, David Simchi-Levi, Xinshang WangSupply Chain OptimizationLarge Language Model-Guided Optimization

    Massachusetts Institute of Technology. · Alibaba Group.

  26. Partial Optimality in the Preordering Problem

    Feb 19, 2026David Stein, Jannik Irmai, Bjoern AndresCombinatorial Optimization

    Machine Learning for Computer Vision TU Dresden

  27. Heuristic Search as Language-Guided Program Optimization

    Feb 17, 2026Mingxin Yu, Ruixiao Yang, Chuchu FanAutomated Heuristic DesignLarge Language Model-Guided Optimization

    Massachusetts Institute of Technology, Cambridge, MA, USA

  28. On inferring cumulative constraints

    Feb 17, 2026Konstantin SidorovResource-Constrained Project SchedulingConstraint Programming

    Faculty of Electrical Engineering, Mathematics & Computer Science, Delft University of Technology, Delft, The Netherlands

  29. Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks

    Feb 16, 2026Sungwoo KangAlgorithm SelectionCombinatorial Optimization

    Department of Electrical and Computer Engineering Korea University Seoul 02841, Republic of Korea

  30. A Bayesian Approach to Low-Discrepancy Subset Selection

    Feb 16, 2026Nathan KirkCombinatorial Optimization

    1*School of Mathematics and Statistics, University of St Andrews, Mathematical Institute, St Andrews, KY16 9SS, United Kingdom.