無料数理最適化ソルバーOR-Toolsのインストールから簡単な問題を解くまで

<h2>数理最適化ソルバーである OR-Toolsをインストールして使ってみる

大学の研究で使うことになったのでインストール方法と簡単な問題をPythonで解く方法をまとめてみました．
本記事ではWindows向け，またPythonは既にインストールしてあるものとして解説します．
公式サイトにはインストール方法などが載ってはいますが、コマンドラインの説明がなく、コマンドラインを全く知らない、もしくはあまり見たくない、という人にとっては難しいかもしれないと思ったため出来るだけ詳しくインストール手順から簡単な問題を解くまでを記しました。

---

<h3>目次<h3>

1.この記事の対象者
2.コマンドラインからpipコマンドを用いたOR-Toolsのインストール
3.実際に簡単な問題を解いてみる

---


<h4>この記事の対象者

この記事は以下のような人物を対象としています．
・OR-Toolsのサイトを見に行ったけどインストールガイドが難しかった
・とりあえず組み合わせ最適化問題をなんか解きたい
・コマンドライン難しくてよくわからない

---

<h4>1.コマンドプロンプトからpipコマンドを用いたOR-Toolsのインストール

 Windowsボタンを押し，アプリ，設定，ドキュメントの検索からコマンドプロンプトを検索
![qiita投稿用１.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3573354/676b579d-4cb3-00e4-03e0-980d0f79ea15.png)

コマンドプロンプトを開く．
![commandline.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3573354/1b2498ce-50f3-1a16-89c7-114902e33ffb.png)

こんな感じの画面が出てくると思います。

まず，コマンドプロンプトに以下のコマンドを入力してOR-Toolsが入っているかどうか確かめます．

```:コマンドプロンプトに入力するコマンド
$ pip list
```

![piplist.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3573354/e3e40e4c-4132-e776-fda3-bc31a25acfda.png)




($は入力する必要はありません)
このリストの中に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があればインストール完了です．
![ortools.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3573354/10857239-21d7-83a9-a106-796dd4ac655f.png)

---
<h4>2.簡単な問題を解いてみる


Googleの公式サイトにはスタートガイドとして様々な例題とその解き方のソースコードが載っています。

https://developers.google.com/optimization/introduction?hl=ja

その中でオーソドックスな0-1ナップザック問題をOR-Toolsを用いて解いていきます。
今回解くナップザック問題は以下のような問題とします。


ナップザックの容量：50kg
ナップザックに入れられるアイテム
化石A：5万円　23㎏
化石B：6万円　26㎏
化石C：4万円　19㎏
化石D：8万円　30㎏
化石E：3万円　17㎏

これを重複なしでナップザックに入れていく場合、価値が最大になる入れ方を求めます。

ナップザック問題を解くソースコードはGoogleがサンプルコードを出しているため、その数値を少し変えるだけで今回の問題は解決することができます。

https://developers.google.com/optimization/pack/knapsack?hl=ja#complete_programs

valuesの部分を今回の化石A～Dの金額に、weightsの部分を今回の化石A～Dの重さに、capacitiesを今回のナップザックの容量に書き換えます。

```py
#ナップサック問題を解くためのアルゴリズム

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の公式チュートリアルには今回のナップサック問題だけでなく様々な問題のサンプルコードが載っていますので是非参照してください．