はじめに
数理最適化についての参考テキスト「Pythonによる問題解決シリーズ データ分析ライブラリーを用いた最適化モデルの作り方」の練習問題を解きます。
本書はPythonのツールPuLPが使用されていますが、ここでは、Googleのフリーツール「OR-Tools」を使用します。
■Googleのフリーツール「OR-Tools」
https://developers.google.com/optimization
■参考テキスト
「Pythonによる問題解決シリーズ データ分析ライブラリーを用いた最適化モデルの作り方」
斉藤努[著]
近代科学社[出版]
準備
プログラムを実行する環境を準備します。
環境は以下としました。
| 環境 |
|---|
| 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番目です。
問題
1x1マスに、1から3の数字のいずれか1つを入れることを考える。
制約条件は「1マスの数字の合計が2である」とする。
1マスに入る数字は何か?
考え方
当該の1x1マスに入る数字が1なのか、2なのか、3なのか、それぞれの場合(3パターン)でYesまたはNoを判断する3つの変数を考えます。
これらの変数を左から順にVar1,Var2,Var3と定義します。
それぞれの変数は0(Noの場合)または1(Yesの場合)をとると定義します。
(0まはた1のみを取る変数を0-1変数、またはバイナリー変数と呼びます)
Var1,Var2,Var3の各変数がどんな値を取りうるか、その条件を考えながら解法を探ります。
(上記の条件を制約条件と呼びます)
解答
制約条件を考えます。
制約条件①
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)
プログラムの冒頭におまじないを書きます。
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,Var2,Var3についての非負条件(マイナス値でないこと)
Var1 = solver.IntVar(0.0, 1, 'Var1')
Var2 = solver.IntVar(0.0, 1, 'Var2')
Var3 = solver.IntVar(0.0, 1, 'Var3')
制約条件①を定義します。
solver.Add(Var1 + Var2 + Var3 == 1)
制約条件①を定義します。
solver.Add(1 * Var1 + 2 * Var2 + 3 * Var3 == 2)
制約条件を定義後、計算を実行し解を求めます。
status = solver.Solve()
最後に結果を確認します。
解が存在する場合は、statusの値がpywraplp.Solver.OPTIMALとなります。
変数.solution_value()で各変数の値を取得します。
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であることがわかりました。
以下にプログラムの全体を記載します。
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.')
ご意見など
ご意見、間違い訂正などございましたらお寄せ下さい。