全６回にわたり、数理最適化に関してご紹介いたしました。
とっつきにくい分野かもしれませんが、このコラムにて興味を持って頂ければ幸いです。

良きパートナーとして、弊社をご指名頂ければ幸いです。

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

線形計画問題	←	線形計画法 （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軸として制約条件を数式で表し、グラフで実行可能領域を示したいと思います。

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

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

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

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

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

最適化問題はいくつかの種類があり、それに対する解法が存在します。
はじめに線形計画法が発案され、それを応用して整数計画法と非線形計画法へと発展しました。

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

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

“線形計画問題”は一次式や一次不等式で表される制約条件の中で、一次式の目的関数を最大化または最小化する問題です。イメージしやすいように例題をご用意しました。

---

CCC動物園ではコアラを飼育していますが、近頃ぐうたらし過ぎて太ってしまいました。そこで、ダイエットのために糖質制限をかけて餌を与えることにします。主食のユーカリには糖質の他にも食物繊維、ミネラル、毒素が含まれていますが、ミネラル以外のものは取りすぎるとよくないので、こちらも摂取制限をかけます。
成分構成の異なる二つのユーカリをうまく食べ合わせて、なるべく多くのミネラルを摂取するにはどうすればいいでしょうか。

ユーカリ1gあたりの成分表（成分の単位：mg）

---

今回の目的はミネラル摂取量の最大化でした。
ユーカリAの質量をx、ユーカリBの質量をyとすると、

これを最大化することになります。
次に、今回の制約条件を一次不等式で表してみましょう。

これらの条件式から目的関数を求め、グラフ化すると以下の図のようになります。
横線で塗りつぶされた領域が制約条件を満たす範囲（実行可能領域）となり、この中から最も良い解を探索することになります。

最適化問題の中では最も簡単な問題であり、高速に解を得られる解法が存在します。
その中でも代表的なものとして、以下の２つの方法があります。

・単体法	（Simplex Method）
・内点法	（Internal Point Method）

数理最適ソルバでは単体法と内点法を組み合わせて最適解を導出しています。

さて、コアラにはユーカリをそれぞれ何gずつ与えれば良いのでしょうか。
答えは下図の黄色点部分となり、
　　ユーカリA：240g
　　ユーカリB：240g
を与えたときにミネラルの摂取が最大値（216mg）となります。

第2回の最後にご説明しましたが、最適化問題には2つの解法があります。

それぞれの解法は「どのような特徴を持っているのか」「どのようなアプローチがあるのか」について紹介していきます。

厳密解法は最適化問題に対する最も良い解を求める手法です。
厳密解法で求められた解は、数学的に最適であると証明されているということになります。
しかし、最適解を求めるためには多くの計算時間が必要となるため、大きすぎる問題は扱えない場合があります。

近似解法は、現実的な時間でなるべく良い解を効率よく得る手法です。
厳密解法と違い、求めた解は最適性を保証されませんが、高速に近似解を求めることができます。

実際に最適化問題を解く場合、厳密解法と近似解法のどちらを適用すればよいのでしょうか？
多くの場合、まずは厳密解法を適用してみます。
問題の難しさや規模によって現実的な時間で解けない場合、近似解法を適用することになります。

これまでは近似解法でないと解けない問題がほとんどでした。
しかし、数理最適ソルバとコンピュータの進歩により、現実的な問題にも厳密解法が適用できるようになっており、近年注目されてきています。

各々の解法に関する手法を体系的にまとめると、以下のようになります。

あなたは野菜を袋に入れて持って帰ろうとしています。
野菜は1種類につき1個ずつあり、組み合わせて袋に入れることが出来ます。
しかし、手元にある袋には重さの制限があり、5kgまでしか入りません。
持ち帰る野菜の価値の合計を最も高くするにはどの野菜を選択すればいいのでしょうか？

