type個人的な勉強の記録です。データ分析、可視化などをメイントピックとしています。数値最適化は機械学習や数値モデリングの基礎も基礎ですが、単に役に立ちます。Pythonという観点を度外視すれば、いろいろな手段がありますが、基本的には共通するフローがあります。現象から最適化したい目的関数を決定する目的関数に付随する制約条件を立式化するデータを用意し、モデリング言語を記述するモデルをソルバーへ投入し、解を得るこういった作業をするための環境は商用でも色々と売られていまして、例えばAIMMS社とか、GAMS社、AMPL社といった会社は最適化の開発環境や言語を作って販売しています。非商用でも、こういう団体は存在し、COIN-ORではライブラリやソルバーを開発して公開しています。商用のソフトウェアに比べれば少々パフォーマンスに劣りますが無料で使えるということを考えれば文句も出ません。AMPL言語の書き方を見てみると...ちょっとめんどくさそうです。新しく言語を覚えるのは大体の場合面倒くさいので、実務でちゃちゃっと最適化したい場合には向きません。Pythonで済ませられたらうれしいです。Pythonで最適化?Pythonで最適化する方法も色々あります。Scipy.optimize一番最初に思いつく方法だと思います。アルゴリズムも色々ありますし、導入も簡単です。簡単な最小化とか線形計画法(LP)に特化しています。痒いところに手が伸びるものが欲しいのです。PuLP日本語で調べるとこのライブラリについての記事が一番多く出てきます。PuLPは先程のCOIN-ORによって開発が進められているライブラリです。使いやすいですし、Sphinxでのドキュメントも有るのが個人的にはありがたいところです。使えるソルバーが少ない最近開発が停滞気味といった2点が気になりました。リポジトリに書いてあるように、PuLPはLP/MILP用ライブラリです。CBCで、他に使えるのもCPLEX、GLPKなどLPソルバーです。非線形問題は解けません。一つ、PuLPは2017年の中頃からレポジトリが更新されていません。ドキュメントも更新がされておらず、実際に使う上で良く分からないことも多いです。いうか英語ドキュメントすらなさすぎて、日本語記事のほうが詳しいかも...。最適化におけるPythonなどがありました。他にもQiitaやBlog上に、沢山の詳しい記事があります。CVXPYこちらの記事がとても詳しいです*1。ウェブページにも載っていますが、メインで開発しているのは米サンディア国立研究所のようです。昔はCooprという名前でした。Pythonのオブジェクト指向な書き方をとても重視したライブラリです。僕はPuLPの次にこれを使ってみたら、結構似ていると感じたので、移行も簡単でしょう。PyomoやPuLPは2008年ぐらいに沢山開発されたPythonライブラリで、今も生き残っているものたちです。書きやすさは担保されていると思います(参考↓)。使えるソルバーが多いコミュニティがそこそこ活発という点です。Library)に対応しています。PuLPで使えていたCBC、GLPK、CPLEXなども利用することが出来ますし、その他についてはAMPLのページを見たほうが早いですね。PuLPでは使えなかった非線形ソルバーで有名なSCIPが使えますし、Open-OR主導で開発されているBonminやCouenne、IPOPTなども利用できます。一つ、PyomoはPuLPと同じぐらいドキュメントは弱いのですが*2、コミュニティは活発です。リポジトリは頻繁にコミットがありますし、チュートリアル用のリポジトリやモデル例もあります。Groupが活発で、質問にすぐに答えてくれた点です。いうわけで、今回はPyomoを使って最適化を試してみます。先行記事にはpyomoとglpkを使ってナップサック問題を解く数理最適化とPythonがありました。他に日本語の記事があまり出てこないので、残しておきます。pyomoで終わりですが、これだとソルバーが全然入っていません。ソルバーはコマンドラインから実行できるようにする必要があります。自分はOSXの端末に以下のソルバーを入れました。皆様はお好きにどうぞ。glpkで終了!CPLEXアカデミックライセンスを使いました。IBMのインストーラーで導入後、/Applications/CPLEX_Studio128/cplex/bin/x86-64_osxへPATHを通せばOKです。IPOPTこちらを参照しました。古い記事ですが、この通りで動きます*3。SCIPそのまま導入しただけでは利用することが出来ません。Groupではnlオプションを付ければいいと書いてありましたが、僕は無理でした。SCIPをAMPLフォーマットで読み書きするようにコンパイルする必要があります。これはこちらをそのまま参考にしました。Bonmin、CouenneOpen-ORのソルバーなので、IPOPTと同様の手順で入ります。IPOPTの時にOPENBLASやLAPACKを入れていれば、飛ばしてOKです。Dockerを利用する(2019-03-29追記)Dockerを使ったコンテナを作りました。以下のページに詳細は書きましたので、面倒くさい方はこちらをどうぞ。ajhjhaf.hatenablog.com非線形最適化問題を解くどうせなので、非線形問題を解いてみましょう。例として、放送大学の資料にあった問題を解きます。仕上がりを最大化するには、各工程にどのように割り振ればいいか仕上がりの程度にlogが入っているので非線形最適化問題になります。INLP)というパラダイムで解かれる問題ですね。MINLP)の一部として取り組むことが多いです。ソルバーもMINLP用のものを探したほうがいいです。Pythonでの解法です。これはJupyter環境でやっています。Pyomoの例題ではコマンドラインから動かしていますが、こうすればJupyterでも動きます。optの部分でsolverを指定して下さい。PyomoはList型のIndexingを自動でやってくれないので、Dict型に変換しています。変数についてはVarで宣言し、2つめの位置変数へデータ型を入れます。今回は日数なので、非負整数です。制約条件を書いていきます。最適化条件と順番が前後しても大丈夫です。Pyomoの変な特性ですが、グローバル変数とローカル変数がごっちゃになっても受け付けてしまいます。良い書き方がありそうですが...現状知りません。制約条件時に、Iの各要素iで成立...としたい場合は、第一位置変数へ入力すれば受け付けてくれます。最適化条件を書きます。最小化(minimize)を指定します。opt.solveをする時に、tee=Trueとすればソルバーのメッセージが表示されます。デバッグ時に便利です。モデルの結果を表示します。以下出力です(デバッグ部分は除きました)。None4つのタスクに対して、15:20:50:15と割り振ることでパフォーマンスが最大化され、パフォーマンス和は19.26です。終わる仕事の4番目ですが、プロトタイプが出来てからの伸びしろが良いのでこうなるわけです。おわり以上Pythonでの数値最適化でした。セミナー資料(伊藤聡先生)*1:解説が薄いのは、このライブラリ(記事)を見つけたのが記事を書き終わってからというだけであり、他意はありません*2:APIが纏められていない点が使いづらいです。»プロフィールid:ajhjhaf検索リンクはてなブログブログをはじめる週刊はてなブログはてなブログPro最新記事StanのMAP推定の収束判定についてのコードを読むDockerでPyomo+Jupyterlabの実行環境をパッケージ化こうしてGoogleに落ちたScipyでBrunner-Munzel検定Stanで非閉型な逆関数を含む分布のモデリング月別アーカイブはてなブログをはじめよう!ajhjhafさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。