aiqbench analysis
This research applies GFlowNets, a generative modeling technique, to tackle NP-hard combinatorial optimization problems by efficiently sampling high-quality solutions within constrained solution spaces. By designing specific Markov decision processes and improving credit assignment for long-range dependencies, the study demonstrates that these policies can outperform traditional methods on both synthetic and realistic datasets. The work advances the intersection of generative AI and discrete mathematics, offering a scalable approach to solving complex optimization tasks where exact algorithms are computationally infeasible.
Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets
arXiv:2305.17010v4 Announce Type: replace-cross Abstract: Combinatorial optimization (CO) problems are often NP-hard and thus out of reach for exact algorithms, making them a tempting domain to apply machine learning methods. The highly structured constraints in these problems can hinder either optimization or sampling directly in the solution space. On the other hand, GFlowNets have recently emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially and have the potential to amortize such solution-searching processes in CO, as well as generate diverse solution candidates. In this paper, we design Markov decision processes (MDPs) for different combinatorial problems and propose to train conditional GFlowNets to sample from the solution space. Efficient training techniques are also developed to benefit long-range credit assignment. Through extensive experiments on a variety of different CO tasks with synthetic and realistic data, we demonstrate that GFlowNet policies can efficiently find high-quality solutions. Our implementation is open-sourced at https://github.com/zdhNarsil/GFlowNet-CombOpt.
Abstract:Combinatorial optimization (CO) problems are often NP-hard and thus out of reach for exact algorithms, making them a tempting domain to apply machine learning methods. The highly structured constraints in these problems can hinder either optimization or sampling directly in the solution space. On the other hand, GFlowNets have recently emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially and have the potential to amortize such solution-searching processes in CO, as well as generate diverse solution candidates. In this paper, we design Markov decision processes (MDPs) for different combinatorial problems and propose to train conditional GFlowNets to sample from the solution space. Efficient training techniques are also developed to benefit long-range credit assignment. Through extensive experiments on a variety of different CO tasks with synthetic and realistic data, we demonstrate that GFlowNet policies can efficiently find high-quality solutions. Our implementation is open-sourced at this https URL.
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM); Machine Learning (stat.ML)
arXiv:2305.17010 [cs.LG]
(or arXiv:2305.17010v4 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2305.17010 Focus to learn more arXiv-issued DOI via DataCite
https://doi.org/10.52202/075280-0522 Focus to learn more DOI(s) linking to related resources
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 261 words
Related coverage
Navigating uncertainty in Amazon's middle-mile network
Amazon Science · May 6, 2026
Donald Knuth, The Man Who Made Algorithms Count
Quantum Zeitgeist · Aug 7, 2026
Notes on Algorithms
LessWrong · Jun 10, 2026
Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow
arXiv · Sep 11, 2026