Toshiba SQBM+ TSP Solver を使って巡回セールスマン問題を解いてみる

2023年6月26日

はじめに

東芝デジタルソリューションズ株式会社が提供しているシミュレーテッド分岐マシン)は、それを核とする量子インスパイアード最適化ソリューション「SQBM+」と名前を改めて現在は提供されています。これから２回に分けて、この新しい SQBM+ の機能に触れてみたいと思います。

TSP ソルバー

今回は、SQBM+ で提供される巡回セールスマン問題(TSP)専用のソルバーを使ってみたいと思います。

以前、こちらの記事にてSBM を用いて巡回セールスマン問題を解くという内容の実験を行い、
その中で TSPLIB というデータセットを紹介しました。今回もこちらのデータセットを使用します。

まずは14都市のインスタンス burma14 で実験してみます。

NAME: burma14
TYPE: TSP
COMMENT: 14-Staedte in Burma (Zaw Win)
DIMENSION: 14
EDGE_WEIGHT_TYPE: GEO
EDGE_WEIGHT_FORMAT: FUNCTION
DISPLAY_DATA_TYPE: COORD_DISPLAY
NODE_COORD_SECTION
1 16.47 96.10
2 16.47 94.44
3 20.09 92.54
4 22.39 93.37
5 25.23 97.24
6 22.00 96.05
7 20.47 97.02
8 17.20 96.29
9 16.30 97.38
10 14.05 98.12
11 16.53 97.38
12 21.52 95.59
13 19.41 97.13
14 20.09 94.55
EOF

以前の記事では QUBO 形式の入力を扱うソルバーを用いたため、 QUBO 定式化を行う必要がありました。今回利用する TSP ソルバーの API は、上述の TSPLIB のフォーマットを入力とする方式のため、QUBO 定式化の手順無しに問題を解くことができます。

問題データを curl コマンドで送信し、計算結果を取得してみます。

$ curl -i -H "Content-Type: application/octet-stream" -X POST "http://SQBM+_engine_server:8000/solver/tsp" --data-binary "@burma14.tsp"

HTTP/1.1 200 OK
X-Calculation-Time: 0.011
X-ID: r1791999202
Content-Type: application/json; charset=utf-8
Content-Length: 148
ETag: W/"94-jgowsbIFXwo5iU1fKQ+HVF5gSH0"
Date: Thu, 24 Nov 2022 05:57:48 GMT
Connection: keep-alive
Keep-Alive: timeout=5

{
    "id": "r1791999202",
    "time": 0.011,
    "wait": 0,
    "message": "finished",
    "runs": 160,
    "value": 3323,
    "result": [1,10,9,11,8,13,7,12,6,5,4,3,14,2],
    "NAME": "burma14"
}

結果が得られました。

"value":3323 が評価値、つまり解の経路長を表します。burma14 の既知最良解 3323 に到達したことがわかります。

次に、大規模問題として、299都市のインスタンス pr299 をやってみます。
この問題を QUBO として定式化を行うと約10万変数の問題となり、 QUBO を入力とする現行のイジングマシンで実行可能な最大規模クラスの TSP インスタンスとなることが知られています。

$ curl -i -H "Content-Type: application/octet-stream" -X POST "http://SQBM+_engine_server:8000/solver/tsp" --data-binary "@pr299.tsp"
HTTP/1.1 200 OK
X-Calculation-Time: 0.02
X-ID: r3649234124
Content-Type: application/json; charset=utf-8
Content-Length: 1201
ETag: W/"4b1-W7J8GvHKUvPvbMNOYqnmKLPu4AM"
Date: Thu, 24 Nov 2022 05:59:21 GMT
Connection: keep-alive
Keep-Alive: timeout=5

