Quadratic Unconstrained Binary Optimization (QUBO) is a generic technique to
model various NP-hard combinatorial optimization problems in the form of binary
variables. The Hamiltonian function is often used to formulate QUBO problems
where it is used as the objective function in the context of optimization. In
this study, we investigate how reinforcement learning-based (RL) paradigms with
the presence of the Hamiltonian function can address combinatorial optimization
problems over graphs in QUBO formulations. We use Graph Neural Network (GNN) as
the message-passing architecture to convey the information among the nodes. We
have centered our discussion on QUBO formulated Max-Cut problem but the
intuitions can be extended to any QUBO supported canonical NP-Hard
combinatorial optimization problems. We mainly investigate three formulations,
Monty-Carlo Tree Search with GNN-based RL (MCTS-GNN), DQN with GNN-based RL,
and a generic GNN with attention-based RL (GRL). Our findings state that in the
RL-based paradigm, the Hamiltonian function-based optimization in QUBO
formulation brings model convergence and can be used as a generic reward
function. We also analyze and present the performance of our RL-based setups
through experimenting over graphs of different densities and compare them with
a simple GNN-based setup in the light of constraint violation, learning
stability and computation cost. As per one of our findings, all the
architectures provide a very comparable performance in sparse graphs as per the
number of constraint violation whreas MCTS-GNN gives the best performance. In
the similar criteria, the performance significantly starts to drop both for GRL
and simple GNN-based setups whereas MCTS-GNN and DQN shines. We also present
the corresponding mathematical formulations and in-depth discussion of the
observed characteristics during experimentations.

利用强化学习与哈密顿函数结合的方法在二次无约束二进制优化（QUBO）问题中处理组合优化问题。使用图神经网络作为节点之间信息传递的消息传递架构，并使用 Monty-Carlo Tree Search with GNN-based RL（MCTS-GNN）、DQN with GNN-based RL 和 GRL 三种结构进行研究。发现 RL 范式中，QUBO 公式中基于哈密顿函数的优化可以带来模型收敛，并可作为通用的奖励函数；并通过对不同密度图上的实验，从违反约束、学习稳定性和计算成本的角度比较了不同结构的性能。

关于在图上的组合优化中的 QUBO 基于哈密顿函数用于 Max Cut (MC) 问题的研究

Understanding the Usage of QUBO-based Hamiltonian Function in  Combinatorial Optimization over Graphs: A Discussion Using Max Cut (MC)  Problem

We propose Symplectic Recurrent Neural Networks (SRNNs) as learning
algorithms that capture the dynamics of physical systems from observed
trajectories. An SRNN models the Hamiltonian function of the system by a neural
network and furthermore leverages symplectic integration, multiple-step
training and initial state optimization to address the challenging numerical
issues associated with Hamiltonian systems. We show that SRNNs succeed reliably
on complex and noisy Hamiltonian systems. We also show how to augment the SRNN
integration scheme in order to handle stiff dynamical systems such as bouncing
billiards.

本文提出了一种名为对称循环神经网络的学习算法，其可以从观察到的轨迹中捕获物理系统的动力学，并通过神经网络模型系统的哈密顿函数，结合较为复杂的多步训练和初始状态优化来解决哈密顿系统所涉及的数值问题，从而成功的处理包括噪声和复杂系统在内的哈密顿系统及其他动力学系统。并提出如何用扩展的 SRNN 集成方案来处理像弹球这样的非常振动力学系统。