組合せ最適化のための実現不可能性（不可能性）を考慮した大規模言語モデル

概要: 大規模言語モデル（LLM）は、NP困難な組合せ最適化問題に対してますます検討されているが、既存のほとんどの手法は実行可能なインスタンスの解生成を重視しており、不可能性（infeasibility）の検出を明示的に扱っていない。そこで本研究では、証明可能なデータセット構築、教師ありファインチューニング、そしてLLM支援による下流探索を組み合わせた、不可能性を考慮した枠組みを提案する。マイナー埋め込み（minor-embedding）問題に対しては、新しい数学的計画法の定式化を導入するとともに、証明可能なゼロ相不可能性スクリーニング（provable zero-phase infeasibility screening）を実現する。これにより、学習用インスタンスを大規模に構築でき、構造化された証明（certificate）を伴う実行可能（feasible）としてラベル付けされたもの、または証明可能に不可能（certifiably infeasible）としてラベル付けされたものの両方を扱える。厳密な最適化パイプラインによって生成された学習データを用いて、8B（80億）パラメータのLLMを、解生成と不可能性検出を同時に行うようにファインチューニングできることを示す。さらに、下流の局所探索においてLLMの出力をウォームスタートとして利用することで、LLMの出力が不完全であっても最適化を加速する実用的な方法を提供する。実験の結果、ファインチューニングしたモデルはGPT-5.2に比べて全体の精度を最大30\%向上させる一方、LLMに導かれたウォームスタートは、下流の局所探索においてゼロから開始する場合と比べて最大2\timesの速度向上をもたらすことが分かった。