Abstract
本論文では、整数線形計画法（ILP）として定式化された組合せスケジューリング問題を解くための、ハイブリッドCPU-GPUフレームワークを提案する。計算システムにおける多くの最適化タスクの基盤となるのがスケジューリングである一方、これらの問題を大規模に最適解として解くことは、NP困難であることに起因して、長年の課題として残されてきた。本論文では、差分可能な最適化と従来型のILPソルバを組み合わせる新しいアプローチを提示する。具体的には、差分可能なpresolving（事前縮約）を用いて、質の高い部分解を迅速に生成し、それを商用ILPソルバ（CPLEX、Gurobi）および台頭するオープンソースソルバHiGHSのウォームスタートとして利用する。この手法は、最先端のスタンドアロンソルバと比較して、初期段階での枝刈りを大幅に改善することを可能にする。産業規模のベンチマークにわたる実験結果は、ベースラインに対して最大10\timesの性能向上を示し、最適性ギャップを<0.1\%まで縮小する。本研究は、組合せスケジューリングに対して差分可能な最適化を用いて厳密なILPソルバを初期化することを最初に実証するものであり、より広い領域において機械学習の基盤インフラと古典的な厳密最適化手法を統合する新たな機会を切り拓くものである。
