  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.
