連載コラム
『数理最適化』

第5回 数理最適化とその歴史②

2017.1.12

第4回に引き続き、「厳密解法である数理最適化はどのようにして解を出すのか?」という点に関して、数学者達の発案の歴史に焦点を当てながら「各手法の特徴」を紹介したいと思います。

【ふりかえり】最適化問題の種類と解法

前回、最適化問題はいくつかの種類があり、それに対する解法が存在することを説明しました。

線形計画問題  ←  線形計画法
(Linear Programming, LP)
整数計画問題  ←  整数計画法
(Integer Programming, IP)
非線形計画問題  ←  非線形計画法
(Nonlinear Programming, NLP)

今回は“整数計画問題”と“非線形計画問題”について紹介します。

整数計画問題(Integer Programming Problem)

整数計画問題は制約条件や目的関数に整数を扱えるようにした問題です。
最適化する対象が人や物など、整数でないと意味がない場合、整数計画問題として定義します。
線形計画問題に比べて整数計画問題の方がより現実に近い問題を取り扱うことができます。第2回で取りあげた「ナップザック問題」などの“組み合わせ最適化問題”などがこれに当てはまります。

線形計画法のように高速な解法が存在せず、多くの計算時間が必要となるため、線形計画問題に比べて難しい問題となります。
1957年にライフ・ゴモリーによって発案された切除平面法という解法が整数計画法の始まりとされていますが、現在では、整数計画問題を解くための一般的な方法として分枝限定法(Branch and Bound)が用いられています。

分枝限定法(Branch and Bound)

1960年に英国のランドとドイグが発案した手法です。
下の図のように元の問題を子問題へ再帰的に分割して解いていく方法です。子問題を線形計画法で解き、答えが整数でない場合、さらに子問題に分割していきます。
子問題へ分割したとき、明らかに最適解が含まれていないことが分かった場合、その子問題は解く必要がありませんので、その子問題から先の計算を省略することができます。(限定操作)
このようにして計算を省略しながらすべての領域を探索し終えたとき最適解が得られます。

数理最適ソルバの登場

単体法(当連載第4回でご紹介しました)と分枝限定法が発案された後に、最適化問題を解くための汎用ソフトウェアである数理最適ソルバが登場します。数理最適ソルバは数理計画法と共に進歩し、様々なソフトウェアが競い合うように発展してきました。
現在では、数理最適化を行う=数理最適ソルバを利用するといった形式が一般的となっています。

数理最適ソルバには商用とフリーのソフトウェアが存在しており、代表的なものとして、

商用 Gurobi Optimizer(製品情報はこちら
非商用 lp_solve(詳細はこちら
CBC(詳細はこちら
SCIP(詳細はこちら

などがあります。 (※各リンクは外部サイトへ遷移します。)

商用ソルバは非商用ソルバに比べて高速に動作し、より多くの問題を解くことができます。

非線形計画問題(Nonlinear Programming Problem)

線形計画問題や整数計画問題はあくまで一次式のみでしたが、非線形計画問題は制約条件と目的関数に非線形式(一次式以外)が含まれている問題のことを指します。
現在でも非常に限られた状況でなければ現実的な時間で解くことが難しい問題ですが、定式化を工夫することにより整数計画問題として定義できる問題は解くことができるようになります。また、非線形の制約を緩和して解くこともできます。

第4回で取りあげた例題に新たな制約条件を加えて、非線形計画問題へ変えてみましょう。元の問題は第4回のコラムにてご確認ください。(→第4回へ


新たな制約条件

  • コアラの餌であるユーカリを購入する予算は60,000円と決まっています。
  • ユーカリAは単価の定価が300円ですが、購入量が増えれば増えるほど割引率が大きくなります。グラムあたりの値引きが0.375円で設定されているので、ユーカリAの単価は以下のように表すことができます。(xはユーカリAの購入量)
  • ユーカリBは単価が100円で割引はありません。



新たな制約条件である予算に収まり、かつ、当初の目的であるミネラル摂取量を最大化するにはどうすればいいでしょうか。前回同様、ユーカリAの購入量をx軸、ユーカリBの購入量をy軸として制約条件を数式で表し、グラフで実行可能領域を示したいと思います。

予算の制約条件はそれぞれ単価と購入量をかけて、以下のように表します。

これを整理すると以下のように二次式となり、新たな制約条件によって非線形計画問題となったことが分かります。

前回のグラフに今回の制約条件を追加して実行可能領域(横線で塗りつぶされた領域)を示すとこのようになります。

グラフで実行可能領域を示すことはできましたが、このような非線形の制約を含む問題は“非線形に特化した数理最適ソルバ”でなければ解くことができません。
さらに、非線形に特化した数理最適ソルバであればどんな非線形計画問題でも解ける訳ではなく、様々な制限が出てくるため、なるべく線形緩和して解くというのが現在では一般的です。


次回、制約を緩和して実際に解を求めるところまでの具体的な流れをご紹介いたします。

第4~5話のまとめ

  • 線形計画問題は高速に解を求めることができる
  • 整数計画問題は現実的な問題を定義できるが、計算時間が必要となる
  • 数理最適化は数理最適ソルバというソフトウェアを利用して解く
この連載のバックナンバーはこちら