GPU（Graphics Processing Unit）は、機械学習における学習および推論処理の高速化において顕著な成果を上げてきた。一方で、一般的かつ厳密な組合せ最適化の分野では、同様の性能向上はまだ十分に達成されていない。これまでのGPU向け組合せ最適化手法は、主にメタヒューリスティック手法や特定の問題に限定された厳密解法に集中してきた。近年では、行列演算を中心とする原始–双対ハイブリッド勾配法の登場により、線形計画問題および混合整数線形計画においてGPU活用の大きな進展が見られている。
これに対し、**制約プログラミング（Constraint Programming, CP）**は、非線形制約を扱い、制約伝播とバックトラック探索によって厳密解を提供する一般的な手法であるが、GPUアーキテクチャ上での発展は限定的であった。従来研究では、制約言語の表現力を制限する、計算の一部のみをGPUにオフロードする、あるいは特定の制約に限定するなどのアプローチが取られてきたが、汎用的なGPUベースのCPソルバは実現されていなかった。
本研究では、並行制約プログラミングの進展を踏まえ、GPU向けに設計された汎用かつ厳密な離散制約プログラミングソルバ Turbo を提案する。Turboは、整数区間境界伝播とバックトラック探索をGPU上で完全に実装し、制約ネットワークを三項制約ネットワーク（TCN）に分解することで、parallel CCPモデルに基づく効率的な並列伝播を実現する。この表現により、GPUに適したメモリアクセスと高い並列効率が可能となる。
GPUのハードウェア制約により、TurboはCPU向けの最先端CPソルバと比較して簡素な構成を採用しており、グローバル制約、学習機構、再起動戦略、ドメイン整合性などの高度な最適化は実装していない。それにもかかわらず、MiniZinc Challenge 2024における実験結果では、Turboが多くの問題において既存の逐次ソルバと同等、あるいはそれ以上の性能を示すことが確認された。本論文では、提案手法の有効性と拡張性について包括的な実験評価を行う。
TY - BOOKAU - Talbot, PierrePY - 2026/01/22SP - T1 - A GPU-based Constraint Programming SolverVL - ER -
Link to full paper:
https://www.researchgate.net/publication/399606771_A_GPU-based_Constraint_Programming_Solver
