組合せ最適化問題とは
組合せ最適化問題とは、様々な制約の下で多くの選択肢の中から、ある指標（価値）を最も良くする変数の値（組合せ）を求めることです。以下では、身近な組合せ最適化問題として分かりやすい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 |
問題に応じたさまざまな解法が提案されている
一口に組合せ最適化問題と言っても、菓子選択問題と巡回セールスマンでは解く方法が随分変わってきます。菓子選択問題の解き方は、前述の通り中学生までに習うような数式で表すことができ、この式に従って解く場合は表計算ソフトのソルバを使うことができます。もしくは、学校で習ったようにグラフを書いて求めることができます。一方、巡回セールスマン問題の場合は、30都市の組合せを一通り調べるやり方では効率よく厳密解を得ることができないことがわかっています。このような場合にヒューリスティックと呼ばれる解法を用いることが研究されてきました。更に、ある条件を持つ組合せ最適化問題ではアニーリングマシンを使って効率的に解くことが可能であることがわかってきており、アニーリングマシンではどのような問題に適用すれば、効率的に社会課題を解決できるのか、またアニーリングマシンを効果的に用いる方法がないか、多角的な視点から実用に向けた研究が進められています。
関連リンク
社会課題解決と組合せ最適化処理の関係
組合せ最適化問題を高速に解くための専用ハードウェアがこの数年立て続けに登場し、研究が進められています。アニーリングマシンは、組合せ最適化処理という特定用途のために開発が進められているコンピュータです。その理論の元となっているシミュレーティドアニーリング法が最初に提案され、40年ほどが経ちました。今、実際にアニーリングマシンの専用ハードウェアを使って私達の身近な情報処理に応用されているケースはまだ限られていますが、生活に身近な産業や経済活動に導入され、拡がっていく段階に入っています。
その背景には、様々な外的要因、すなわち社会課題の深刻化も顕在化していることが挙げられます。例えば、物流の増加に対し、ドライバー不足とCＯ2削減が課題となっており、物流業務や運搬経路の最適化処理が喫緊の課題となっています。
一方で、これまでは汎用のコンピュータを用いてソフトウェアでヒューリスティックな解き方などを実装して組合せ最適化処理を行ってきましたが、増大する社会課題の解決には性能に限界が見えてきました。よって、その限界を突破する新しいハードウェア、つまり、アニーリングマシンの研究開発が本格的になっています。
アニーリングマシンの研究開発の進展に伴い、産業を担う事業者側が革新的なサービスを検討し始めています。例えば、アニーリングマシンによって再保険のポートフォリオをシミュレートし、災害リスクの変化に耐えうる社会基盤を準備するなどのことが可能となっています。
アニーリングマシンが社会課題の解決のための強力なツールとして成熟するには、使う側（Business）と作る側（Engineer）のステークホルダーが協力しあい、創造的で、挑戦的な取り組みを加速する必要があります。
様々な可能性を秘めたアニーリングマシンをAnnealing Cloud Webで学び、体験を重ね、あなたもぜひ組合せ最適化の威力を発見してください!
関連リンク
ACWスキルロードマップ
この記事はACWスキルロードマップの一部です。スキルロードマップを使ってACWを学んでみてください。
SNS共有
記事が役に立ちましたか？他の人に共有してみてください。
次のステップ
COVID-19感染対策を考慮し研究員シフトを最適化する
COVID-19の流行に伴い、感染リスクを考慮した制約条件の下、研究員のシフト作成をアニーリングマシンで行うユースケースを紹介しています。
保険会社の再保険ポートフォリオを最適化する
自然災害リスクに対応するため、保険会社が保有する膨大なデータを活用した再保険ポートフォリオ策定をアニーリングマシンで行うユースケースを紹介しています。
易しく学ぶ最適化フロー
初級者向けに、アニーリングマシンで最適化問題を解く工程を、「課題整理と要件定義」「定式化」「入力データ作成」「アニーリングマシン実行」の４段階に分けて手順やポイントを解説します。
アニーリングマシンのための数学
アニーリングマシンが得意とする問題の特徴である「二次」「離散」を中心に、知っておくべき数学的前提を易しく解説します。