GoogleのOR-Toolsで数理最適化モデルの練習問題を解く(1)一番易しいマス埋め問題

#はじめに

数理最適化についての参考テキスト「Pythonによる問題解決シリーズ　データ分析ライブラリーを用いた最適化モデルの作り方」の練習問題を解きます。
本書はPythonのツールPuLPが使用されていますが、ここでは、Googleのフリーツール「OR-Tools」を使用します。

■Googleのフリーツール「OR-Tools」
https://developers.google.com/optimization

■参考テキスト
「Pythonによる問題解決シリーズ　データ分析ライブラリーを用いた最適化モデルの作り方」
　斉藤努[著]
　近代科学社[出版]
![001.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/399135/f0b2ec71-1647-81b0-3630-cf5388c2e7d6.jpeg)

#準備
プログラムを実行する環境を準備します。
環境は以下としました。

|環境|
|:---:|
|Python 3.6.8|
|ortools 7.2.6977|
|pandas 0.23.4|

GoogleのOR-Toolsは以下のコマンドでインストールします。
`pip install --upgrade --user ortools`


インストールについて、Googleの解説ページがこちらにあります。
https://developers.google.com/optimization/install



#一番易しいマス埋め問題

参考テキストに出てくる練習問題の1番目です。

>:speech_balloon: 問題

```ruby:7.1.問題
1x1マスに、1から3の数字のいずれか1つを入れることを考える。
制約条件は「1マスの数字の合計が2である」とする。
1マスに入る数字は何か?
```

>:question: **考え方**


当該の1x1マスに入る数字が1なのか、2なのか、3なのか、それぞれの場合(3パターン)でYesまたはNoを判断する3つの変数を考えます。

これらの変数を左から順にVar1,Var2,Var3と定義します。
それぞれの変数は0(Noの場合)または1(Yesの場合)をとると定義します。
(0まはた1のみを取る変数を0-1変数、またはバイナリー変数と呼びます)

Var1,Var2,Var3の各変数がどんな値を取りうるか、その条件を考えながら解法を探ります。
(上記の条件を制約条件と呼びます)

>:a: **解答**

制約条件を考えます。

**制約条件①**
1マスに整数は一つしか入らないので、Var1,Var2,Var3の値は以下のいずれかのパターンになることが分かります。

|Var1|Var2|Var3|条件|
|:--:|:--:|:--:|:--:|
| 1 | 0 | 0 |1マスに1が入っている条件|
| 0 | 1 | 0 |1マスに2が入っている条件|
| 0 | 0 | 1 |1マスに3が入っている条件|

よって、上記の表から以下を導くことができます。
`Var1 + Var2 + Var3 = 1`


**制約条件②**
制約条件①では、1マスにいずれか一つの数字が入るという条件を定義できました。
ここでは、1マスの数字の合計が2であるという条件を定義します。

1マスの数字の合計は以下の式で表すことができます。
`1 x Var1 + 2 x Var2 + 3 x Var3`

検証してみます。

1マスの数字が1の場合は、数字の合計を表す式は以下のように示すことができます。
`1 x 1 + 2 x 0 + 3 x 0`
これを満たすのはVar1=1,Var2=0,Var3=0の場合です。

1マスの数字が2の場合は、数字の合計を表す式は以下のように示すことができます。
`1 x 0 + 2 x 1 + 0 x 3`
これを満たすのはVar1=0,Var2=1,Var3=0の場合です。

同様に1マスの数字が3の場合は、数字の合計を表す式は以下のように示すことができます。
`1 x 0 + 2 x 0 + 3 x 1`
これを満たすのはVar1=0,Var2=0,Var3=1の場合です。

よって、1マスの数字の合計が2となる制約条件式について、以下を導くことができます。
`1 x Var1 + 2 x Var2 + 3 x Var3 = 2`


以上で制約条件が決定しました。


プログラムを検討します。
プログラムの記載内容については、基本的にGoogleのOR-Toolsのガイドに沿っています。
(https://developers.google.com/optimization)


プログラムの冒頭におまじないを書きます。

```ruby:7.1.renshu.py
from __future__ import print_function
from ortools.linear_solver import pywraplp
```

この問題は整数解を扱う問題ですが、目的関数はありません。
混合整数計画問題に近い問題で、混合整数計画ソルバーで解いてみます。

以下に宣言します。

```ruby:7.1.renshu.py
# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
                             pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
```

Var1,Var2,Var3はマイナス値を取らない条件を付けます。

```ruby:7.1.renshu.py
# Var1,Var2,Var3についての非負条件(マイナス値でないこと)
Var1 = solver.IntVar(0.0, 1, 'Var1')
Var2 = solver.IntVar(0.0, 1, 'Var2')
Var3 = solver.IntVar(0.0, 1, 'Var3')
```

制約条件①を定義します。

```ruby:7.1.renshu.py
solver.Add(Var1 + Var2 + Var3 == 1)
```

制約条件①を定義します。

```ruby:7.1.renshu.py
solver.Add(1 * Var1 + 2 * Var2 + 3 * Var3 == 2)
```

制約条件を定義後、計算を実行し解を求めます。

```ruby:7.1.renshu.py
status = solver.Solve()
```

最後に結果を確認します。
解が存在する場合は、statusの値がpywraplp.Solver.OPTIMALとなります。
`変数.solution_value()`で各変数の値を取得します。


```ruby:7.1.renshu.py
if status == pywraplp.Solver.OPTIMAL:
    print('Solution Done! The result is below.')
    print('Var1=',Var1.solution_value())
    print('Var2=',Var2.solution_value())
    print('Var3=',Var3.solution_value())
else:
    print('Unsolved the problems.')
```

今回の計算の結果、解は以下となりました。
>Solution Done! The result is below.
>Var1 = 0.0
>Var2 = 1.0
>Var3 = 0.0

よって、問題の答えが数字の2であることがわかりました。

以下にプログラムの全体を記載します。

```ruby:7.1.renshu.py
from __future__ import print_function
from ortools.linear_solver import pywraplp

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('simple_mip_program',
                             pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# Var1,Var2,Var3についての非負条件(マイナス値でないこと)
Var1 = solver.IntVar(0.0, 1, 'Var1')
Var2 = solver.IntVar(0.0, 1, 'Var2')
Var3 = solver.IntVar(0.0, 1, 'Var3')

# 制約条件(1)
solver.Add(Var1 + Var2 + Var3 == 1)

# 制約条件(2)
solver.Add(1 * Var1 + 2 * Var2 + 3 * Var3 == 2)

# 計算実行
status = solver.Solve()

# 結果確認
if status == pywraplp.Solver.OPTIMAL:
    print('Solution Done! The result is below.')
    print('Var1=',Var1.solution_value())
    print('Var2=',Var2.solution_value())
    print('Var3=',Var3.solution_value())
else:
    print('Unsolved the problems.')
```

# ご意見など

ご意見、間違い訂正などございましたらお寄せ下さい。