組合せ最適化問題とは
組合せ最適化問題とは、様々な制約の下で多くの選択肢の中から、ある指標（価値）を最も良くする変数の値（組合せ）を求めることです。以下では、身近な組合せ最適化問題として分かりやすい2つの例について説明します。その後、IoT社会における組合せ最適化処理の高速解法の重要性について述べます。
菓子選択問題
組合せ最適化問題を解くことは、日常生活の様々な場面で皆さんも経験しています。例えば、子供の時の遠足の菓子選び（菓子選択問題）を思い出してみましょう。
この場合、変数・制約・価値は下記で与えられます。
- 変数：どの菓子を選ぶのか？
- 制約：遠足で決められた総額
- 指標（価値）：子供の満足度
| アイテム | 変数 | 値段 | 満足度 |
|---|---|---|---|
| チョコレート | $x_1$ | 120円 | 10点 |
| キャンディ | $x_2$ | 30円 | 3点 |
| クッキー | $x_3$ | 90円 | 4点 |
| ポテチ | $x_4$ | 150円 | 8点 |
| グミ | $x_5$ | 120円 | 7点 |
ここでそれぞれのお菓子は2個以上買わないものとします。見通しを良くするために、変数$x_1, x_2,⋯x_5∈ {0, 1},$ 0: 選択しない、1:選択するを導入して菓子選択問題を数式で表現してみましょう。この時、最大化したい価値（満足度）と制約（決められた総額は）以下で与えられます。
- 価値：$10x_1 + 3x_2 + 4x_3 + 8x_4 + 7x_5$
- 制約：$120x_1 + 30x_2 + 90x_3 + 150x_4 + 120x_5\leq300$
この制約を満足しつつ、価値を最大化する菓子の組合せが求めたい答えとなります。
- 答え：チョコレート、キャンディ、ポテチ（満足度21点、総額300円）
ここで挙げた例は菓子の種類は5種類であり非常に単純な例でしたが、様々な応用が考えられる問題であると言えます。実際このような問題は実社会の様々なシーンで現れます。例えば、各案件の必要経費と期待利益が与えられたとき、決められた予算（制約）で期待利益（価値）を最大化する、案件の組合せを求める問題（投資先選択問題）等が挙げられます。
巡回セールスマン問題
組合せ最適化問題の別の例として、巡回セールスマン問題（配送経路問題）を考えてみましょう。
この問題は、都市間の距離のリストが与えられた際に、セールスマンが複数の都市をどのように訪問すれば、最短の移動経路（最適経路）で済むかを求める問題となります。ただしそれぞれの都市には一度ずつしか訪問しないとします。都市数が少なければすべて全ての解候補をしらみつぶしに調べることが可能です。しかし、都市数が例えば30都市に増えると、候補数が爆発的に増加し、その組合せの数は10の30乗という驚異的な値となります。この場合、全ての解候補を網羅的にリスト化して最適経路を求めるには、スーパーコンピュータを用いたとしても1,400万年という天文学的な時間が必要となってしまいます。このように、組合せ最適化問題はパラメータが増えると、厳密解を得ることが途端に解くのが難しくなる特徴があります。
| 経路の候補 | 移動距離 | |
|---|---|---|
| 経路1 | ABCDE(A) | 22 |
| 経路2 | ABCED(A) | 24 |
| 経路3 | ABDCE(A) | 20 (最短経路) |
| ABDEC(A) | 26 | |
| ABECD(A) | 22 | |
| ABEDC(A) | 26 | |
| 経路M | ACBDE(A) | 25 |
| ACBED(A) | 27 |
IoT社会と組合せ最適化処理の関係
実世界とサイバー空間が相互連携したIoT社会においては、人とインターネット空間の接点はパソコンやスマートフォンといったエッジ端末に留まらず、車や家といった生活空間や工場・オフィスなどに遍く広がっていきます。
そしてIoT社会においては、大量のセンサーで収集された膨大なデータを解析し、それに基づいて実世界や各種システムを最適制御することを目指しています。それにより、我々の生活がより豊かになり、少子高齢化やエネルギー問題といった私たちが抱える社会的な課題も解決すると期待されています。すなわち、製造（Industry 4.0）、物流、小売、金融（Fintech）、交通、社会インフラ、医療、農業、ヘルスケア等の広範な産業分野において、技術革新や新たな雇用創出が行われ、産業・経済構造が劇的に変革すると考えられています。
このようなIoT社会においては、与えられた制約条件の下で、膨大な組合せの中から（準）最適解を高速かつ高精度に探索し、それに基づいて各種機器、インフラ、工場、都市などのIoTシステムを最適制御することが必須となっています。
例えば、物流システムの場合、すべての配送先を訪れるという制約条件の下で、配送コストを最小とする配送経路を求める必要があります。また人工知能における機械学習アルゴリズム（深層学習等）においては、最適化処理を学習過程において行う必要があります。
このように、IoT社会を活用した新たな価値・サービスを実現するには、組合せ最適化問題を高効率で処理する技術がキーとなると考えられています。
一方で複雑で大規模化する社会システムに内在する組合せ最適化問題に対して、従来のノイマン型計算機を前提とした手法を適用することは組合せ最適化問題の特徴から計算量が爆発し、計算効率及びエネルギー効率の観点から困難と考えられます。
実際、IoTが世の中に遍く浸透する2030年においては、データ量は現在の100倍以上となると予測されています。このように爆発的に増え続けるビッグデータを高速かつ低消費電力で処理し、最適システム制御を行うためには、計算機ハードウェアの抜本的かつ非連続的革新が必要となっています。
次のステップ
COVID-19感染対策を考慮し研究員シフトを最適化する
COVID-19の流行に伴い、感染リスクを考慮した制約条件の下、研究員のシフト作成をアニーリングマシンで行うユースケースを紹介しています。
保険会社の再保険ポートフォリオを最適化する
自然災害リスクに対応するため、保険会社が保有する膨大なデータを活用した再保険ポートフォリオ策定をアニーリングマシンで行うユースケースを紹介しています。
易しく学ぶ最適化フロー
初級者向けに、アニーリングマシンで最適化問題を解く工程を、「課題整理と要件定義」「定式化」「入力データ作成」「アニーリングマシン実行」の４段階に分けて手順やポイントを解説します。
アニーリングマシンのための数学
アニーリングマシンが得意とする問題の特徴である「二次」「離散」を中心に、知っておくべき数学的前提を易しく解説します。