- 様々な時間尺度やリスクレベルで研究を促進する環境の構築
- 基礎研究と応用研究の両方を通じてコンピュータサイエンスの進歩を推進
- 数十億人が毎日使用する技術に影響を与える機会を持つ研究チーム
- 広い研究コミュニティとプロジェクトをオープンソース化し、Google製品に適用
- アイデアを共有し、コンピュータサイエンスの分野を進めるために作品を公開
- 協力的なエコシステムの構築を目指し、製品、ツール、データセットを誰にでも利用可能に
- 広範囲のプログラミングを通じて次世代の研究者を支援
- 大学教員との意義ある協力を通じてアカデミック研究コミュニティに参加
- イベントを通じて広い研究コミュニティとのつながりを強化し、業務のあらゆる側面で進展を生み出す
今回の記事は、Google Researchの研究者であるHaihao Lu氏とDavid Applegate氏が共同で開発したPDLPという名の賞を受賞した製品について紹介しています。PDLPは大規模な線形計画問題のための新しいファーストオーダーメソッドベースのソルバーであり、従来のLPソルバーに比べてメモリ使用量を削減し、現代の計算技術に適したスケーラブルな代替手段を提供しています。PDLPはGoogleのOR-Toolsでオープンソース化されており、2024年7月の数学プログラミング国際シンポジウムでBeale-Orchard-Hays賞を受賞しました。
PDLPは、従来のLP問題の解決における信頼性を高めるために、再開されたPDHGという修正されたアプローチを開発しました。この手法は、PDHGのスパイラルフェーズの終了時に計算された平均値から再起動することで、収束へのパスを効果的に短縮します。この再起動技術により、PDHGの収束振る舞いを理論的にも実践的にも大幅に加速させることが示されています。
PDLPは、OR-Toolsの一環としてオープンソース化されており、Python、C ++、Java、C＃のインターフェースを備えたソルバーであり、効率的に線形計画問題を解決するソフトウェアパッケージとして設計されています。
元記事: https://research.google/blog/scaling-up-linear-programming-with-pdlp/