{
    "id": "r3649234124",
    "time": 0.02,
    "wait": 0,
    "message": "finished",
    "runs": 160,
    "value": 50592,
    "result":[1,92,93,144,146,145,148,147,149,150,151,152,153,154,155,156,214,215,298,296,297,294,295,293,292,290,291,289,288,287,217,216,218,213,212,222,221,219,286,285,284,280,283,282,281,278,279,275,276,277,232,233,230,228,200,199,235,274,273,272,238,237,236,234,198,197,167,168,165,131,130,104,129,132,133,103,78,76,80,75,77,72,73,74,71,69,70,67,68,105,64,66,63,62,65,107,106,108,110,61,59,39,57,60,58,112,109,111,113,123,124,121,125,126,127,177,175,176,178,187,188,250,251,190,189,179,173,171,172,128,174,169,170,195,191,192,194,193,196,242,240,241,239,271,269,270,243,247,246,245,244,249,248,268,267,265,266,264,262,258,257,259,260,254,255,261,263,252,253,186,256,185,184,183,182,181,180,120,122,118,119,117,115,114,116,55,56,54,53,52,51,50,49,48,47,44,46,45,41,43,40,42,37,38,36,35,32,33,34,31,30,29,28,27,26,25,24,22,23,21,18,17,15,16,19,20,81,79,82,102,136,135,134,137,138,162,163,164,166,201,202,203,229,231,227,225,226,299,206,205,204,223,224,207,208,220,209,210,211,160,161,159,158,157,143,142,141,140,139,97,96,95,98,101,100,99,84,83,87,85,86,94,91,89,90,88,14,13,12,11,10,9,8,7,5,6,2,3,4],
    "NAME": "pr299"
}

得られた解の経路長は "value":50592 でした。pr299 の既知最良解は 48191 ですので、誤差5％になります。まだループ回数などのパラメータ設定を特に行っていない段階ですが、なかなか良質な解が得られましたね。

マシンパラメータの調整

マシンパラメータの調整を行ってみましょう。TSP ソルバーで指定可能なパラメータの内、精度向上に影響しそうなものは以下のとおりです。

  • 計算パラメータ
    • steps : 1ループ内での計算ステップ数。
  • 実行回数
    • loops : 計算のループ回数。0 を指定した場合、上限時間まで実行。
    • target : 到達目標値。評価値が指定値に到達した場合、計算を終了する
    • timeout : 実行時間の上限値(秒)

steps を変化させる

パラメータ steps は一度の求解におけるアルゴリズムの処理回数を表します。
こちらを指定しない場合（または0を指定した場合）、自動的に steps の値を変化させて計算します。
今回の実験では steps を明示的に指定し、解精度の変化を観察してみます。
実行する問題は引き続き pr299 を使用します。

実験で利用したコードは下記のとおりです。
パラメータは URL クエリパラメータによって指定しますが、今回は requests パッケージの機能を使用します。

import json
from pathlib import Path

import requests

SQBM_URL = "http://SQBM+_engine_server:8000/solver/tsp"  # 起動中のSQBM+のホスト名を指定
TSPLIB_DIR = Path().cwd() / "TSPLIB"  # TSPLIB インスタンスの格納場所を指定


def tsp_solver_solve(data: str, parameters: dict = {}):
    response = requests.post(
        SQBM_URL,
        headers={
            "Content-Type": "application/octet-stream",
        },
        params=parameters,
        data=data,
    )

    return json.loads(response.text)


if __name__ == "__main__":
    instance_name = "pr299"
    with open(TSPLIB_DIR / (instance_name + ".tsp"), "r") as f:
        data = f.read()

    steps_list = [100, 300, 1_000, 3_000, 10_000, 30_000, 100_000]
    for steps in steps_list:
        result_json = tsp_solver_solve(data, {"steps": steps})
        print(f"steps: {steps:6}, time: {result_json['time']:2.3f}, " f"value: {result_json['value']:5}")

実行結果はこのようになりました。

$ python sqbm_tsp_solver.py
instance: pr299
steps: 100, time: 0.015, value: 51161
steps: 300, time: 0.026, value: 49557
steps: 1000, time: 0.069, value: 48644
steps: 3000, time: 0.187, value: 48318
steps: 10000, time: 0.538, value: 48227
steps: 30000, time: 1.552, value: 48191
steps: 100000, time: 5.144, value: 48191

steps を大きくしたとき、計算時間も増加するものの解精度は向上することが分かりました。
また、pr299 の既知最良解である 48191 に到達することも確認できました。
なお、最良解 48191 の巡回ルートを地図上にプロットするとこのようになります。

まとめ

  • TSP ソルバーでは QUBO 定式化なしに TSP の求解が可能
  • 300都市程度の問題でも高速に解を得られた
  • パラメータ調整により精度向上の余地もみられた

Tags

SBM

About Author

hiroki.kawahara

Leave a Comment

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。

Recent Comments

Social Media