SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2305.17010 · NeurIPS · 2023

Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets

Yoshua Bengio, Dinghuai Zhang, Aaron Courville, Ling Pan, Nikolay Malkin, Mila Dai

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

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.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2305.17010")
get_code_for_paper("2305.17010")
have("2305.17010")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2305.17010.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2305.17010.svg)](https://syntology.ai/paper/2305.17010)

Connect an agent — have() is free.