仕事で数理計画(数理最適化)を触ることがちょくちょくある。職場では、ライセンス費年間3ケタ万円とかのツール&ソルバを使えるが、自主学習用にはとてもじゃないが用意できないので、Googleのオープンソース数理最適化ツールが使えるか試してみる。環境整備インストール公式ページに環境別のインストール方法が載っている。Python3.7を前提にする。公式ページに注意書きがあるが、64bitアーキテクチャしかサポートしていないらしい。architecture.今どきは大抵問題ないだろうが、大企業とかだと組織運営的に環境移行が遅くて、まだ残っていることもありそうなので注意する。前提で問題なければ、pipとかでインストールするだけ。ortools公式ページでは、--userオプションついているがその辺はお好みで。適当に問題解いてみるまるっきり一緒ではないが、業務でやったスケジュール作成に近いものをやってみる。1つのリソースに対して複数の仕事を時間を守りながら順番に割り付ける問題を想定。一般的には1機械問題というらしい。問題の概要1つのリソースに対して、$N$個の仕事を割り付ける。仕事にはそれぞれ、"作業可能時間"が設定されていて、各仕事は作業の開始~終了を"作業可能時間"内に収めないといけない。リソースにも使用時間の制限があり、仕事の割り当てはリソースの使用可能時間内にしなければならない。$N$個の仕事がすべて割り付けられれば、リソースの使用時間を最短にする必要はない。仕事$n$の作業開始時刻は、その仕事$n$に設定された作業可能時間及び、リソースの使用可能時間の下限時刻以降でなければならない。N\end{eqnarray}$$仕事$n$の作業完了時刻は、その仕事$n$に設定された作業可能時間及び、リソースの使用可能時間の上限時刻以前でなければならない。N\end{eqnarray}$$リソースに対して、同時に複数の仕事を割り当てることはできない。制約を満たしている満足解を得られれば良いので、特に設定しない。Pythonでの実装モジュールのインポートortoolsをインポートする。)なので、公式ページのここを参考にする。pywraplpあとは、今回の例題用にいくつかインポートする。時刻を足し引きするのでdatetime.timedeltaを、順序設定時に仕事の数から組合せを算出するのにitertools.combnationsを使う。pandasは標準ライブラリではないが、仕事毎のパラメータ設定等の視認性と利便性で使っている。管理できればpandasを使わなくてもいい。combinationsソルバのインスタンスを生成これも、公式ページを参考に設定する。)なので、pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMINGであるが、問題によってソルバを切り替える形みたい。適当に4つの仕事を定義する。実務だと仕事の要求に紐づいているのだろうが、今回は例題なので自分で適当に決めた。upper)を定義する。これも適当に自分で決めた。実務だと始業~終業の時間とかになるはず。時刻を基準値からの秒数で扱う必要があるので、時刻系をすべてfloatに変換する。何らかでtimedeltaに変換してtotal_seconds()メソッドで秒数を取り出していく。今回はpandasを使っているので、applymap()やmap()メソッドで一気に変換する。resource.map(dt2f)各仕事の変数と制約を設定する。各仕事の作業開始時刻を設定する変数sは、時刻秒数を連続的に推移させるので、連続数の変数インスタンスをsolver.NumVar()で作成する。"s{}".format(n))solver.NumVar()には、第一引数に作成する変数の下限値、第二引数に上限値、第三引数に変数名を指定する。今回は全仕事で共通の上下限値である、リソースの使用可能時間を設定したが、変数作成時点では上下限無限にして制約で後付けしてもいい。各仕事sには、仕事毎の作業可能時間の上下限もあるので、solver.Constraint()で制約を作成して、SetCoefficient()メソッドで付加する。制約のインスタンスを作成した後、SetCoefficient()メソッドで対応する変数と係数を設定する。SetCoefficient()メソッドは第一引数に対応する変数のインスタンス、第二引数にその変数にかかる係数を設定する。このような制約を作ってから、変数と係数を設定する作りなので、事前に制約式を定数項と変数項でまとめておくとやりやすい。ここまでの流れを一連で書くとこのようになる。1)順序設定の変数と制約を設定する。作業開始時刻の変数sと同様に、順序設定の変数xとそれの制約を作成する。制約中にsを使うので、sを設定後に設定する。n1とn2の組合わせなので、itertools.combinations()で仕事jobsのイテレータから2つの組合わせを作成してイテレーションする。2):xは仕事n1がn2の前に作業完了するか否かを1,0で表現するので、solver.IntVar()で整数変数のインスタンスとして作成する。引数はsolver.NumVar()と同様。n2))順序に基づき後攻の作業開始時刻を、先行の作業完了時刻以降に制限する制約を作る。順序の設定によって、2つの相反する制約を排他的に切り替えるため、"適当な大きい値の実数"Mを作成する。すれば、実質無効化になるのでリソースの使用可能時間幅をMとすれば最悪値の時でも十分大きい値として機能する。resource["lower"]順序の制約を設定する。基本的には作業開始時刻の変数sと同様だが、こちらは関連する変数が複数あるので、式を定数項と変数項に整理して、各変数の符号・係数を明確にした上で設定する。M)ここまでの流れを一連で書くと以下のようになる。ないので、そのまま求解する。solver.Solve()で計算が実行され、結果のステータスが戻り値で得られる。ソルバのインスタンスにステータス判定用のプロパティを持っているみたいだが、公式ページ中でクラスのリファレンスなどを見つけられなかったので、とりあえずOPTIMALか否かで処理分けしてみる。概要として、変数の数・制約の数および求解結果のコスト関数の値を表示している。この辺は、公式ページに載っているサンプルそのまま。求解が終わった作業開始時刻を取り出す。後処理のためにpandas.DataFrameに保存する。求解で決まっているのは作業開始時刻だけなので、作業完了時刻は作業開始時刻から各仕事の作業時間をオフセットして決定する。"work"]求解結果だけだと、すべて起点からの秒数になっていて一目でわからないので、datatimeに変換しておく。sol.applymap(f2dt)最後に、作業開始時刻をキーにソートする。inplace=True)ここまでのすべてを一連にする。inplace=True)solちゃんと制限を守った順序になっている。目的関数未設定なので、仕事同士の間隔が空いている。今回の問題の趣旨ではないが、今後汎用的に使うなら目的関数の設定もできないといけないでしょう。いうことで、今回の問題で仕事の作業時間を最短にする目的を付加してみる。各仕事中の作業開始時刻の最短値及び、作業完了時刻の最長値を補助変数として、$s\_min$・$t\_max$に設定する。最長時刻と最短時刻の差分を最小化するようにコスト関数を定義する。補助変数を追加で作って、各仕事の作業開始時刻設定ループの中で制約を付加する。-1)目的関数のインスタンスを作成して設定する。基本的に制約式の設定の仕方と同じで、違いはインスタンスの生成時に指定するものがないことと、最大化問題か最小化問題かの設定があるくらい。最大化問題にしたい時はobjective.SetMaxmization()にすればいいが、各項の符号反転でも対応できるので覚えてなくてもよさそう。-1)objective.SetMinimization()以上を反映させたプログラムが下記。inplace=True)sol例として設定したデータの値が微妙だったせいでわかりにくいが、リソースの所要時間は最小化されている。最後に大きい問題はやったことがないが、ちょっとした問題には十分使える。デフォルトでつくソルバはCBC-Coinというオープンソースのものらしいので、PuLPとかほかのライブラリと同じような性能だと思われる。変数や制約をインスタンスとして作成してそれぞれ設定するやり方は好みが分かれそうだが、個人的には結構好き。今回はMIPを解いたが、いくつかヒューリスティックサーチのアルゴリズムも持っていたりするみたいなので、そのうち使ってみたい。「逐次処理でもできるんだけど、面倒だから式起こしちゃえ!」みたいなものから徐々に使って行ってみようかなと。requestStockLike13TAKE@kira4845しがないエンジニアです。組み込み系出身なので、電子回路設計~制御ソフトウェアの設計・実装は経験あります。最近はデータ分析系でPythonとか組合せ最適化とか勉強してます。コーポレート・ガバナンスとかが厳しいので、念のため所属している会社名は伏せてます。upLoginユーザーは見つかりませんでした。