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. Learning to Approximate Uniform Facility Location via Graph Neural Networks

    Feb 13, 2026Chendi Qian, Christopher Morris, Stefanie Jegelka +1Graph Neural NetworksCombinatorial Optimization

    RWTH Aachen University, Germany · Technical University of Munich, Germany · Massachusetts Institute of Technology, USA +1

  2. ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

    Feb 10, 2026Alexey Kravatskiy, Valentin Khrulkov, Ivan OseledetsLarge Language Model-Guided Scientific DiscoveryEvolutionary Optimization

    1MIRIAI, Russia · 2FusionBrain Lab, Russia · 3AXXX, Russia +1

  3. Graph-Theoretic Formulation of Hamiltonian and Ground-State Sign Structures in Heisenberg Antiferromagnets

    Feb 4, 2026Mahmud Ashraf Shamim, Md Moshiur Rahman Raj, Mohamed Hibat-Allah +3Quantum Many-Body PhysicsCombinatorial Optimization

    Department of Physics and Astronomy, University of Alabama, Tuscaloosa, 35487, Alabama, USA. · Department of Physics, University of Rajshahi, P.O. Box 6205, Rajshahi, Bangladesh. · Department of Applied Mathematics, University of Waterloo, Ontario Canada N2L 3G1 +1

  4. Fair and Efficient Investment in Public Transportation

    Feb 3, 2026Martin Bullinger, Edith Elkind, Kassian KöckAlgorithmic FairnessCombinatorial Optimization

    School of Engineering Mathematics and Technology, University of Bristol, Bristol, UK · School of Engineering, Northwestern University, Evanston, USA · School of Computation, Information and Technology, Technical University of Munich, Munich, Germany

  5. Towards Solving the Gilbert-Pollak Conjecture via Large Language Models

    Jan 29, 2026Yisi Ke, Tianyu Huang, Yankai Shu +3Combinatorial OptimizationLarge Language Model-Guided Scientific Discovery

    School of EECS, Peking University · School of Mathematical Sciences, Peking University · State Key Laboratory of General Artificial Intelligence, Peking University, Beijing, China +2

  6. Graph Neural Networks are Heuristics

    Jan 19, 2026Yimeng Min, Carla P. GomesTraveling Salesperson ProblemGraph Neural Networks

    Department of Computer Science Cornell University Ithaca, NY, USA

  7. Enabling Population-Based Architectures for Neural Combinatorial Optimization

    Jan 13, 2026Andoni Irazusta Garmendia, Josu Ceberio, Alexander MendiburuMetaheuristic OptimizationCombinatorial Optimization

    University of the Basque Country (EHU), Department of Computer Science and Artificial Intelligence, San Sebastian, Spain.

  8. Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach

    Jan 10, 2026Corentin Juvigny, Antonín Novák, Jan Mandík +1Resource-Constrained Project SchedulingCombinatorial Optimization

    Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugosl´avsk´ych partyz´an˚u 1580/3, 160 00, Prague 6, Czech Republic

  9. A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm

    Jan 9, 2026Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum +1ClusteringCombinatorial Optimization

    Department of Business Administration, University of Bern, Engehaldenstr. 4, 3012 Bern, Switzerland · Riverside County Office of Education, Riverside, CA 92501, USA · Industrial Engineering and Operations Research Department, University of California, Berkeley, CA 94720, USA

  10. Neural Minimum Weight Perfect Matching for Quantum Error Codes

    Jan 1, 2026Yotam Peled, David Zenati, Eliya NachmaniNeural DecodingQuantum Error Correction

    School of Electrical and Computer Engineering (ECE), Ben-Gurion University, Beer Sheva, Israel.

  11. Leveraging Discrete Function Decomposability for Scientific Design

    Nov 4, 2025James C. Bowden, Sergey Levine, Jennifer ListgartenAI-Assisted Scientific ResearchCombinatorial Optimization

    Department of Electrical Engineering and Computer Sciences, UC Berkeley. · Center for Computational Biology, UC Berkeley. · UC Berkeley–UCSF Graduate Program in Bioengineering, UC San Francisco.

  12. Arithmetic Circuits and Neural Networks for Regular Matroids

    Nov 4, 2025Christoph Hertrich, Stefan Kober, Georg LohoCombinatorial Optimization

    University of Technology Nuremberg, Germany · Universit´e Libre de Bruxelles, Belgium · Freie Universität Berlin, Germany +1

  13. Column Generation with Domain-Independent Dynamic Programming

    Oct 16, 2025Ryo Kuroiwa, Edward LamDynamic ProgrammingCombinatorial Optimization

    Department of Data Science and Artificial Intelligence, Monash University, Melbourne, Australia · The Graduate University for Advanced Studies, SOKENDAI, Kanagawa, Japan

  14. Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity

    Oct 4, 2025Lutz Oettershagen, Othon MichailFair Resource AllocationCombinatorial Optimization

    University of Liverpool

  15. Graph Optimization Foundation Model: Tokenizing Graph via A Language-Model Paradigm

    Sep 29, 2025Yunhao Liang, Pujun Zhang, Yuan Qu +3Graph SSLCombinatorial Optimization

    Faculty of Engineering, The University of Hong Kong, Hong Kong SAR, China · Costello College of Business, George Mason University, VA, USA · Faculty of Business and Economics, The University of Hong Kong, Hong Kong, China +1

  16. Self-Improving Neural Pruning: A Graph Neural Network Framework for Scalable Mixed Bundle Pricing

    Sep 26, 2025Liangyu Ding, Chenghan Wu, Guokai Li +1Graph Neural NetworksCombinatorial Optimization

    School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, China

  17. Recurrent State Encoders for Efficient Neural Combinatorial Optimization

    Sep 5, 2025Tim Dernedde, Daniela Thyssens, Lars Schmidt-ThiemeRecurrent Neural NetworksCombinatorial Optimization

    Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim

  18. Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture

    Aug 11, 2025Xiang Li, Shanshan Wang, Chenglong XiaoAlgorithm SelectionCombinatorial Optimization

    College of Mathematics and Computer, Shantou University, Shantou, China

  19. Flow-Through Tensors: A Unified Computational Graph Architecture for Multi-Layer Transportation Network Optimization

    Jun 30, 2025Xuesong Zhou, Taehooie Kim, Mostafa Ameli +3Intelligent Transportation SystemsCombinatorial Optimization

  20. Physics Inspired Neural Networks Enable Efficient Graph Coloring

    Aug 2, 2024Lorenzo Colantonio, Andrea Cacioppo, Federico Scarpati +3Combinatorial OptimizationNeural Combinatorial Optimization

    Department of Physics, Sapienza University of Rome

  21. Probabilistic Approach to Black-Box Binary Optimization with Budget Constraints: Application to Sensor Placement

    Jun 9, 2024Ahmed AttiaBlack-Box OptimizationCombinatorial Optimization

    Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL, USA

  22. GFPack++: Attention-Driven Gradient Fields for Optimizing 2D Irregular Packing

    Jun 9, 2024Tianyang Xue, Lin Lu, Yang Liu +5Combinatorial OptimizationConstrained Optimization

    Shandong University, China · Microsoft Research Asia, China · Peking University, China

  23. Leader Reward for POMO-Based Neural Combinatorial Optimization

    May 22, 2024Chaoyang Wang, Pengzhi Cheng, Jingze Li +1Traveling Salesperson ProblemReward Shaping

    Fudan University

  24. A short review on the maximum clique problem algorithms with classical, AI, and quantum methods

    Mar 13, 2024Raffaele Marino, Lorenzo Buffoni, Bogdan ZavalnijCombinatorial Optimization

    Dipartimento di Fisica e Astronomia Università degli studi di Firenze Via Giovanni Sansone 1, 50019 Sesto Fiorentino, Florence, Italy · HUN-REN Rényi Institute of Mathematics H-1053, Reáltanoda u. 13-15 Budapest, Hungary

  25. Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary

    Feb 2, 2023Alexander Lindermayr, Nicole Megow, Martin RappCombinatorial OptimizationLearning-Augmented Algorithms

    University of Bremen, Faculty of Mathematics and Computer Science, Germany · Faculty for Informatics, Karlsruhe Institute of Technology, Germany

  26. Context-Aware System Synthesis, Task Assignment, and Routing

    Jun 14, 2017Jason Ziglar, Ryan Williams, Alfred WicksCombinatorial OptimizationRobotics