#
はじめに
数理最適化を初めて学ぶ勉強資料の1回目です。
これから各回を通して、数理最適化を学んでいきましょう。
数理最適化
と聞くと、初めて聞くとか、何だか難しそう…と聞こえますが、構えるほどではありません。
「そっかぁ、こんな考え方で、こんなふうに解くんだ～」
それを学んでいきましょう。エンジニアとして新しい知識を学べば、他の分野でもそれを応用でき、メリットがあるに違いありません。
ついでにこれで仕事になれば食い扶ちになるかな!?
# 教材
本記事では、数理最適化モデルについて参考テキスト「Pythonによる問題解決シリーズ データ分析ライブラリーを用いた最適化モデルの作り方」の練習問題などを見ながら進めていきます。テキストの詳細は以下です。
■参考テキスト
「Pythonによる問題解決シリーズ データ分析ライブラリーを用いた最適化モデルの作り方」
斉藤努[著] ／ 近代科学社[出版]
# 数理最適化とは？
参考テキストから引用します。最適化とは、以下のような問題を解決するための手段となります。
自宅の最寄り駅から会社へ行くのに最短時間の経路を知りたい。
リュックサックに入れる商品の価値の合計を最大化したい。
倉庫から工場へ原料を輸送する費用を最小化したい。
また、最適化と機械学習とは以下の違いがあります。
機械学習
過去を物指しに未来を知る
最適化
モデルを物指しに未来を決める
モデルとは何か?この後はモデルについて解説して参ります。
# 最適化モデル
モデルとは、現実問題を数式などに置き換えて何らかの解を算出できる形にしたものです。最短経路を探索する場合は、探索経路を表現する数式を考えモデルとします。また、リュックサックの詰め物問題は、詰めた状態を表す数式を考えモデルとします。
モデルを構築した後、次の作業はソルバーと言われるコンビュータのソフトを使用して解答を得る作業に入ります。
ソルバーには有料のものと無料のものがあります。
ここでは、ソルバーとして無料のCBC(Coin Or branch and Cut)を使用します。
また、組み合わせ最適化を解くための専用ライブラリである、Google社が提供しているOR-Toolsを使用します。
このOR-ToolsはPythonで書かれています。
OR-Toolsについては以下をご参照下さい。
■Googleのフリーツール「OR-Tools」
https://developers.google.com/optimization
# モデルの構成要素と制約条件
モデルを構築するにあたり、以下の3つの構成要素があります。
①変数
モデル上で様々な値を取り得る数値の入れ物。数式を当てはめる対象となるもの。
②目的関数
良い解を探すための指標。変数を使った数式を用いて関数として表し、その関数が最大か最小となるように計算することで解を求める。
③制約条件
変数の組み合わせや数式としてで守るべき条件。
制約条件は次のいずれかの書き方をします。複数の条件を指定できますが、指定した条件を全て守らなければなりません。
数式 ≧ 数式
数式 ＝ 数式
数式 ≦ 数式
※ここで、≠ ＜ ＞ は使用できません。
モデルは数式を使って表現するので数理モデルと呼ばれます。
また、厳密に数式だけでモデルを表現することを定式化する、といいます。
# 最適化の種類
最適化問題には以下の3種類があります。
線形最適化問題
(LP：Linear programming Problem)
連続変数しか使用できない。目的関数と制約条件は線形の式でなければならない。問題は簡単に解ける。制約条件の数が数千の問題でも解かれている。
混合整数最適化問題
(MIP：Mixed Integer programming Problem)
連続変数と離散変数が使用できる。目的関数と制約条件は線形の式でなければならない。基本的には簡単に解けない。変数や制約条件の数が少なければ解きやすい。
一般の最適化問題
変数、目的関数、制約条件に制限が無い。研究では非線形最適化問題(NLP：Non-Linear programming Problem)という分類で扱われている。解くのは場合によっては解けるが、基本的には難しい。
※連続変数とは、実数値を取る変数です。一方、離散変数とは、整数のようにとびとびの値だけを取れる変数です。
# 終わりに
次回は第2回目、典型問題についての予定です。お読み頂けたら幸いです。
当記事については、著者も最適化の入門者です。誤解・誤植等至る所にあると思いますので、お気軽にご意見やご指摘などお寄せ下さい。