Snowflake と数理最適化の相性について

1. はじめに

クラウドデータウェアハウス（DWH）である Snowflake は，大規模データの処理とスケーラビリティの面で優れた特徴を持っている．一方で，数理最適化 は，組合せ爆発を伴う計算問題を解くためのアプローチとして多くの分野で活用されている．

現実問題で数理最適化を活用する場合，（近似）最適化のみを出力することが多いが，現場では性質の異なる解についても見たいという声が上がることが多々ある．このような場合に対応するには，探索過程の解を保持する必要があるが，探索アルゴリズム※によっては，その解の容量が大きくなることがある．そこで，大容量のデータを保存可能なことと，大量のデータへのアクセスが高速なSnowflake を活用することを考えた．
※数理最適化のアルゴリズムは，計算量と計算過程のメモリ量が課題になることが多い

本記事では，代表的な組合せ最適化問題である 巡回セールスマン問題（TSP） を例に取り，Snowflake と数理最適化の相性について考察する．

2. 巡回セールスマン問題（TSP）の計算負荷

TSP とは，複数の訪問地点を最適な順番で回るルートを求める問題である．訪問地点の数を n とすると，訪問地点間の移動時間が非対称であるとき，

$$(n-1)! \text{ 通りのルートが存在}$$

となり，地点数が増えると計算量が指数関数的に増加する．

例えば，全探索を行う場合の経路数は次のようになります。

訪問地点数	経路総数 (n-1)!
10	362,880
20	約1.2×10¹⁷
30	約8.8×10³⁰
40	約2.2×10⁴⁶
50	約6.1×10⁶²

このように，20地点以上では全探索が現実的でなくなるため，数理最適化手法を活用する必要がある．

3. Snowflake で TSP を扱う際の工夫

TSP の解探索では，膨大なデータの管理が必要である．Snowflake の スケーラブルなストレージと並列処理機能 を活用することで，最適解の探索やデータ管理を効率化できる．

(1) 全探索の結果をすべて保存する場合

全探索で得られるすべての解を保存すると，必要なストレージ容量は 48バイト/解（訪問順40バイト + コスト8バイト）と仮定しても，

$$(n-1)! \times 48 \text{ バイト}$$

となり，地点数が増えると以下のように 天文学的なデータ量 になる．

訪問地点数	必要ストレージ容量
10	約17.4MB
20	約5.8EB
30	約4.2×10¹⁶EB
40	約1.1×10³²EB
50	約3.0×10⁴⁸EB

この方法では，20地点以上で保存が現実的でなくなる ため，次の方法を検討する．

(2) 最適解の更新時のみ記録する方法

全探索の過程で 最短経路が更新されたときのみ記録 することで，データ量を大幅に削減できる．

更新回数は経験則的に (n-1) log(n-1) 程度と見積もられるため，

訪問地点数	更新回数	必要ストレージ容量
10	21	1.0 KB
20	52	2.5 KB
50	201	9.8 KB
100	613	28.7 KB
500	4,494	215 KB
1000	9,073	435 KB

この方法では，数千地点でも1MB未満のストレージで管理可能 になる．

例

以下は，Streamlit in Snowflake（SiS）にて，訪問地点が10か所の巡回セールスマン問題を全探索法にて解き，更新時の解を保持した例となる．

4. Snowflake を活用した計算の並列化

Snowflake の 並列処理とスケーラブルな計算機能 を活かせば，TSP のような計算負荷の高い処理も効率的に実行できる．

(1) クエリ並列処理の活用

Snowflake では ウェアハウスのスケールアップ/スケールアウト により並列クエリ実行が可能である．

スケールアップ → コンピュートリソースを増やして 1 クエリの処理を高速化
スケールアウト → クエリを複数のノードで並列実行

例えば，TSP の部分探索を 複数の Snowflake ノードで並列実行 することで，探索時間を短縮できる．

(2) Snowflake の UDF / ストアドプロシージャの活用

UDF（ユーザー定義関数） を活用し、TSP の評価関数を SQL 内で計算
Python ストアドプロシージャ を利用し、Snowflake 内で動的にルート探索

CREATE FUNCTION tsp_distance(route ARRAY) RETURNS FLOAT
AS $$
  -- ここでルートの総距離を計算するロジックを実装
$$;

(3) Snowflake のタスクを活用した定期実行

定期的に新しいデータをもとに最適ルートを再計算する場合，Snowflake の タスク機能 を活用すると自動化できる．

CREATE TASK tsp_optimization
  WAREHOUSE = my_warehouse
  SCHEDULE = '1 HOUR'
AS
  CALL calculate_optimal_route();

5. まとめ

数理最適化のアルゴリズムにおける，計算量と計算過程のメモリ量の課題に対して，Snowflake の活用は有用であると考えられる．

TSP の全探索は地点数が増えると現実的でない
最適解の更新時のみ記録することでデータ量を削減可能
Snowflake の並列処理や UDF を活用すれば、計算の高速化が可能

今後の課題として，

Snowflake の機械学習機能（Snowpark）を活用した数理最適化の実装
物流や経路最適化などの実業務への応用

などが挙げられる．