潜在最適化

潜在最適化は、Lokadが先駆けた最適化パラダイムであり、困難で複雑な組み合わせ最適化問題を対象としています。また、不確実性が存在する場合に発生する確率的問題も扱います。潜在最適化は、スケジュールされたリソース配分といった課題において画期的な技術です。従来のソルバーが解空間で動作するのに対し、潜在最適化は_戦略_空間で動作します。このアプローチにより、状況の変化に応じた迅速な再最適化が可能となります.

技術概要

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

概念的には、Lokadのサプライチェーン・サイエンティストは、次のステップを含むデータ処理パイプラインを設計します:

過去のデータを準備する.
確率的予測を生成する.
堅牢な意思決定戦略を作成する.
条件が変化した直前に再最適化する.

過去のデータは、Envisionの汎用データエンジニアリング機能を用いて準備されます。Envisionは、Lokadのドメイン固有言語です。その後、確率的予測は微分可能プログラミングを使用して生成され、これは確率モデリングに理想的なパラダイムとしてEnvision内で一級市民の扱いを受けています.

次に、潜在最適化を利用して意思決定戦略を生成します。実質的に、潜在最適化の成果は、特定の問題に合わせて狭く調整された専用のソルバーです。最後に、この戦略は最終的な、やや変動する条件下で実行（場合によっては再実行）され、必要な決定が導かれます。戦略が高速に動作するため、関与する人々による対話的な利用が可能です.

(1)、(2)、(3)、(4) の全てのステップは、Envision内で実行されます.

従来のソルバーの限界

数学的最適化は、コンピュータサイエンスの成熟した分野です。独自ソルバーもオープンソースソルバーも市場に数多く存在します。しかし、特に厳しいスケジューリング問題において、これらの既存技術は我々の要求を満たしません.

ブランチ・アンド・バウンドアルゴリズム（およびその全ての変種）は、実行可能領域をより小さな部分問題に分割（ブランチング）し、緩和手法（バウンディング）を用いて探索空間の大部分を剪定することに依存しています。しかし、このアプローチはサプライチェーン問題にはうまく機能しません。解空間は厳しく制約されているものの、依然として膨大であり、単に制約を満たすだけでは良い解を得るには不十分で、分割の基本前提を損ないます.

局所探索アルゴリズム（およびその全ての変種）は、1つまたは複数の現在の解を反復的に検証し、近傍の変種を調査することに基づいています。しかし、この手法も、「局所性」という概念がこれらの問題では明確でないため、うまく機能しません。これらのシナリオが厳しく制約されているため、ほとんどの局所的な調整は多くの制約に違反し、探索プロセスがより良い解を見出すことができなくなります.

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

内部の仕組み

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

潜在最適化は、元の問題の代替表現を導入します。この代替表現は、対象の問題に合わせて調整されたシンプルなソルバーの高次元パラメータ化です。これらのパラメータは、パラメータ化されたソルバーを元の問題（多くの場合、確率的な変種を含む）に対して反復的に適用することにより_学習_されます。根本的に、潜在最適化は_学習_プロセスです.

潜在最適化の成果は、元の問題およびその変種に対して高品質な解を生成する、十分にパラメータ化されたシンプルなソルバーです.

例: 航空生産サイトのスケジューリング

ある航空機メーカーとその生産拠点の一つを考えてみましょう。この拠点では、重要な航空機部品が組み立てられています。全体の目標は、利用可能な資源（人員および工業資産）を前提として拠点のスループットを最大化することです.

この組み立てプロセスには約100種類の異なる作業が含まれています。また、これらの作業を実施するためには約20の利用可能なスロットがあり、それぞれ異なる属性を持っています。特定の作業は特定のスロットでのみ実施可能です。作業同士は複雑な依存関係のグラフで結ばれていますが、自動車生産ラインのような直線的な並びにはならず、最終的な作業順序にはかなりの柔軟性があります.

さらに、いくつかの作業は、拠点に限られた数量しか存在しない特定の装置を必要とします。多くの作業は、必要な在庫が確保されていることに依存しており、時には重要な部品が遅延することもあります。作業ごとに、同時に作業に参加できる人数が異なり、1人から最大5人までが一斉に作業することがあります.

約100名の技術者が、20～30名のシフトで拠点を運営しています。各技術者はそれぞれの作業について3段階の資格レベルを持っており、最上位のレベルでは他者の作業の検証も可能です。中間レベルでは自身の作業の実施と自己検証が可能であり、最下位のレベルでは作業の実施は可能ですが、最上位の資格を持つ同僚による検証が必要です.

生産拠点の管理者は、今後数週間にわたる1分ごとの詳細な作業スケジュールを求めており、各部品についてどの技術者がどの作業を担当するか（各部品はシリアル番号で個別に識別される）を正確に指定する必要があります。このレベルの詳細は、スケジュールの信頼性を確保するために不可欠です.

しかし、各シフトの開始時には状況が変化する可能性があります。従業員が病気で欠勤したり、部品が遅延して利用できなくなったりすることもあります。これらの問題が迅速に対処されない場合、連鎖的に非効率が発生し、技術者や資産が待機状態になる恐れがあります.

潜在最適化を用いることで、生産拠点の管理者は、今後数週間にわたる数万件に及ぶ詳細な作業スケジュールを作成することができます。また、予期せぬ変更に対応するため、最後の瞬間にツールを再実行することも可能です。さらに、新たに生成された解は元の計画の大規模な無作為再編成ではなく、初期バージョンに非常に近いスケジュールであり、最新の状況に合わせたわずかな調整のみで済みます.