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

Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
Apr 23, 2026Eleanor Wiesler, Trace BaxleyImage Segmentation Graph Neural Networks
1Harvard Department of Mathematics. · 2Harvard Department of Computer Science.
Integrated packing, placement, scheduling, and routing of personalized production: a pharmaceutical Industry 4.0 use-case with a planar transport system
Apr 22, 2026Viktor Emil Korladinov, Antonin Novak, Zdeněk Hanzálek +2Combinatorial Optimization
Faculty of Electrical Engineering, Czech Technical University in Prague, Karlovo Náměstí 13, 120 00, Prague 2, CZ · Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslávských partyzánů 1580/3, 160 00, Prague 6, CZ · Department of Chemical Engineering, University of Chemistry and Technology, Technická 3, 166 28, Prague, CZ
Machine Learning-based Two-Stage Graph Sparsification for the Travelling Salesman Problem
Apr 22, 2026Bo-Cheng Lin, Yi Mei, Mengjie ZhangTraveling Salesperson Problem Graph Sparsification
Centre for Data Science and Artificial Intelligence, and the School of Engineering and Computer Science, Victoria University of Wellington, Wellington, 6140, New Zealand
Learning to Solve the Quadratic Assignment Problem with Warm-Started MCMC Finetuning
Apr 22, 2026Yicheng Pan, Ruisong Zhou, Haijun Zou +2Markov Chain Monte Carlo Combinatorial Optimization
School of Mathematical Science, Peking University, Beijing 100871, China · State Key Laboratory of Mathematical Sciences, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China · Beijing International Center for Mathematical Research, Peking University, Beijing 100871, China
On Scalability of Multi-Objective Evolutionary Algorithms on Combinatorial Optimisation Problems
Apr 20, 2026Menghao Tang, Zimin Liang, Miqing LiEvolutionary Optimization Multi-Objective Evolutionary Optimization
University of Birmingham Birmingham, United Kingdom
From Necklaces to Coalitions: Fair and Self-Interested Distribution of Coalition Value Calculations
Apr 18, 2026Terry R. Payne, Luke RileyCooperative Game Theory Multi-Agent Coordination
School of Computer Science and Informatics, University of Liverpool, Liverpool, UK. · Quant, London, UK.
Stein Variational Black-Box Combinatorial Optimization
Apr 17, 2026Thomas Landais, Olivier Goudet, Adrien Goëffon +2Stochastic Optimization Black-Box Optimization
LERIA, Université d’Angers, 2 Boulevard Lavoisier, Angers 49045, France
On the Use of Iterative Problem Solving for the Traveling Salesperson Problem with Changing Time Window Constraints
Apr 16, 2026Hy Nguyen, Thanh Nguyen Pham, Helen Yuliana Angmalisang +2Traveling Salesperson Problem Metaheuristic Optimization
Optimisation and Logistics School of Computer Science and Information Technology Adelaide University Adelaide, Australia
When does learning pay off? A study on DRL-based dynamic algorithm configuration for carbon-aware scheduling
Apr 2, 2026Andrea Mencaroni, Robbert Reijnen, Yingqian Zhang +1RL Control Learning to Optimize
Department of Industrial Systems Engineering and Product Design, Ghent University, Ghent, Belgium · Industrial Systems Engineering (ISyE), Flanders Make, Kortrijk, Belgium · Eindhoven Artificial Intelligence Systems Institute, Eindhoven University of Technology, The Netherlands +1
Online Learning for Dynamic Constellation Topologies
Mar 26, 2026João Norberto, Ricardo Ferreira, Cláudia SoaresCombinatorial Optimization Wireless Communications
NOVA School of Science and Technology, Caparica, Portugal
Agentic Service Markets Across the Computing Continuum: A Polymatroidal Architecture
Mar 5, 2026Lauri Lovén, Alaa Saleh, Reza Farahani +5Mechanism Design Combinatorial Optimization
Future Computing Group, University of Oulu, Finland · Distributed Systems Group, TU Wien, Vienna, Austria · Department of Mechatronics, University of Prishtina, Kosova +4
Universal NP-Hardness of Clustering under General Utilities
Feb 27, 2026Angshul MajumdarClustering Unsupervised Clustering
Indraprastha Institute of Information Technology, New Delhi, India
Precedence-Constrained Decision Trees and Coverings
Feb 24, 2026Michał Szyfelbein, Dariusz DereniowskiCombinatorial Optimization Constrained Optimization
Gdańsk University of Technology, 80-233 Gdańsk, Poland
Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks
Feb 16, 2026Sungwoo KangAlgorithm Selection Combinatorial Optimization
Department of Electrical and Computer Engineering Korea University Seoul 02841, Republic of Korea
Learning to Approximate Uniform Facility Location via Graph Neural Networks
Feb 13, 2026Chendi Qian, Christopher Morris, Stefanie Jegelka +1Graph Neural Networks Combinatorial Optimization
RWTH Aachen University, Germany · Technical University of Munich, Germany · Massachusetts Institute of Technology, USA +1
ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search
Feb 10, 2026Alexey Kravatskiy, Valentin Khrulkov, Ivan OseledetsAutomated Algorithm Discovery Evolutionary Optimization
1MIRIAI, Russia · 2FusionBrain Lab, Russia · 3AXXX, Russia +1
Fair and Efficient Investment in Public Transportation
Feb 3, 2026Martin Bullinger, Edith Elkind, Kassian KöckAlgorithmic Fairness Combinatorial 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
Towards Solving the Gilbert-Pollak Conjecture via Large Language Models
Jan 29, 2026Yisi Ke, Tianyu Huang, Yankai Shu +3Combinatorial Optimization Large 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
Graph Neural Networks are Heuristics
Jan 19, 2026Yimeng Min, Carla P. GomesTraveling Salesperson Problem Graph Neural Networks
Department of Computer Science Cornell University Ithaca, NY, USA
Enabling Population-Based Architectures for Neural Combinatorial Optimization
Jan 13, 2026Andoni Irazusta Garmendia, Josu Ceberio, Alexander MendiburuMetaheuristic Optimization Combinatorial Optimization
University of the Basque Country (EHU), Department of Computer Science and Artificial Intelligence, San Sebastian, Spain.
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 +1Combinatorial Optimization Constraint Programming
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
A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm
Jan 9, 2026Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum +1Clustering Combinatorial 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
Neural Minimum Weight Perfect Matching for Quantum Error Codes
Jan 1, 2026Yotam Peled, David Zenati, Eliya NachmaniNeural Decoding Quantum Error Correction
School of Electrical and Computer Engineering (ECE), Ben-Gurion University, Beer Sheva, Israel.
Leveraging Discrete Function Decomposability for Scientific Design
Nov 4, 2025James C. Bowden, Sergey Levine, Jennifer ListgartenAI-Assisted Scientific Research Combinatorial 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.
Column Generation with Domain-Independent Dynamic Programming
Oct 16, 2025Ryo Kuroiwa, Edward LamDynamic Programming Combinatorial Optimization
Department of Data Science and Artificial Intelligence, Monash University, Melbourne, Australia · The Graduate University for Advanced Studies, SOKENDAI, Kanagawa, Japan
Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity
Oct 4, 2025Lutz Oettershagen, Othon MichailFair Resource Allocation Combinatorial Optimization
University of Liverpool
Graph Optimization Foundation Model: Tokenizing Graph via A Language-Model Paradigm
Sep 29, 2025Yunhao Liang, Pujun Zhang, Yuan Qu +3Graph SSL Combinatorial 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
Self-Improving Neural Pruning: A Graph Neural Network Framework for Scalable Mixed Bundle Pricing
Sep 26, 2025Liangyu Ding, Chenghan Wu, Guokai Li +1Graph Neural Networks Combinatorial Optimization
School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, China
Recurrent State Encoders for Efficient Neural Combinatorial Optimization
Sep 5, 2025Tim Dernedde, Daniela Thyssens, Lars Schmidt-ThiemeRecurrent Neural Networks Combinatorial Optimization
Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim
Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture
Aug 11, 2025Xiang Li, Shanshan Wang, Chenglong XiaoAlgorithm Selection Combinatorial Optimization
College of Mathematics and Computer, Shantou University, Shantou, China

