元はLinkedIn 向けに書いた記事を日本語化したもの。クライアントとの守秘義務のため内容は匿名化してある。

最適化プロジェクトには必ず、ピカピカの新しいツールと地味な旧来のツールがぶつかり合う瞬間があり、たいてい地味な方が2桁から3桁のオーダーで勝つ。本稿は、そうした瞬間のひとつと、それがなぜ起きたのかについての話である。

背景

あるティア1メーカーのリターナブルコンテナ（再利用可能なパレット・コンテナ）物流ネットワークの最適化を支援していた。海外の複数工場と国内倉庫からなるマルチサイトのネットワークにおいて、各拠点が遊休コンテナへ過剰投資することなく十分な在庫を維持できるよう、週次で「パレット・コンテナを何個、出荷・保管・新規調達すべきか」を決める案件である。典型的な在庫・輸送コスト最小化問題であり、何らかの形でほぼすべての実物のサプライチェーンに現れる種類の問題だ。

多数の拠点と期間にわたる離散量を扱う問題であるため、量子インスパイアード・コンピューティングが真価を発揮するはずの、大規模で厄介な組合せ最適化問題だと思い込みたくなる。今回は、東芝の量子インスパイアード最先端ソルバーであるシミュレーテッド分岐マシン（SQBM+）と、従来型のオープンソース整数線形計画法（ILP）ソルバーである HiGHS の両方を利用できる環境にあった。そこで、ごく自然な流れとして次の検証を行った——同じ問題を両方の方式で定式化し、規模を徐々に大きくしながら、どちらが勝つかを見たのである。

試したこと

ILPのベースラインはシンプルだった。非負整数の決定変数に対し、安全在庫・積載上限・コンテナ容量・累積返却上限といったいくつかの線形制約のもとで、線形コスト関数（コンテナ・輸送コストに新規調達コストを加えたもの）を最小化する。HiGHS は、変数の数が数千のオーダーまで増えても、ミリ秒〜秒のオーダーで証明付きの最適解に到達した。

量子インスパイアード側では、同じ問題を QUBO（Quadratic Unconstrained Binary Optimization — すべての決定を0/1変数として表現し、目的関数全体を一つの二次形式にまとめる定式化）として、その後 SQBM+ 向けのネイティブな二次計画問題（QP）として再定式化した——最初は「レガシー」定式化で、続いてソルバーの強みを活かすよう作り直したネイティブ二値（バイナリ）定式化で。これらすべてを、小規模なパイロット事例から本番規模に近いベンチマークまで、複数のスケールでベンチマークした。

結果

検証したすべてのスケールで ILP の解の方が安価であり、しかも量子インスパイアード側の「最善ケース」は、問題が大きくなるにつれて悪化し続けた。

小規模なパイロット規模では、SQBM+ の QUBO 定式化は設定次第で ILP 最適値のおよそ2倍〜160倍のコストに落ち着いた——この幅が広いのは、この段階ではまだ調整が甘い初期の定式化と、より練り込んだ定式化を混ぜて検証していたためである。
中規模のベンチマークでは、定式化を絞り込んだ上で、我々が作り込める最良の QP 定式化でも ILP 最適値のおよそ64倍〜77倍だった。
検証した中で本番に最も近い規模では、最善ケースでもそのギャップはおよそ2,700倍のオーダーまで開いた。

つまり注目すべきは上限ではなく下限の推移だ。2倍 → 64倍 → 2,700倍と、単調に悪化している。(省略せず併記しておきたい一点として: 初期段階の自社ログには「最適値の7倍〜39倍」というより小さい数値も残っているが、後年の監査で特定のスケールや実行結果まで完全には遡れなかった——より粗い、あるいはより初期・より小規模な計測を反映している可能性がある。方向性を変えるものではなく、あくまで我々自身の記録管理上のギャップである。)

なぜそうなったのか

そもそもこの問題は、量子インスパイアードの組合せ最適化ソルバーに向いていなかった。それはベンダー自身のドキュメントにも明記されている。東芝は、SQBM+ は「LP/MILP では古典ソルバーに勝てない」こと、非凸な二次二値問題（MAX-CUT、最大独立集合など）で最も性能を発揮すること、そして「等式制約が多い場合はSQBM+よりSA（シミュレーテッド・アニーリング、SQBM+とは別の量子インスパイアード発見的手法）の方が優れている」ことを明言している。我々の問題は、これらの注意書きすべてに同時に当てはまっていた。

なお、SA自体は本検証では試していない。ただし構造的に見れば、SAもSQBM+と同じQUBOエンコーディング（対角Q行列・二次ペナルティによる制約表現）上を探索するヒューリスティックであるため、同様のエンコーディング・オーバーヘッドを免れない可能性が高い——これはあくまで構造的な推測であり、実測による裏付けではない。

構造的に見ると、線形コスト関数は QUBO/QP形式では対角な Q 行列に対応する——各変数の目的関数への寄与が、他のすべての変数から独立しているということだ。シミュレーテッド分岐の強みは、まさに結合した非対角の相互作用を利用して、広大な探索空間を効率的に探索する点にある。結合すべき相手がなければ、そのメカニズムは何のアドバンテージも発揮できない。

さらに悪いことに、整数をビット列として、ハードな線形制約を二次ペナルティ項としてエンコードすることは純粋なオーバーヘッドを追加する。最大の定式化では、約220個の整数変数が約2,000量子ビットに展開され、ペナルティ係数は実際のコスト信号のおよそ10億倍のスケールにまで達した。つまり、ソルバーの探索は実質的に「コストを最小化する」ではなく「ペナルティに違反しない」ことに支配されていたのである。

一方この問題の、ネットワークフローに近いタイトなLP緩和——整数制約を外した連続緩和の時点で、すでに整数最適解にきわめて近いということ——は、まさに分枝限定法がほぼ瞬時に、ほとんど探索することなく解を絞り込めるように作られた形そのものだった。

正直に述べておくべき例外がひとつある。複数拠点向け混載出荷の課金拡張案では、真にバイリニア（双線形）な項（2つの二値決定の積）が生じる。これは ILP では多数の線形化用補助制約を経由してしか扱えないが、SQBM+ はネイティブに扱える。これは本プロジェクトの中で、量子インスパイアード・ソルバーに構造的に本当の分があった唯一の箇所である——ただし、これは狭く限定的なケースであり、これまでの結論を覆すものではない。

まとめ

量子・量子インスパイアードのソルバーに手を伸ばす前に、目的関数と制約の構造が実際どうなっているかを問うべきだ。

目的関数が線形で、LP緩和がタイトで、整数に対する等式・不等式制約が中心——それはILPの領域であり、現代的なオープンソースMIPソルバーは、規模が大きくなるほどますます大差をつけてQUBO/QPアプローチに勝つ可能性が高い。二次で非凸、変数間の結合が豊かな、真に組合せ的な目的関数——MAX-CUT型の問題——こそ、量子インスパイアード手法がその真価を発揮できる領域である。

重要なのは「どちらのソルバーが新しいか」ではなく、まず最強の古典的厳密解法をベースラインにベンチマークし、流行ではなく問題構造にアーキテクチャを決めさせることだ。

サプライチェーンやスケジューリングの問題に量子・量子インスパイアード最適化の適用を検討している方がいれば、ぜひ知見を交換したい——定式化にエンジニアリング時間を投じる前に、どのような構造適合性チェックを行っているか、ぜひ聞かせてほしい。