数理最適化ソルバーである OR-Toolsをインストールして使ってみる
大学の研究で使うことになったのでインストール方法と簡単な問題をPythonで解く方法をまとめてみました．
本記事ではWindows向け，またPythonは既にインストールしてあるものとして解説します．
公式サイトにはインストール方法などが載ってはいますが、コマンドラインの説明がなく、コマンドラインを全く知らない、もしくはあまり見たくない、という人にとっては難しいかもしれないと思ったため出来るだけ詳しくインストール手順から簡単な問題を解くまでを記しました。
目次
1.この記事の対象者
2.コマンドラインからpipコマンドを用いたOR-Toolsのインストール
3.実際に簡単な問題を解いてみる
この記事の対象者
この記事は以下のような人物を対象としています．
・OR-Toolsのサイトを見に行ったけどインストールガイドが難しかった
・とりあえず組み合わせ最適化問題をなんか解きたい
・コマンドライン難しくてよくわからない
1.コマンドプロンプトからpipコマンドを用いたOR-Toolsのインストール
Windowsボタンを押し，アプリ，設定，ドキュメントの検索からコマンドプロンプトを検索
コマンドプロンプトを開く．
こんな感じの画面が出てくると思います。
まず，コマンドプロンプトに以下のコマンドを入力してOR-Toolsが入っているかどうか確かめます．
$ pip list
($は入力する必要はありません)
このリストの中にOR-Toolsがなければまだインストールができていないため，以下のコマンドを入力してください．
$ pip install -U --user ortools
※少し時間かかります
Successfully installed absl-py-2.0.0 numpy-1.26.1 ortools-9.7.2996 protobuf-4.24.4
このように表示されたら，インストール完了です．(数字はバージョンによって異なる場合があります)
念のため先ほどのコマンドでちゃんとインストールされているか確認しておきましょう．
$ pip list
これでOR-Toolsがあればインストール完了です．
2.簡単な問題を解いてみる
Googleの公式サイトにはスタートガイドとして様々な例題とその解き方のソースコードが載っています。
その中でオーソドックスな0-1ナップザック問題をOR-Toolsを用いて解いていきます。
今回解くナップザック問題は以下のような問題とします。
ナップザックの容量：50kg
ナップザックに入れられるアイテム
化石A：5万円 23㎏
化石B：6万円 26㎏
化石C：4万円 19㎏
化石D：8万円 30㎏
化石E：3万円 17㎏
これを重複なしでナップザックに入れていく場合、価値が最大になる入れ方を求めます。
ナップザック問題を解くソースコードはGoogleがサンプルコードを出しているため、その数値を少し変えるだけで今回の問題は解決することができます。
valuesの部分を今回の化石A～Dの金額に、weightsの部分を今回の化石A～Dの重さに、capacitiesを今回のナップザックの容量に書き換えます。
#ナップサック問題を解くためのアルゴリズム
from ortools.algorithms.python import knapsack_solver #OR-Toolsのインポート
values = [5,6,4,8,3] #アイテムの価値
weights = [
[23,26,19,30,17]
] #アイテムの重さ
capacities = [50] #ナップサックの容量
def main():
solver = knapsack_solver.KnapsackSolver(
knapsack_solver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample",
) #ソルバーの呼び出しとアルゴリズムの指定
solver.init(values, weights, capacities) #ソルバーの初期化
computed_value = solver.solve()
packed_items = []
packed_weights = []
total_weight = 0
print("Total value =", computed_value)
for i in range(len(values)):
if solver.best_solution_contains(i):
packed_items.append(i)
packed_weights.append(weights[0][i])
total_weight += weights[0][i]
print("Total weight:", total_weight)
print("Packed items:", packed_items)
print("Packed_weights:", packed_weights)
if __name__ == "__main__":
main()
pythonでこれを実行すると
Total value = 12
Total weight: 49
Packed items: [2, 3]
Packed_weights: [19, 30]
このように表示され，化石Cと化石Dが選ばれたことが分かります．
今回はOR-Toolsをインストールしてから簡単なプログラムを動かすまでを載せました．
OR -Toolsの公式チュートリアルには今回のナップサック問題だけでなく様々な問題のサンプルコードが載っていますので是非参照してください．