--- hide-toc: true file_format: mystnb kernelspec: name: python3 --- # 定式化ベンチマーク Python のライブラリとして提供される数理最適化モデルについて、Amplify SDK との比較として定式化のベンチマークを取得しています。ここでは QUBO ソルバーの実行を前提として、[巡回セールスマン問題の定式化](tsp.ipynb) を例にモデルの作成し QUBO として出力するまでの実行時間を計測しました。 ただし、Amplify SDK を含む各ライブラリはそれぞれのカバーする機能が定式化の方法によっても異なります。ここでは次のように定式化を行い、それぞれの機能と方針についてまとめました。 ```{list-table} :width: 100% :widths: 4 5 5 5 5 5 :header-rows: 1 :stub-columns: 1 * - \- - [Amplify](https://amplify.fixstars.com/docs/amplify/v1/) - [PyQUBO](https://pyqubo.readthedocs.io/en/latest/) - [dimod](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/) BQM (index) - [dimod](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/) BQM (symbol) - [dimod](https://docs.ocean.dwavesys.com/en/stable/docs_dimod/) CQM{sup}`*` * - 記号演算 - ✅ - ✅ - ❌ - ✅ - ✅ * - 目的関数 - ✅ - ✅ - ✅ - ✅ - ✅ * - 制約条件 - ✅ - ✅{sup}`**` - ❌{sup}`***` - ❌{sup}`***` - ✅{sup}`*` * - 高次多項式 - ✅ - ✅ - ❌ - ❌ - ❌ * - 係数行列 - ✅ - ❌ - ❌ - ❌ - ❌ * - 変数タイプ - B/S/I/R - B/S - B/S - B/S - B/S/I/R * - 対応マシン - さまざま - ユーザ次第 - D-Wave のみ - D-Wave のみ - D-Wave のみ ``` {.sd-text-right} B: Binary, S: Ising Spin, I: Integer, R: Real \*: QUBO 出力 (制約条件のペナルティ関数化) ができないためモデル作成のみ計測 \*\*: ペナルティ関数を定義する必要あり \*\*\*: ペナルティ関数を目的関数に足すことで表現 (amplify-tsp-bench)= ````{dropdown} Amplify ```python import amplify def tsp_for_amplify(ncity: int, distances: np.ndarray, dmax: float): q = amplify.VariableGenerator().array("Binary", ncity + 1, ncity) q[-1, :] = q[0, :] # 目的関数 objective: amplify.Poly = amplify.einsum( "ij,ki,kj->", distances, q[:-1], q[1:] ) # 制約条件 constraints: amplify.ConstraintList = amplify.one_hot( q[:-1], axis=1 ) + amplify.one_hot(q[:-1], axis=0) return objective + dmax * constraints class BenchTspAmplify: def create_model(self, ncity: int, distances: np.ndarray, dmax: float): self.model = tsp_for_amplify(ncity, distances, dmax) def to_qubo(self): self.model.to_unconstrained_poly() ``` ```` (pyqubo-tsp-bench)= ````{dropdown} PyQUBO ```python import pyqubo def tsp_for_pyqubo(ncity: int, distances: np.ndarray, dmax: float): # from https://github.com/recruit-communications/pyqubo/blob/master/notebooks/TSP.ipynb # NOTE: https://github.com/recruit-communications/pyqubo/blob/master/benchmark/benchmark.py # is not valid for TSP x = pyqubo.Array.create("c", (ncity, ncity), "BINARY") # Constraint not to visit more than two cities at the same time. time_const = 0.0 for i in range(ncity): # If you wrap the hamiltonian by Const(...), this part is recognized as constraint time_const += pyqubo.Constraint( (sum(x[i, j] for j in range(ncity)) - 1) ** 2, label=f"time{i}" ) # Constraint not to visit the same city more than twice. city_const = 0.0 for j in range(ncity): city_const += pyqubo.Constraint( (sum(x[i, j] for i in range(ncity)) - 1) ** 2, label=f"city{j}" ) # distance of route feed_dict = {} distance = 0.0 for i in range(ncity): for j in range(ncity): for k in range(ncity): # we set the constant distance distance += distances[i, j] * x[k, i] * x[(k + 1) % ncity, j] # Construct hamiltonian A = pyqubo.Placeholder("A") H = distance + A * (time_const + city_const) feed_dict["A"] = dmax # Compile model return H.compile(), feed_dict class BenchTspPyQubo: def create_model(self, ncity: int, distances: np.ndarray, dmax: float): self.model, self._feed_dict = tsp_for_pyqubo(ncity, distances, dmax) def to_qubo(self): self.model.to_qubo(index_label=False, feed_dict=self._feed_dict) ``` ```` (dimod-bqm-idx-tsp-bench)= ````{dropdown} dimod BQM (index) ```python import dimod def tsp_for_dimod_bqm(ncity: int, distances: np.ndarray, dmax: float): bqm = dimod.BinaryQuadraticModel(ncity * ncity, dimod.BINARY) # 目的関数 for n in range(ncity): for i in range(ncity): for j in range(ncity): bqm.add_quadratic( n * ncity + i, ((n + 1) % ncity) * ncity + j, distances[i, j], ) # 行に対する制約 for n in range(ncity): left = [(n * ncity + i, 1) for i in range(ncity)] bqm.add_linear_equality_constraint(left, dmax, -1) # 列に対する制約 for i in range(ncity): left = [(n * ncity + i, 1) for n in range(ncity)] bqm.add_linear_equality_constraint(left, dmax, -1) return bqm class BenchTspDimodBQM: def create_model(self, ncity: int, distances: np.ndarray, dmax: float): self.model = tsp_for_dimod_bqm(ncity, distances, dmax) def to_qubo(self): self.model.to_qubo() ``` ```` (dimod-bqm-sym-tsp-bench)= ````{dropdown} dimod BQM (symbol math) ```python import dimod def tsp_for_dimod_bqm_sym( ncity: int, distances: np.ndarray, dmax: float ) -> dimod.BinaryQuadraticModel: bqm = dimod.BinaryQuadraticModel(ncity * ncity, dimod.BINARY) vars = [ [dimod.Binary(f"{n},{i}") for i in range(ncity)] for n in range(ncity) ] # 目的関数 for n in range(ncity): for i in range(ncity): for j in range(ncity): bqm += distances[i, j] * vars[n][i] * vars[(n + 1) % ncity][j] # 行に対する制約 for n in range(ncity): bqm += dmax * (sum(vars[n][i] for i in range(ncity)) - 1) ** 2 # 列に対する制約 for i in range(ncity): bqm += dmax * (sum(vars[n][i] for n in range(ncity)) - 1) ** 2 return bqm # type: ignore class BenchTspDimodBQMSym: def create_model(self, ncity: int, distances: np.ndarray, dmax: float): self.model = tsp_for_dimod_bqm_sym(ncity, distances, dmax) def to_qubo(self): self.model.to_qubo() ``` ```` (dimod-cqm-tsp-bench)= ````{dropdown} dimod CQM ```python import dimod def tsp_for_dimod_cqm(ncity: int, distances: np.ndarray, dmax: float): cqm = dimod.ConstrainedQuadraticModel() vars = [ [dimod.Binary(f"{n},{i}") for i in range(ncity)] for n in range(ncity) ] # 目的関数 obj = 0.0 for n in range(ncity): for i in range(ncity): for j in range(ncity): obj += distances[i, j] * vars[n][i] * vars[(n + 1) % ncity][j] cqm.set_objective(obj) # 行に対する制約 for n in range(ncity): cqm.add_constraint(sum(vars[n]) == 1) # 列に対する制約 for i in range(ncity): cqm.add_constraint(sum(vars[n][i] for n in range(ncity)) == 1) return cqm class BenchTspDimodCQM: def create_model(self, ncity: int, distances: np.ndarray, dmax: float): self.model = tsp_for_dimod_cqm(ncity, distances, dmax) def to_qubo(self): pass ``` ```` ````{dropdown} ベンチマークコード ```python import time def make_distance(ncity: int) -> tuple[np.ndarray, float]: rng = np.random.default_rng(12345) x = rng.random(ncity) y = rng.random(ncity) distances = ( (x[:, np.newaxis] - x[np.newaxis, :]) ** 2 + (y[:, np.newaxis] - y[np.newaxis, :]) ** 2 ) ** 0.5 dmax: float = np.max(distances) # type: ignore return distances, dmax for ncity in [32, 100, 317]: distances, dmax = make_distance(ncity) for bench_class in [ BenchTspAmplify, BenchTspPyQubo, BenchTspDimodBQM, BenchTspDimodBQMSym, BenchTspDimodCQM, ]: bench = bench_class() start = time.time() bench.create_model(ncity, distances, dmax) end = time.time() t1 = end - start start = time.time() bench.to_qubo() end = time.time() t2 = end - start print(f"{t1} {t2}") ``` ```` **ベンチマーク環境** ``````{grid} 1 2 2 2 :padding: 2 2 5 5 ````{grid-item} :padding: 0 0 0 3 :margin: 0 ```{card} CPU Intel{sup}`R` Core{sup}`TM` i9-12900K (E-Cores disabled) ``` ```{card} OS Ubuntu 22.04 ``` ```` ```{grid-item-card} Python 3.11 :padding: 0 3 0 3 :margin: 0 * amplify 1.0.0 * pyqubo 1.4.0 * dimod 0.12.14 ``` `````` ## ベンチマーク結果 % workaround for showing Plotly figure % ```{raw} html ``` ```{code-cell} --- tags: [remove-input, remove-stderr] --- import pandas as pd import plotly.express as px import plotly.io as pio data = [[16,"Amplify",9.27E-05], [25,"Amplify",6.88E-05], [36,"Amplify",9.97E-05], [49,"Amplify",0.000118732], [64,"Amplify",0.000119686], [81,"Amplify",0.000145555], [100,"Amplify",0.000160456], [121,"Amplify",0.00019753], [144,"Amplify",0.000222921], [169,"Amplify",0.000273347], [196,"Amplify",0.000327587], [225,"Amplify",0.00036025], [256,"Amplify",0.000391603], [289,"Amplify",0.000477433], [324,"Amplify",0.000590563], [361,"Amplify",0.00060606], [400,"Amplify",0.000651956], [441,"Amplify",0.000794888], [484,"Amplify",0.000905752], [529,"Amplify",0.001135111], [576,"Amplify",0.001049519], [625,"Amplify",0.001177669], [676,"Amplify",0.001416564], [729,"Amplify",0.001593351], [784,"Amplify",0.001718521], [841,"Amplify",0.001957536], [900,"Amplify",0.001943946], [961,"Amplify",0.00222528], [1024,"Amplify",0.002306581], [1089,"Amplify",0.002649426], [1156,"Amplify",0.002997875], [1225,"Amplify",0.003309131], [1296,"Amplify",0.003594875], [1369,"Amplify",0.003966093], [1444,"Amplify",0.003832459], [1521,"Amplify",0.004283309], [1600,"Amplify",0.004448295], [1681,"Amplify",0.004890323], [1764,"Amplify",0.005404234], [1849,"Amplify",0.006014228], [1936,"Amplify",0.006367326], [2025,"Amplify",0.007068276], [2116,"Amplify",0.007801414], [2209,"Amplify",0.008617878], [2304,"Amplify",0.007824183], [2401,"Amplify",0.008245826], [2500,"Amplify",0.00896287], [2601,"Amplify",0.009761214], [2704,"Amplify",0.010263085], [2809,"Amplify",0.011022687], [2916,"Amplify",0.01189208], [3025,"Amplify",0.013104916], [3136,"Amplify",0.013679743], [3249,"Amplify",0.014846921], [3364,"Amplify",0.016150236], [3481,"Amplify",0.017695904], [3600,"Amplify",0.016322494], [3721,"Amplify",0.017001271], [3844,"Amplify",0.017937064], [3969,"Amplify",0.018792868], [4096,"Amplify",0.019935846], [4225,"Amplify",0.021067262], [4356,"Amplify",0.022222757], [4489,"Amplify",0.029886603], [4624,"Amplify",0.031201243], [4761,"Amplify",0.032712698], [4900,"Amplify",0.034661531], [5041,"Amplify",0.037011147], [5184,"Amplify",0.039380789], [5329,"Amplify",0.041349769], [5476,"Amplify",0.044507861], [5625,"Amplify",0.043555617], [5776,"Amplify",0.046607852], [5929,"Amplify",0.047909617], [6084,"Amplify",0.049533486], [6241,"Amplify",0.051884532], [6400,"Amplify",0.053924799], [6561,"Amplify",0.056623578], [6724,"Amplify",0.058390856], [6889,"Amplify",0.061252356], [7056,"Amplify",0.064158797], [7225,"Amplify",0.072519898], [7396,"Amplify",0.074694872], [7569,"Amplify",0.078118205], [7744,"Amplify",0.081175208], [7921,"Amplify",0.084622383], [8100,"Amplify",0.088214993], [8281,"Amplify",0.092220187], [8464,"Amplify",0.088975668], [8649,"Amplify",0.093203306], [8836,"Amplify",0.097578645], [9025,"Amplify",0.108216286], [9216,"Amplify",0.117958546], [9409,"Amplify",0.127122879], [9604,"Amplify",0.130149245], [9801,"Amplify",0.135959864], [10000,"Amplify",0.139675379], [10201,"Amplify",0.143155932], [10404,"Amplify",0.14694488], [10609,"Amplify",0.151726484], [10816,"Amplify",0.158475161], [11025,"Amplify",0.163659215], [11236,"Amplify",0.169449806], [11449,"Amplify",0.173620582], [11664,"Amplify",0.190505624], [11881,"Amplify",0.187952518], [12100,"Amplify",0.191333294], [12321,"Amplify",0.197302461], [12544,"Amplify",0.203752041], [12769,"Amplify",0.210929394], [12996,"Amplify",0.216718078], [13225,"Amplify",0.246912003], [13456,"Amplify",0.255573273], [13689,"Amplify",0.263508439], [13924,"Amplify",0.273116589], [14161,"Amplify",0.300814986], [14400,"Amplify",0.309835076], [14641,"Amplify",0.316710234], [14884,"Amplify",0.285605073], [15129,"Amplify",0.33084178], [15376,"Amplify",0.30218637], [15625,"Amplify",0.348266721], [15876,"Amplify",0.31750679], [16129,"Amplify",0.364827394], [16384,"Amplify",0.335345507], [16641,"Amplify",0.342283607], [16900,"Amplify",0.348634124], [17161,"Amplify",0.359068751], [17424,"Amplify",0.3700068], [17689,"Amplify",0.37945807], [17956,"Amplify",0.38861239], [18225,"Amplify",0.398347497], [18496,"Amplify",0.409527779], [18769,"Amplify",0.419436455], [19044,"Amplify",0.428367853], [19321,"Amplify",0.44172287], [19600,"Amplify",0.45586741], [19881,"Amplify",0.466280937], [20164,"Amplify",0.481732845], [20449,"Amplify",0.492578387], [20736,"Amplify",0.511633873], [21025,"Amplify",0.526583552], [21316,"Amplify",0.541424751], [21609,"Amplify",0.558040142], [21904,"Amplify",0.575971246], [22201,"Amplify",0.592509627], [22500,"Amplify",0.584789634], [22801,"Amplify",0.594039917], [23104,"Amplify",0.619269371], [23409,"Amplify",0.620789766], [23716,"Amplify",0.635715604], [24025,"Amplify",0.645790458], [24336,"Amplify",0.660801291], [24649,"Amplify",0.676979303], [24964,"Amplify",0.689066291], [25281,"Amplify",0.702891946], [25600,"Amplify",0.717083931], [25921,"Amplify",0.732932329], [26244,"Amplify",0.741057992], [26569,"Amplify",0.842698693], [26896,"Amplify",0.860516667], [27225,"Amplify",0.875992417], [27556,"Amplify",0.893065691], [27889,"Amplify",0.908732057], [28224,"Amplify",0.928986073], [28561,"Amplify",0.946311355], [28900,"Amplify",0.964772701], [29241,"Amplify",0.891912341], [29584,"Amplify",1.006009698], [29929,"Amplify",1.024284363], [30276,"Amplify",1.045701623], [30625,"Amplify",0.974162817], [30976,"Amplify",1.093782783], [31329,"Amplify",1.016245723], [31684,"Amplify",1.140674472], [32041,"Amplify",1.068394184], [32400,"Amplify",1.194435716], [32761,"Amplify",1.118344307], [33124,"Amplify",1.14394486], [33489,"Amplify",1.168364167], [33856,"Amplify",1.209633231], [34225,"Amplify",1.231564522], [34596,"Amplify",1.261775136], [34969,"Amplify",1.305404782], [35344,"Amplify",1.336910844], [35721,"Amplify",1.199819207], [36100,"Amplify",1.216382742], [36481,"Amplify",1.237865567], [36864,"Amplify",1.262149572], [37249,"Amplify",1.282259941], [37636,"Amplify",1.294066906], [38025,"Amplify",1.316236019], [38416,"Amplify",1.34753716], [38809,"Amplify",1.36692071], [39204,"Amplify",1.384322524], [39601,"Amplify",1.411111593], [40000,"Amplify",1.436032295], [40401,"Amplify",1.454410315], [40804,"Amplify",1.481553197], [41209,"Amplify",1.504740357], [41616,"Amplify",1.533810377], [42025,"Amplify",1.558588624], [42436,"Amplify",1.57389617], [42849,"Amplify",1.606753826], [43264,"Amplify",1.637432933], [43681,"Amplify",1.665415764], [44100,"Amplify",1.692073464], [44521,"Amplify",1.711081505], [44944,"Amplify",1.753840089], [45369,"Amplify",1.774175406], [45796,"Amplify",1.801724792], [46225,"Amplify",1.839895129], [46656,"Amplify",1.875293851], [47089,"Amplify",1.910146832], [47524,"Amplify",1.942101002], [47961,"Amplify",1.980130911], [48400,"Amplify",2.018701673], [48841,"Amplify",2.051336408], [49284,"Amplify",2.087353587], [49729,"Amplify",2.125805259], [50176,"Amplify",2.172478199], [50625,"Amplify",2.202131033], [51076,"Amplify",2.249419332], [51529,"Amplify",2.294949889], [51984,"Amplify",2.358826995], [52441,"Amplify",2.400712729], [52900,"Amplify",2.656062007], [53361,"Amplify",2.708972573], [53824,"Amplify",2.771580815], [54289,"Amplify",2.828468561], [54756,"Amplify",2.886733294], [55225,"Amplify",2.947639704], [55696,"Amplify",3.021421909], [56169,"Amplify",3.066215634], [56644,"Amplify",2.768004775], [57121,"Amplify",2.778854489], [57600,"Amplify",2.817772269], [58081,"Amplify",2.852214098], [58564,"Amplify",2.882239819], [59049,"Amplify",2.918477654], [59536,"Amplify",2.964296818], [60025,"Amplify",2.998894572], [60516,"Amplify",3.035671592], [61009,"Amplify",3.069847107], [61504,"Amplify",3.117627621], [62001,"Amplify",3.155214548], [62500,"Amplify",3.192190289], [63001,"Amplify",2.929602981], [63504,"Amplify",3.279174328], [64009,"Amplify",3.009449363], [64516,"Amplify",3.359084487], [65025,"Amplify",3.077080488], [65536,"Amplify",3.458454132], [66049,"Amplify",3.172464728], [66564,"Amplify",3.187776446], [67081,"Amplify",3.235719085], [67600,"Amplify",3.270784259], [68121,"Amplify",3.329084158], [68644,"Amplify",3.370325208], [69169,"Amplify",3.415745616], [69696,"Amplify",3.474949479], [70225,"Amplify",3.504231334], [70756,"Amplify",3.557719469], [71289,"Amplify",3.618027449], [71824,"Amplify",3.675520539], [72361,"Amplify",3.724296093], [72900,"Amplify",3.772123694], [73441,"Amplify",3.832803845], [73984,"Amplify",3.876357913], [74529,"Amplify",3.939578652], [75076,"Amplify",4.004696965], [75625,"Amplify",4.059197068], [76176,"Amplify",4.487405896], [76729,"Amplify",4.163074374], [77284,"Amplify",4.601295352], [77841,"Amplify",4.312493324], [78400,"Amplify",4.363325953], [78961,"Amplify",4.821487069], [79524,"Amplify",4.534025431], [80089,"Amplify",4.558062196], [80656,"Amplify",4.636669636], [81225,"Amplify",4.729419589], [81796,"Amplify",4.832344174], [82369,"Amplify",4.897665977], [82944,"Amplify",4.992205262], [83521,"Amplify",5.068235278], [84100,"Amplify",5.127729535], [84681,"Amplify",5.253166556], [85264,"Amplify",5.334953547], [85849,"Amplify",5.422147393], [86436,"Amplify",5.520197272], [87025,"Amplify",5.611216664], [87616,"Amplify",5.732600331], [88209,"Amplify",5.838080764], [88804,"Amplify",5.919652462], [89401,"Amplify",6.058257937], [90000,"Amplify",5.140513897], [90601,"Amplify",5.152812719], [91204,"Amplify",5.239851356], [91809,"Amplify",5.277008057], [92416,"Amplify",5.376128674], [93025,"Amplify",5.411436439], [93636,"Amplify",5.506927371], [94249,"Amplify",5.54893899], [94864,"Amplify",5.64994812], [95481,"Amplify",5.68894577], [96100,"Amplify",5.71973896], [96721,"Amplify",5.815832257], [97344,"Amplify",5.910229802], [97969,"Amplify",5.954457402], [98596,"Amplify",5.972197771], [99225,"Amplify",5.926132679], [99856,"Amplify",5.902313232], [100489,"Amplify",5.937704325], [1024,"PyQUBO",0.29150 ], [1024,"dimod BQM (index)",0.06412], [1024,"dimod BQM (symbol)",1.087], [1024,"dimod CQM",0.8959], [10000,"PyQUBO",9.87900 ], [10000,"dimod BQM (index)",2.126], [10000,"dimod BQM (symbol)",32.77], [10000,"dimod CQM",26.93], [100489,"PyQUBO",349.00000 ], [100489,"dimod BQM (index)",83.1], [100489,"dimod BQM (symbol)",1062], [100489,"dimod CQM",855], [16,"Amplify 0.12.1",0.000173092], [25,"Amplify 0.12.1",0.000225186], [36,"Amplify 0.12.1",0.00030756], [49,"Amplify 0.12.1",0.000432253], [64,"Amplify 0.12.1",0.000560164], [81,"Amplify 0.12.1",0.00068748], [100,"Amplify 0.12.1",0.000941277], [121,"Amplify 0.12.1",0.001128197], [144,"Amplify 0.12.1",0.001369357], [169,"Amplify 0.12.1",0.001817465], [196,"Amplify 0.12.1",0.002255797], [225,"Amplify 0.12.1",0.00243783], [256,"Amplify 0.12.1",0.003099918], [289,"Amplify 0.12.1",0.003789902], [324,"Amplify 0.12.1",0.004154086], [361,"Amplify 0.12.1",0.00454855], [400,"Amplify 0.12.1",0.005934238], [441,"Amplify 0.12.1",0.006604433], [484,"Amplify 0.12.1",0.007256269], [529,"Amplify 0.12.1",0.007932305], [576,"Amplify 0.12.1",0.009629846], [625,"Amplify 0.12.1",0.010630012], [676,"Amplify 0.12.1",0.01249373], [729,"Amplify 0.12.1",0.012948513], [784,"Amplify 0.12.1",0.014122844], [841,"Amplify 0.12.1",0.015902877], [900,"Amplify 0.12.1",0.017157316], [961,"Amplify 0.12.1",0.020729542], [1024,"Amplify 0.12.1",0.022745728], [1089,"Amplify 0.12.1",0.024587035], [1156,"Amplify 0.12.1",0.025656343], [1225,"Amplify 0.12.1",0.027319312], [1296,"Amplify 0.12.1",0.029599071], [1369,"Amplify 0.12.1",0.031652808], [1444,"Amplify 0.12.1",0.038052201], [1521,"Amplify 0.12.1",0.040365696], [1600,"Amplify 0.12.1",0.045632362], [1681,"Amplify 0.12.1",0.046342373], [1764,"Amplify 0.12.1",0.048691511], [1849,"Amplify 0.12.1",0.051237822], [1936,"Amplify 0.12.1",0.054391742], [2025,"Amplify 0.12.1",0.057870388], [2116,"Amplify 0.12.1",0.061783791], [2209,"Amplify 0.12.1",0.065680265], [2304,"Amplify 0.12.1",0.07783246], [2401,"Amplify 0.12.1",0.082075715], [2500,"Amplify 0.12.1",0.086981773], [2601,"Amplify 0.12.1",0.089370251], [2704,"Amplify 0.12.1",0.094569921], [2809,"Amplify 0.12.1",0.098874569], [2916,"Amplify 0.12.1",0.102502465], [3025,"Amplify 0.12.1",0.107627749], [3136,"Amplify 0.12.1",0.119086742], [3249,"Amplify 0.12.1",0.130530715], [3364,"Amplify 0.12.1",0.133724928], [3481,"Amplify 0.12.1",0.139126182], [3600,"Amplify 0.12.1",0.161703467], [3721,"Amplify 0.12.1",0.1691221], [3844,"Amplify 0.12.1",0.176939368], [3969,"Amplify 0.12.1",0.185654998], [4096,"Amplify 0.12.1",0.191904783], [4225,"Amplify 0.12.1",0.196415663], [4356,"Amplify 0.12.1",0.2049402], [4489,"Amplify 0.12.1",0.212720633], [4624,"Amplify 0.12.1",0.220281243], [4761,"Amplify 0.12.1",0.228739738], [4900,"Amplify 0.12.1",0.237228632], [5041,"Amplify 0.12.1",0.245768547], [5184,"Amplify 0.12.1",0.255371213], [5329,"Amplify 0.12.1",0.265177727], [5476,"Amplify 0.12.1",0.274446011], [5625,"Amplify 0.12.1",0.284912825], [5776,"Amplify 0.12.1",0.330538154], [5929,"Amplify 0.12.1",0.338934541], [6084,"Amplify 0.12.1",0.34914577], [6241,"Amplify 0.12.1",0.360873222], [6400,"Amplify 0.12.1",0.377599359], [6561,"Amplify 0.12.1",0.382658601], [6724,"Amplify 0.12.1",0.390755177], [6889,"Amplify 0.12.1",0.402357817], [7056,"Amplify 0.12.1",0.414294362], [7225,"Amplify 0.12.1",0.427267909], [7396,"Amplify 0.12.1",0.43998313], [7569,"Amplify 0.12.1",0.453189135], [7744,"Amplify 0.12.1",0.468515277], [7921,"Amplify 0.12.1",0.48476541], [8100,"Amplify 0.12.1",0.502392173], [8281,"Amplify 0.12.1",0.522226691], [8464,"Amplify 0.12.1",0.539714694], [8649,"Amplify 0.12.1",0.557114601], [8836,"Amplify 0.12.1",0.573114276], [9025,"Amplify 0.12.1",0.663230777], [9216,"Amplify 0.12.1",0.680469036], [9409,"Amplify 0.12.1",0.698078036], [9604,"Amplify 0.12.1",0.717182279], [9801,"Amplify 0.12.1",0.734380126], [10000,"Amplify 0.12.1",0.755874157], [10201,"Amplify 0.12.1",0.785692096], [10404,"Amplify 0.12.1",0.767130852], [10609,"Amplify 0.12.1",0.796575427], [10816,"Amplify 0.12.1",0.816874385], [11025,"Amplify 0.12.1",0.833752275], [11236,"Amplify 0.12.1",0.856078625], [11449,"Amplify 0.12.1",0.877023697], [11664,"Amplify 0.12.1",0.898231387], [11881,"Amplify 0.12.1",0.919370532], [12100,"Amplify 0.12.1",0.937847376], [12321,"Amplify 0.12.1",0.966069698], [12544,"Amplify 0.12.1",0.982683301], [12769,"Amplify 0.12.1",1.004372358], [12996,"Amplify 0.12.1",1.075474381], [13225,"Amplify 0.12.1",1.076647758], [13456,"Amplify 0.12.1",1.10104537], [13689,"Amplify 0.12.1",1.125991702], [13924,"Amplify 0.12.1",1.153831124], [14161,"Amplify 0.12.1",1.181185603], [14400,"Amplify 0.12.1",1.378538609], [14641,"Amplify 0.12.1",1.40635848], [14884,"Amplify 0.12.1",1.436725616], [15129,"Amplify 0.12.1",1.468566775], [15376,"Amplify 0.12.1",1.501669049], [15625,"Amplify 0.12.1",1.539886475], [15876,"Amplify 0.12.1",1.582930803], [16129,"Amplify 0.12.1",1.611595273], [16384,"Amplify 0.12.1",1.609653711], [16641,"Amplify 0.12.1",1.637283802], [16900,"Amplify 0.12.1",1.664260149], [17161,"Amplify 0.12.1",1.686968327], [17424,"Amplify 0.12.1",1.720116615], [17689,"Amplify 0.12.1",1.748004556], [17956,"Amplify 0.12.1",1.782075763], [18225,"Amplify 0.12.1",1.817974448], [18496,"Amplify 0.12.1",1.847237468], [18769,"Amplify 0.12.1",1.882803679], [19044,"Amplify 0.12.1",1.924093127], [19321,"Amplify 0.12.1",1.954374909], [19600,"Amplify 0.12.1",1.991669774], [19881,"Amplify 0.12.1",2.032533884], [20164,"Amplify 0.12.1",2.073743939], [20449,"Amplify 0.12.1",2.1244874], [20736,"Amplify 0.12.1",2.157899141], [21025,"Amplify 0.12.1",2.213461041], [21316,"Amplify 0.12.1",2.25191927], [21609,"Amplify 0.12.1",2.295990109], [21904,"Amplify 0.12.1",2.348167777], [22201,"Amplify 0.12.1",2.390437484], [22500,"Amplify 0.12.1",2.4483459], [22801,"Amplify 0.12.1",2.830868244], [23104,"Amplify 0.12.1",2.876840115], [23409,"Amplify 0.12.1",2.920388937], [23716,"Amplify 0.12.1",2.975622416], [24025,"Amplify 0.12.1",3.02257967], [24336,"Amplify 0.12.1",3.074261427], [24649,"Amplify 0.12.1",3.138824463], [24964,"Amplify 0.12.1",3.185057521], [25281,"Amplify 0.12.1",3.252398014], [25600,"Amplify 0.12.1",3.27671814], [25921,"Amplify 0.12.1",3.207731485], [26244,"Amplify 0.12.1",3.324149132], [26569,"Amplify 0.12.1",3.385492921], [26896,"Amplify 0.12.1",3.440587401], [27225,"Amplify 0.12.1",3.497018337], [27556,"Amplify 0.12.1",3.552553654], [27889,"Amplify 0.12.1",3.627676368], [28224,"Amplify 0.12.1",3.677097082], [28561,"Amplify 0.12.1",3.739594102], [28900,"Amplify 0.12.1",3.79697752], [29241,"Amplify 0.12.1",3.875931025], [29584,"Amplify 0.12.1",3.939109564], [29929,"Amplify 0.12.1",3.998035073], [30276,"Amplify 0.12.1",4.067542434], [30625,"Amplify 0.12.1",4.140975714], [30976,"Amplify 0.12.1",4.211170554], [31329,"Amplify 0.12.1",4.291448593], [31684,"Amplify 0.12.1",4.379054308], [32041,"Amplify 0.12.1",4.461811423], [32400,"Amplify 0.12.1",4.562819123], [32761,"Amplify 0.12.1",4.678703427], [33124,"Amplify 0.12.1",4.72806251], [33489,"Amplify 0.12.1",4.790589809], [33856,"Amplify 0.12.1",4.850347638], [34225,"Amplify 0.12.1",4.924911857], [34596,"Amplify 0.12.1",5.010771036], [34969,"Amplify 0.12.1",5.08455205], [35344,"Amplify 0.12.1",5.17099607], [35721,"Amplify 0.12.1",5.923170209], [36100,"Amplify 0.12.1",6.039165258], [36481,"Amplify 0.12.1",6.114944577], [36864,"Amplify 0.12.1",6.221640944], [37249,"Amplify 0.12.1",6.299827933], [37636,"Amplify 0.12.1",6.360730886], [38025,"Amplify 0.12.1",6.440552711], [38416,"Amplify 0.12.1",6.535546541], [38809,"Amplify 0.12.1",6.648950815], [39204,"Amplify 0.12.1",6.70527482], [39601,"Amplify 0.12.1",6.83101213], [40000,"Amplify 0.12.1",6.952670097], [40401,"Amplify 0.12.1",6.988735676], [40804,"Amplify 0.12.1",6.878164291], [41209,"Amplify 0.12.1",6.95722425], [41616,"Amplify 0.12.1",7.045882702], [42025,"Amplify 0.12.1",7.262242675], [42436,"Amplify 0.12.1",7.344267607], [42849,"Amplify 0.12.1",7.465735555], [43264,"Amplify 0.12.1",7.566412807], [43681,"Amplify 0.12.1",7.684015036], [44100,"Amplify 0.12.1",7.824592471], [44521,"Amplify 0.12.1",7.908399701], [44944,"Amplify 0.12.1",8.021014214], [45369,"Amplify 0.12.1",8.158521414], [45796,"Amplify 0.12.1",8.247758746], [46225,"Amplify 0.12.1",8.417805791], [46656,"Amplify 0.12.1",8.521734357], [47089,"Amplify 0.12.1",8.6638726], [47524,"Amplify 0.12.1",8.78726995], [47961,"Amplify 0.12.1",8.89971149], [48400,"Amplify 0.12.1",9.042147994], [48841,"Amplify 0.12.1",9.141168594], [49284,"Amplify 0.12.1",9.294381857], [49729,"Amplify 0.12.1",9.409124613], [50176,"Amplify 0.12.1",9.586859941], [50625,"Amplify 0.12.1",9.678881764], [51076,"Amplify 0.12.1",9.802509785], [51529,"Amplify 0.12.1",9.909022331], [51984,"Amplify 0.12.1",10.07336318], [52441,"Amplify 0.12.1",10.3845737], [52900,"Amplify 0.12.1",10.54887342], [53361,"Amplify 0.12.1",10.67626846], [53824,"Amplify 0.12.1",10.84283984], [54289,"Amplify 0.12.1",10.96669078], [54756,"Amplify 0.12.1",11.12514305], [55225,"Amplify 0.12.1",11.26253366], [55696,"Amplify 0.12.1",11.43190312], [56169,"Amplify 0.12.1",11.55493939], [56644,"Amplify 0.12.1",13.11510456], [57121,"Amplify 0.12.1",13.24709392], [57600,"Amplify 0.12.1",13.37448502], [58081,"Amplify 0.12.1",13.54280674], [58564,"Amplify 0.12.1",13.66189134], [59049,"Amplify 0.12.1",13.8125515], [59536,"Amplify 0.12.1",13.99586904], [60025,"Amplify 0.12.1",14.1542697], [60516,"Amplify 0.12.1",14.30214226], [61009,"Amplify 0.12.1",14.4767431], [61504,"Amplify 0.12.1",14.61799502], [62001,"Amplify 0.12.1",14.78278649], [62500,"Amplify 0.12.1",14.98609567], [63001,"Amplify 0.12.1",15.18546569], [63504,"Amplify 0.12.1",15.45340025], [64009,"Amplify 0.12.1",15.48715806], [64516,"Amplify 0.12.1",15.56969213], [65025,"Amplify 0.12.1",15.45804846], [65536,"Amplify 0.12.1",15.93097901], [66049,"Amplify 0.12.1",15.68845284], [66564,"Amplify 0.12.1",15.79248047], [67081,"Amplify 0.12.1",15.94654655], [67600,"Amplify 0.12.1",16.07540512], [68121,"Amplify 0.12.1",16.26151907], [68644,"Amplify 0.12.1",16.39928234], [69169,"Amplify 0.12.1",16.53768623], [69696,"Amplify 0.12.1",16.7533704], [70225,"Amplify 0.12.1",16.91872954], [70756,"Amplify 0.12.1",17.08070564], [71289,"Amplify 0.12.1",17.23229527], [71824,"Amplify 0.12.1",17.42308593], [72361,"Amplify 0.12.1",17.62183189], [72900,"Amplify 0.12.1",17.81020045], [73441,"Amplify 0.12.1",18.02867186], [73984,"Amplify 0.12.1",18.19259679], [74529,"Amplify 0.12.1",18.41549516], [75076,"Amplify 0.12.1",18.5574497], [75625,"Amplify 0.12.1",18.79428339], [76176,"Amplify 0.12.1",18.93877161], [76729,"Amplify 0.12.1",19.18607318], [77284,"Amplify 0.12.1",19.36053765], [77841,"Amplify 0.12.1",19.55815291], [78400,"Amplify 0.12.1",19.78280187], [78961,"Amplify 0.12.1",19.99346662], [79524,"Amplify 0.12.1",20.16756022], [80089,"Amplify 0.12.1",20.46861732], [80656,"Amplify 0.12.1",20.66470444], [81225,"Amplify 0.12.1",20.87595904], [81796,"Amplify 0.12.1",21.14638197], [82369,"Amplify 0.12.1",21.38422775], [82944,"Amplify 0.12.1",21.61783504], [83521,"Amplify 0.12.1",21.76913881], [84100,"Amplify 0.12.1",22.01870918], [84681,"Amplify 0.12.1",22.25100243], [85264,"Amplify 0.12.1",22.48969519], [85849,"Amplify 0.12.1",22.73059988], [86436,"Amplify 0.12.1",23.00052762], [87025,"Amplify 0.12.1",23.2231735], [87616,"Amplify 0.12.1",23.53701568], [88209,"Amplify 0.12.1",23.76956689], [88804,"Amplify 0.12.1",24.03883123], [89401,"Amplify 0.12.1",24.3881712], [90000,"Amplify 0.12.1",27.47148049], [90601,"Amplify 0.12.1",27.6653893], [91204,"Amplify 0.12.1",27.91433907], [91809,"Amplify 0.12.1",28.17641211], [92416,"Amplify 0.12.1",28.43760538], [93025,"Amplify 0.12.1",28.6461637], [93636,"Amplify 0.12.1",28.9519031], [94249,"Amplify 0.12.1",29.30131245], [94864,"Amplify 0.12.1",29.59358513], [95481,"Amplify 0.12.1",29.7363137], [96100,"Amplify 0.12.1",30.06596696], [96721,"Amplify 0.12.1",30.28914189], [97344,"Amplify 0.12.1",30.63115132], [97969,"Amplify 0.12.1",30.85390604], [98596,"Amplify 0.12.1",31.153736], [99225,"Amplify 0.12.1",31.47998548], [99856,"Amplify 0.12.1",31.79635715], [100489,"Amplify 0.12.1",32.07418537]] pio.renderers.default = 'notebook' df = pd.DataFrame(data, columns=["num variables", "formulation", "execution time (s)"]) fig = px.scatter( df, x="num variables", y="execution time (s)", color="formulation", log_x=True, log_y=True ) fig.update_traces(visible="legendonly", selector=dict(name="Amplify 0.12.1")) fig.show() ``` ### 32 都市 (1,024 バイナリ変数) ```{list-table} :width: 100% :widths: 1 1 1 1 :header-rows: 1 * - 定式化 - モデル作成時間 - QUBO 作成時間 - 合計時間 * - [Amplify](#amplify-tsp-bench) - **1.309 ms** - **0.998 ms** - **2.307 ms** 🏆 * - [PyQUBO](pyqubo-tsp-bench) - 266.8 ms - 24.63 ms - 291.5 ms (x126.3) * - [dimod BQM (index)](#dimod-bqm-idx-tsp-bench) - 22.53 ms - 41.58 ms - 64.12 ms (x27.8) * - [dimod BQM (symbol)](#dimod-bqm-sym-tsp-bench) - 1028 ms - 58.48 ms - 1087 ms (x471.2) * - [dimod CQM](#dimod-cqm-tsp-bench) - 895.9 ms - N/A ms - 895.9 ms (x388.4) ``` ### 100 都市 (10,000 バイナリ変数) ```{list-table} :width: 100% :widths: 1 1 1 1 :header-rows: 1 * - 定式化 - モデル作成時間 - QUBO 作成時間 - 合計時間 * - [Amplify](#amplify-tsp-bench) - **0.063 s** - **0.077 s** - **0.140 s** 🏆 * - [PyQUBO](pyqubo-tsp-bench) - 8.519 s - 1.360 s - 9.879 s (x70.7) * - [dimod BQM (index)](#dimod-bqm-idx-tsp-bench) - 0.706 s - 1.419 s - 2.126 s (x15.2) * - [dimod BQM (symbol)](#dimod-bqm-sym-tsp-bench) - 30.83 s - 1.935 s - 32.77 s (x234.6) * - [dimod CQM](#dimod-cqm-tsp-bench) - 26.93 s - N/A - 26.93 s (x192.8) ``` ### 317 都市 (100,489 バイナリ変数) ```{list-table} :width: 100% :widths: 1 1 1 1 :header-rows: 1 * - 定式化 - モデル作成時間 - QUBO 作成時間 - 合計時間 * - [Amplify](#amplify-tsp-bench) - **2.992 s** - **2.946 s** - **5.938 s** 🏆 * - [PyQUBO](pyqubo-tsp-bench) - 279.7 s - 69.23 s - 349.0 s (x58.8) * - [dimod BQM (index)](#dimod-bqm-idx-tsp-bench) - 31.05 s - 52.05 s - 83.10 s (x14.0) * - [dimod BQM (symbol)](#dimod-bqm-sym-tsp-bench) - 991.5 s - 70.83 s - 1062 s (x178.9) * - [dimod CQM](#dimod-cqm-tsp-bench) - 855.3 s - N/A - 855.3 s (x144.0) ```