組合せ最適化のためのグラフニューラルソルバとLLMの整合

要旨: 近年の研究により、大規模言語モデル（LLM）が、自然言語によってタスクやインスタンスを表現することで、組合せ最適化問題（COP）を解くのに有効であることが示されています。しかし、純粋に言語ベースのアプローチでは、多くのCOPに内在する複雑な関係構造を正確に捉えることが難しく、その結果として、中規模またはそれ以上のインスタンスに対処する能力が十分でない場合があります。これらの制約に対処するために、我々はAlignOPTという新しいアプローチを提案します。AlignOPTは、LLMをグラフニューラルソルバと整合させることで、より汎化可能なニューラルCOPヒューリスティックを学習します。具体的には、AlignOPTは、LLMの意味理解能力を活用してCOPとそのインスタンスのテキスト記述を符号化すると同時に、グラフニューラルソルバを用いて、COPインスタンスの基底となるグラフ構造を明示的にモデル化します。このアプローチにより、言語的なセマンティクスと構造表現の間の堅牢な統合と整合が可能になり、より正確でスケーラブルなCOP解法を実現します。実験結果は、AlignOPTが多様なCOPにおいて最先端の結果を達成することを示しており、意味表現と構造表現を整合させる上での有効性を裏付けています。特に、AlignOPTは強い汎化能力を示し、これまで見たことのないCOPインスタンスへと効果的に拡張できることを示します。