第1章 組合せ最適化問題とは

第1節 最適化問題と組合せ最適化問題

アニーリングマシンが得意としているのは組合せ最適化問題です。ちなみに、「組合せ最適化問題」という表記が学術上は浸透していて正しいのですが、学会から離れてもっと公的なメディアなどで報道される場合には「組み合わせ最適化問題」という表記に修正されることもあります。私どもは研究開発者として、「組合せ最適化問題」と表記します。

アニーリングマシンを使う上で最も大切なのは、現実の課題から式を立てることなので、このサイトへ訪れてくださった皆さんにはぜひ、扱う問題の特徴について少しずつ知識を深めて頂きたいと思います。まず、組合せ最適化問題とは、「最適化問題」のなかの一つの分類であることをぜひ知って頂きたいと思います。「最適化問題」とは、何かをよくする答えを探す取り組みのことです。決められた予算の中でできるだけ満足度の高いお菓子を選ぶという菓子選択問題、飲食店が仕入れた材料を使って何種類かのメニューを販売したときに、期待できる最も高い金額を売り上げる場合のメニューごとの販売目標を求めるのも最適化問題です。株取引などでは、持つ株の組合せによって、一方の株価が下がってももう一方の株価は上がるというパターンが存在しており、リスクを回避して収益を上げるためにそのような相互作用のある組合せ(ポートフォリオ)を選んで取引を行います。この組合せを考えるのも、最適化問題です。ある職場のシフトを組むのに、希望が満たされずに不満を持つ人が1人も出ず、業務上でもよい成果が出るようなシフトを組むのも最適化問題です。さらには、親子丼を作る際、生すぎず固まりすぎず、ちょうどよい好みのところで仕上げるための温度と加熱時間を決めることも、最適化問題です。

  1. 菓子選択問題
  2. 飲食店の利益最大化問題
  3. ポートフォリオ問題
  4. シフト作成問題
  5. 親子丼問題

以上の通り列記しましたが、この中にはアニーリングマシンが得意な問題とそうでない問題が混在しています。その説明は少し込み入った話題になるのでもう少し後にするとして、まずはこのような最適化問題を数学で解くために必要な、定式化について説明します。