« 読了：Atkinson & Bailey (2001) Biometrikaで振り返る実験計画の100年 | メイン | 読了：Kass & Raftery (1995) ベイズ・ファクターとはなにか »
2016年8月10日 (水)
Ozaltın, O.Y., Hunsaker, B., Schaefer, A.J. (2011) Predicting the Solution Time of Branch-and-Bound Algorithms for Mixed-Integer Programs. INFORMS Journal on Computing. 23(3), 392-403.
B&Bアルゴリズムで整数計画問題を解いているさなかに、その問題があとどのくらいの時間で解けるかを予測する手法を提案する論文。
たまたま見つけてディスプレイ上で眺めた。なにこれ、俺って検索の天才なの?! ついに救いの神を見つけちゃったわけ?! と５秒くらい興奮したけど、ま、神はそんなに甘くない。
いわく。
終了時間の予測にはMIP gapがつかわれることが多いが、たいていずっと一定で、解が見つかる前に突然下がるので、いまいち使いにくい。未処理ノード数を監視することもあるけど、減っているからといってもうすぐ終わるとは限らないし、増え続けることだってあるので困る[←そうそう！]。そこで新指標SSGを提案しましょう。
先行研究概観。
branch-and-boundアルゴリズムのノード数推定にはオフライン法(探索打ち切り後に用いる)とオンライン法がある。前者は...[略]。後者としては、未探索ブランチのノード数はこれまでに探索したブランチのノード数と似ているだろうと仮定する奴とか...[略]...がある。
我々の提案はこれらとはちがって、まずは探索の進行を示す連続的指標をつくることを考える。
提案手法。
全体のMIP gapじゃなくて、B&Bツリーをサブツリーに分割し各サブツリーの最適性gapを測る。サブツリーへの分割がガンガン変わるというところがポイント。で、合計してうまいことスケーリングし、単調に増えていく指標にする。
この指標の時系列をつかって終了時間を予測する。カルマン・フィルタとかだと大変なので、二重指数平滑化で予測する由。
途中で「あ、これは... 誰かにソフトを作ってもらわないとだめだ...」と気づき、急速に関心がなくなってしまった。パラパラ捲っただけだけど読了にしておく。著者はBAKというソフトを配っていて、提案手法はそこで実装してある由。 整数計画ソルバーとして、論文の時点ではSYMPHONY、GLPK、CBC、に対応していたらしい。 いまでも配っているみたいだが、開発は止まっちゃっている模様。
論文：データ解析(2015-) - 読了：Ozaltın, Hunsaker, Shaefer (2011) 整数計画問題があとどのくらいで解けるかを予測する新手法