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

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

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

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

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

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

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

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

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

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

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

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

---

新たな制約条件

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

---

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

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

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

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

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

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