Apr 23, 2026, cs.LGJ/K move · Enter open · S save

Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability

Eleanor Wiesler, Trace Baxley

1Harvard Department of Mathematics. · 2Harvard Department of Computer Science.

Image Segmentation Graph Neural Networks Combinatorial Optimization Learning-Augmented Algorithms

Open paper AskPDF arXiv

We propose a learning-augmented framework for accelerating max-flow computation and image segmentation by integrating Graph Neural Networks (GNNs) with the Ford-Fulkerson algorithm. Rather than predicting initial flows, our method learns edge importance probabilities to guide augmenting path selection. We introduce a Message Passing GNN (MPGNN) that jointly learns node and edge embeddings through coupled updates, capturing both global structure and local flow dynamics such as residual capacity and bottlenecks. Given an input image, we propose a method to construct a grid-based flow network with source and sink nodes, extract features, and perform a single GNN inference to assign edge probabilities reflecting their likelihood of belonging to high-capacity cuts. These probabilities are stored in a priority queue and used to guide a modified Ford-Fulkerson procedure, prioritizing augmenting paths via an Edmonds-Karp-style search with bottleneck-aware tie-breaking. This avoids repeated inference over residual graphs while leveraging learned structure throughout optimization. We further introduce a bidirectional path construction strategy centered on high-probability edges and provide a theoretical framework relating prediction quality to efficiency via a weighted permutation distance metric. Our method preserves max-flow/min-cut optimality while reducing the number of augmentations in practice. We also outline a hybrid extension combining flow warm-starting with edge-priority prediction, establishing a foundation for learning-guided combinatorial optimization in image segmentation.

Momentum

Related topics

Latest papers 277