超速いMIPソルバを作るゾ(｀ω´)vol.00
MIP(Mixed Integer Problem)―混合整数計画問題のソルバと言えば、去年(2008年)IBM社に買収されたILOG社のCPLEXが有名で、性能も他のソルバを圧倒しています。
で、私が今やっている研究ってのは、簡単に言えば「超ムズー(゜Д゜)な問題をCPLEXより速く解く」ってやつで、結構良い結果が出ているのですが、使用しているアルゴリズム等は私個人の研究ではないので、ここにはあまり書けません。
じゃあ、ここでは何をしていくかというと、しばらくは「CPLEXとかメジャーなソルバが使っているであろうアルゴリズムで1からソルバを作って、どの程度の速度まで出せるのか」という実験を行う予定です。
もちろん、CPLEXっていうのは、世界のスゴモノ達が開発しているわけで、単純な後追いでは到底敵いっこないと思いますので、色々とアイデアは必要でしょうけれども…。まあ、目標は高い方が良いということで。
とりあえず、いきなりCPLEXと比べても仕方ないので、フリーのGLPKあたりを基準にやっていこうかなと思います。
