モチベーション

「あたらしい数理最適化 python言語とGurobiで解く」
を教科書として、数理最適化の基本となるところを、肌感覚で理解したい。そのために、

基礎的な内容
その例題演習

を書くことで、自身の理解と、新たな仕事の確保を目指します。私の大本のモチベーションはここを参照してください。

この記事を読むとできること

初回なので

~~Gurobi~~ Google OR-Toolsをインストールし、pythonでHello-worldする
簡単な問題を解き、きちんと動くことを確認する

を目指します。

ステップ1: Gurobiを採用できなかった

まずは、Gurobiをインストールしようと思いましたが、使用にライセンスが必要でした。結論から述べると、「アカデミックの人間でないので、ライセンス取得に金がかかる」ことを理由に断念しました。なので、学生さんは使ってみてはいいんじゃないでしょうか。

Gurobiの公式サイト
 Gurobiのライセンスについて

追記：Named User ライセンスなら行ける可能性はあります。
しかしながら、今回は仕事に使いたいので、余計な学習は避けます。

ステップ2: Google OR-Toolsをインストールする

仕方ないので、代替品を探します。どうせ、googleが出しとるやろ、と気軽に、「google OR」で調べてやると、「Google OR-Tools」がヒットしました。本来ならば、性能やら用意してある解法についてソルバの比較が必要だと思います。今回はざっくり体験するため、使えるならば何でも良い、との目的のもと、こいつを相棒としました。

インストール

Google OR-Toolsから、ツールをダウンロードします。C++, Python, C#, Javaで利用できるので、今回は慣れ親しんでいることも含め、Python版を利用します。残念ながら、Google OR-Toolsインストールについて、これ以上深い説明は述べません。丁寧に解説してある上、ただインストールするだけですし、今回の主題ではないですから...。

ステップ3:Getting Start

何はともあれ、とりあえず写経から! Python用のStart Guideから、写経をしていきます。

上記ページより引用：

/path/to/your_program.py


from __future__ import print_function
from ortools.linear_solver import pywraplp

def main():
  solver = pywraplp.Solver('SolveSimpleSystem',
                           pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
  # Create the variables x and y.
  x = solver.NumVar(0, 1, 'x')
  y = solver.NumVar(0, 2, 'y')
  # Create the objective function, x + y.
  objective = solver.Objective()
  objective.SetCoefficient(x, 1)
  objective.SetCoefficient(y, 1)
  objective.SetMaximization()
  # Call the solver and display the results.
  solver.Solve()
  print('Solution:')
  print('x = ', x.solution_value())
  print('y = ', y.solution_value())

if __name__ == '__main__':
  main()

で、python3 /path/to/your_program.pyで動きます。私の環境では一発成功。成功しないと面倒くさいですから、これはラッキーでした。

ステップ4:何が起こったか検査する

さて、お経から何が起こったかを調査します。

ソルバインスタンスの生成

  solver = pywraplp.Solver('SolveSimpleSystem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

これは、ソルバーのインスタンスを立てているに違いないですね。第一引数で名前を付けられて、第二引数でソルバの種類を選べるみたい。ソルバの種類はどのみち調べないと行けないので、後回しします。

変数と値域の設定

    x = solver.NumVar(0, 1, 'x')
    y = solver.NumVar(0, 2, 'y')

ここで変数と値域を設定するようです。

目的関数の設定

  objective = solver.Objective()
  objective.SetCoefficient(x, 1)
  objective.SetCoefficient(y, 1)
  objective.SetMaximization()

どうやら、objectiveが目的関数を表しているらしい。Coefficientは係数のことなので、今回の場合は、

\begin{align}
&\rm{maximize} & & x+y \\
&\rm{subject\ to} & & 0 \leq x \leq1 \\
& & & 0 \leq y \leq2
\end{align}

という線形計画問題を解くことになります。なので、

\begin{align}
&x=1,& y=2&
\end{align}

が答えになるでしょう。実際そのように出力されました。

結果

Solution:
x =  1.0
y =  2.0

次何をするか

今回は問題例としては非常に簡単なものでした。さらなる疑問としては、

制約条件はどこで入れるのか
二次計画問題とか、非線形な問題はどのように表現するか
実際の問題特性と、どれほど早いか
ソルバの特徴

などが思いついています。ここもおいおい調べて見ましょう。

終わりに

実質、この記事が最初の投稿です。まだまだわからないことがたくさんあるので
何でもいいのでコメントを残して頂けると、僕がめちゃくちゃ喜びますし、良いと思ったものは取り入れます。よろしくお願いします。

#1 Google OR-toolsを使って hello-worldする