This study proposes a trainable sampling-based solver for combinatorial
optimization problems (COPs) using a deep-learning technique called deep
unfolding. The proposed solver is based on the Ohzeki method that combines
Markov-chain Monte-Carlo (MCMC) and gradient descent, and its step sizes are
trained by minimizing a loss function. In the training process, we propose a
sampling-based gradient estimation that substitutes auto-differentiation with a
variance estimation, thereby circumventing the failure of back propagation due
to the non-differentiability of MCMC. The numerical results for a few COPs
demonstrated that the proposed solver significantly accelerated the convergence
speed compared with the original Ohzeki method.

该研究提出了一种可训练的基于采样的求解器用于组合优化问题，使用一种称为深展开的深度学习技术。该求解器基于 Ohzeki 方法，结合了马尔可夫链蒙特卡洛（MCMC）和梯度下降，并通过最小化损失函数来训练其步长。在训练过程中，我们提出了一种基于采样的梯度估计，用方差估计代替自动微分，从而避免了由于 MCMC 的不可微分性导致的反向传播失败。对于几个组合优化问题的数值结果表明，与原始的 Ohzeki 方法相比，所提出的求解器显著加速了收敛速度。