最適化問題とは

最適化問題とは

最適化問題とは、複数の制約条件下で目的値の最大値ないし最小値を求めることを指す。「何を意思決定するのか（変数）」「制約条件」「最大化ないし最小化する値（目的関数）」の3点を定義し、それらを定式化することではじめてコンピューターが最適解を出すことができる。

現在、生産計画や配送計画、人員計画のような複雑な意思決定において最適化問題が応用されている。
コンピューターがこれらの意思決定の最適解を自動算出するため、企業は意思決定のスピードと精度を上げ、コスト削減や利益最大化に繋げることができる。

最適化問題でよく出てくるナップサック問題とは

ここで最適化問題をイメージするものとして「ナップサック問題」を例に挙げる。
ナップサック問題とは、「容量（重量）の決まったナップサックに価値や容量（重量）がわかっている品物を詰めなければならない。ナップサックの容量には上限があるため、無限に品物を詰めるわけにはいかない。この場合、価値の総和を最大にするためには、どの品物を選べば良いか」という問題であり、組合せ最適化問題の代表的な例の一つとしてよく知られている。

簡単な例として、容量が20kgのナップサックに以下の商品を詰める場合の最適解を考える。

商品	A	B	C
容量（kg）	10	7	5
価値（円）	20000	15000	12000
価値/容量	2000	2143	2400

最適化問題を解く場合には厳密解が求められるケースと近似解を求めれば十分であるケースに大別されるが、複雑な意思決定になるほどスピードを優先し後者の判断になる場合が多い。ただし今回の事例は簡易であるため、厳密解を求める「全部の組み合わせを考える（全探索）」と、近似解を求める「重量あたりの価値が高い順に選ぶ（貪欲法）」の解き方をそれぞれ紹介する。
まず全探索で考えると、各商品について「選択する・しない」の2通りずつあるため、2×2×2＝8通り存在する。さらに、この8通りについてそれぞれ価値の総和を求めると容量を満たす最大値はAとBの組み合わせとなる。一方、貪欲法で考えると、重量あたりの価値が高い順に組み合わせたBとCの組み合わせが最適解となり、全探索と異なる結果が出る。また、ビジネスシーンで最適化問題を解く場合には、組み合わせの条件や変数が増えるため、この問題よりはるかに複雑性を増すと考えられる。
したがって実際のビジネスシーンでは、ある程度良質な解が速く出されることを優先し、近似解を求めれば十分とされることが多い。

最適化問題でFPGAが必要な理由とは

上述の通り、最適化問題を解くには多大な時間を要する。
例えば、仮に商品が10種類に増えただけでも2^10=1,024通り考えられる。加えて制約条件を加味して各通りについてシミュレーションした値を求めるとなると、複雑性は急激に増す。
そこで必要となるのが、FPGAである。
FPGAとはField-Programmable Gate Arrayの略であり、現場の設計者がプログラムできるデバイスを指す。回路構成の自由な選択により、さまざまな要求に対して柔軟に対応することができるとして、近年ではビッグデータのデータ処理などでニーズが高まっている。
CPUをベースとする一般的なコンピュータは大規模な計算を扱うと相当の時間が掛かる一方、FPGAを用いると最適なアルゴリズムを自由に実装することができるため高速処理が可能となる。
したがって、現在では最適化問題を扱うにあたりFPGAを用いられるケースが多い。

最適化問題の具体例

最後に最適化問題の身近な具体例として、ビジネスにおける実例を紹介する。

鉄道情報システム株式会社「勤務シフト作成お助けマン」
JR関連のシステム開発のノウハウを活かし、一般企業向けにもシステム提供を行う同社は「勤務シフト作成お助けマン」というシフト作成システムを」一般企業向けに提供する。このシステムに株式会社NTTデータ数理システムが開発した数理最適化システムNumerical Optimizerが搭載されており、これによりシフト作成者の様々な要求に応じたシフトを柔軟に組むことが可能である。

シフト作成の場合、目的関数と制約条件は以下の通りになる。

目的関数

希望シフトや定休日など

制約条件

曜日・ポジションごとの必要人員、労基ルールなど

そして、これらを数式化し制約条件を満たす目的関数の最大値ないし最小値を求めた結果、忙しい時間帯のシフトは多めにする、特定のスタッフに負担がかからないようにするなど適切な調整がなされたシフトができあがることとなる。