統計数理研究所

概要: 最適化手法とコンピュータが生まれてから６０年以上の間、常に計算機、最適化アルゴリズム共に進歩を遂げてきました。優れた理論から必ずしも優れたソフトウェアが生まれるとは限らないのですが、今回の講演では1990年代半ばに誕生した半正定値計画問題(SDP)に対する理論（主双対内点法）を題材に取って、この理論がその後どのような経緯を辿って、ソフトウェア化--> 一般公開 --> 高精度化 --> スパコン上で大規模並列計算へと進んで行ったのかについて説明していく予定です。内容はSDPに関する最適化理論、定式化等から応用分野、ソフトウェア化、大規模計算までと多岐に渡ります。

概要: 混合整数計画ソルバの過去20年間の進歩は著しく，アルゴリズム開発とそのソフトウェア実装技術による進歩は，計算機のハードウェアとしての性能向上を上回る．その結果，混合整数計画ソルバは，ハードウェア自体の性能向上との相乗効果により，現実問題に対する最も利用価値のある最適化ソルバとして定着するようになった．商用の混合整数計画ソルバの多くは，PCのマルチコア化に伴い，既に共有メモリ上で動作するスレッド並列処理に対応している．しかし，大規模分散メモリ計算機環境上で効率的に動作し，現在の商用ソルバの性能を超えるようなソルバの実装はほとんどない．
本発表では，様々な高性能ソルバをblack boxとして利用し，その性能を維持しながら，大規模分散メモリ環境上で動作するソルバの開発を可能とするUbiquity Generator Framework(UG)を紹介するとともに， UGを利用して並列化した混合整数計画ソルバによる最新の計算結果について紹介する．また，ZIBで開発されている混合整数計画の拡張である制約整数計画とそれを解くソルバSCIP (Solving Constraint Integer Programs)に関しても紹介したい．