潜在最適化

潜在最適化は、Lokadによって開拓された最適化パラダイムであり、困難で複雑な組み合わせ問題を対象としています。また、不確実性が存在する場合に発生する確率的問題も扱います。潜在最適化は、予定されたリソースの割り当てなどの課題に対する画期的な解決策です。従来のソルバーが解の空間で動作するのに対し、潜在最適化は「戦略」の空間で動作します。このアプローチにより、状況が変化するにつれて迅速な再最適化が可能となります。

テクノロジー概要

2024年に導入された潜在最適化は、Lokadが開発した汎用最適化技術の第2世代です。確率的離散降下で対処されるよりも難しい組み合わせ問題に取り組みますが、ややスケーラビリティが低下しています。

概念的には、Lokadのサプライチェーンサイエンティストは、以下の手順を含むデータ処理パイプラインを設計します：

過去のデータを準備する。
確率的予測を生成する。
頑健な意思決定戦略を作成する。
最後の瞬間に、変更された条件の下で再最適化する。

過去のデータは、Envisionの一般的なデータエンジニアリング機能を使用して準備されます。EnvisionはLokadのドメイン固有の言語です。確率的予測は、差分可能プログラミングを使用して生成され、確率モデリングに最適なパラダイムであり、Envisionでは第一級の市民として扱われます。

次に、潜在最適化を使用して意思決定戦略を生成します。基本的に、潜在最適化の結果は、特定の問題に狭く適合した専門ソルバーです。最後に、この戦略は、最終的にわずかに変化する条件の下で実行され、必要な意思決定を行うために再実行される可能性があります。戦略が迅速に実行されるため、ループ内の人々によって対話的に使用することができます。

これらの4つのステップ（1）、（2）、（3）、および（4）は、すべてEnvision内で実行されます。

伝統的なソルバーの限界

数学的最適化は、コンピュータサイエンスの成熟した分野です。市場には、プロプライエタリおよびオープンソースのさまざまなソルバーが利用可能です。残念ながら、これらの既存の技術のいずれも、特に厳しいスケジューリング問題に取り組む際には要件を満たしていません。

分枝限定法アルゴリズム（およびそのすべての変種）は、実行可能領域をより小さなサブ問題に分割（分岐）し、リラクゼーション（バウンディング）を使用して探索空間の大部分を刈り取ることに依存しています。このアプローチは、サプライチェーン問題には適していません。解の空間は厳密に制約されていますが、それでも膨大です。制約を満たすだけでは、良い解を生成するには十分ではなく、これは分割の核心的な前提を崩します。

局所探索アルゴリズム（およびそのすべての変種）は、現在の1つまたは複数の解を反復し、近くの変種を調べることに焦点を当てています。残念ながら、この方法もうまく機能しません。なぜなら、これらの問題では「局所性」という概念が十分に定義されていないからです。これらのシナリオが非常に厳密に制約されていることを考えると、解に対するほとんどの局所的な調整が多くの制約を犯すため、検索プロセスが改善された解を回復することができません。

Lokadでは、困難な組み合わせ問題に数百万の変数のスケーラビリティ目標を設定し、条件が変化した場合でも数秒以内に再最適化できる能力を持つことを目指しています。たとえそれらの変更が連鎖的な影響を通じて元の解を完全に無効にする場合でも。

裏側で

Lokadは、組み合わせ最適化に対して伝統的でないアプローチを採用しています。標準的なソルバーを提供するのではなく、潜在最適化と呼ばれる専門的なプログラミングパラダイムを使用して問題に取り組んでいます。この方法は、サプライチェーンサイエンティストの洞察と専門知識を統合するために重要です。

潜在最適化は、元の問題の代替表現を導入します。この代替表現は、その場の問題に適したシンプルなソルバーの高次元のパラメータ化です。これらのパラメータは、元の問題に対してパラメータ化されたソルバーを反復的に適用することによって「学習」されます（これには確率的な変種が含まれる場合があります）。潜在最適化の核心には、「学習」プロセスがあります。

潜在最適化の出力は、元の問題だけでなくその変種にも高品質な解を生成する、適切にパラメータ化されたシンプルなソルバーです。

例：航空機生産現場のスケジューリング

航空機メーカーとその生産現場を考えてみましょう。この現場は重要な航空機部品を組み立てています。全体の目標は、利用可能なリソース（人員と産業資産）を考慮して、現場のスループットを最大化することです。

この組み立てプロセスには約100の異なる操作が関与しています。これらの操作を実行するための約20の利用可能なスロットもあり、各スロットには異なる属性があります。特定の操作は特定のスロットでのみ実行できます。複雑な依存関係グラフが操作をつないでいますが、自動車生産ラインとは異なり、このグラフは直線的なシーケンスを形成しません。タスクの最終的な順序にはかなりの柔軟性があります。

さらに、一部の操作には、現場に限られた数の機器が必要です。多くの操作は、必要な在庫が手元にあることに依存しています。時には重要な部品が遅れることがあります。完了を加速するために同時に作業できる人数が異なる操作もあり、1人から最大5人までです。

約100人の技術者からなる労働力が、20〜30人のシフトで現場を運営しています。各技術者は、各操作に対して3つの資格レベルのうちの1つを持っています。最高レベルでは、技術者は操作を実行し、他の人が行った作業を検証できます。中間レベルでは、技術者は自分の作業を実行し、自己検証できます。最低レベルでは、技術者は操作を実行できますが、最高資格を持つ同僚による検証が必要です。

生産現場の管理者は、数週間先の分単位のジョブスケジュールを作成し、各コンポーネントごとにどの技術者がどの操作に従事するかを正確に指定することを望んでいます（各コンポーネントはシリアル番号で個別に識別されます）。この詳細レベルは、スケジュールの信頼性を確保するために不可欠です。

ただし、条件は各シフトの開始時に変化する可能性があります。従業員が病気で欠勤するか、部品が遅れて利用できなくなるかもしれません。これらの問題がすぐに対処されないと、効率の悪化の連鎖にすぐにつながり、技術者や資産が問題が解決される間にアイドル状態になります。

潜在最適化を使用すると、現場管理者は、数週間先の数万のタスクを含む詳細なジョブスケジュールを作成できます。また、予期せぬ変更に対応するために、ツールを最後の瞬間に再実行することもできます。さらに、新しく生成されたソリューションは、元の計画の大規模なランダムな再配置ではなく、初期バージョンに密接に似ているスケジュールであり、最新の状況に対応するためにわずかな調整しか必要としません。