表を見ると、もっとも価値の高い野菜はかぼちゃ（500円）です。
しかし、袋にはかぼちゃ1つしか入りません。
重さ5kgという制限の中で、500円の価値を超えるような複数の野菜の組み合わせはないでしょうか。

キャベツ （4kg：350円）	＋	ナス （1kg：100円）	＝	5kg：450円
玉ねぎ （3kg：400円）	＋	ナス （1kg：100円）	＝	4kg：500円
トマト （2kg：150円）	＋	ナス （1kg：100円）	＝	3kg：250円
玉ねぎ （3kg：400円）	＋	トマト （2kg：150円）	＝	5kg：550円

例として挙げた問題は一目瞭然なほど簡単ですが、もし野菜の数を20種類とし、袋の容量を50kgまでとしたらどうなるでしょうか？

野菜の組み合わせが膨大な数となり、先ほどのように一つひとつのパターンを検証していくやり方では、人間はもちろん、コンピュータが行っても気が遠くなるほどの時間がかかってしまいます。（野菜の組み合わせはなんと約100万（2^20）通り！）
実際にはさらに多くの組み合わせや制約条件の中で解を求める事になるので、非常に難解な問題だと言えます。

上記のような、最適化問題を解くための方法は2つあります。

今回の連載テーマである数理最適化は厳密解法に分類されます。

第１～２回でご紹介した内容をまとめます。

• 数理最適化とは数学的手法で最適な解を導出すること
• 数理最適ソルバとコンピュータの進歩により、大きな問題も解けるようになってきた
• 検証すべき組み合わせの数が膨大となるため、最適化問題は非常に難解な問題である
• 最適化問題を解く方法は、厳密解法と近似解法の2つに分類される

第１回は、「数理最適化とはどういったものなのか？」というテーマでご紹介したいと思います。

最適化とは、“様々な制約条件を設定し、その制約を満たす選択肢の中から何らかの観点で最適なものを決定すること”です。

最適化は今や社会にとっても欠かせない技術となっており、配送業者の効率的な物流ルートの設定、行政による公共施設の最適配置など、様々な分野で利用されてきています。

数理最適化とは“実際の問題を数式で表し、数学的手法で最適な解を導出すること”を指します。
数理最適化は非常に難しい問題であり、昔から研究者たちがしのぎを削って研究してきました。その成果もあって、数理最適問題を解くことに特化した数理最適ソルバというソフトウェアが登場します。
数理最適ソルバは、計算アルゴリズムの改良によって、計算速度が年々高速化されてきました。20年で10万倍以上高速になったと言われており、これは、1日以上計算が必要な問題が、1秒以下で解けるようになったということを示しています。
また、コンピュータの処理能力も向上しているので、数理最適ソルバで解ける問題の範囲がどんどん広がってきています。

数理最適化を活用した2つの事例を簡単にご紹介します。

ポートフォリオとは、資産を投資する金融商品の組み合わせを指していて、リスクは低いが得られる利益の小さい安全資産と、リスクは高いが得られる利益が大きくなる可能性のある危険資産の保有構成を表します。
リスクを低く抑え過ぎると利益が得られず、利益ばかり狙いすぎると大損する危険性が高くなるので、ちょうど良いバランスが求められます。
そこで、過去のデータを利用して数理最適化を適用し、最適なポートフォリオを導出することによって、ローリスク・ハイリターンの運用を実現しています。

コールセンターやサービス業はシフト制を敷いているところがほとんどです。
たとえば、あるコールセンターでは下記のような傾向があるとします。

このように時間帯毎に要求されるオペレーターの人数や知識が異なる場合、それを満たすように従業員のシフトを作成しなければなりません。
また、シフトに偏りが発生してしまうと、従業員のストレスになってしまいます。
この場合も、過去のデータを元に要求されるオペレータの人数や知識を予測して、公平性と労働基準を満たす人員配置計画を作成します。
こういった人員配置を最適化することを、一般的にWFM（Workforce Management）と呼びます。