Initialization

Initialization#

from juniqutils import save_ising_file, load_ising_file
import os
import json
import numpy as np
import pandas as pd
import dimod
from collections import defaultdict
np.__version__, pd.__version__, dimod.__version__

('2.3.2', '2.3.1', '0.12.20')

Generation#

Problem specification#

TSP_DATA = json.load(open('tsp_data.json'))
CITIES = TSP_DATA['CITIES']
CITIES

['Berlin',
 'Madrid',
 'Rome',
 'Paris',
 'Vienna',
 'Warsaw',
 'Hamburg',
 'Bucharest',
 'Budapest',
 'Barcelona',
 'Munich',
 'Milan',
 'Sofia',
 'Prague',
 'Cologne',
 'Stockholm',
 'Amsterdam',
 'Naples',
 'Marseille',
 'Turin',
 'Krakow',
 'Valencia',
 'Zagreb',
 'Frankfurt',
 'Seville']

COSTS = pd.read_csv('tsp_costs.csv').set_index('City',drop=True)
COSTS
Berlin Madrid Rome Paris Vienna Warsaw Hamburg Bucharest Budapest Barcelona ... Stockholm Amsterdam Naples Marseille Turin Krakow Valencia Zagreb Frankfurt Seville
City
Berlin 0.00 23.25 15.68 11.01 7.28 5.95 3.10 17.93 8.93 18.63 ... 12.48 6.89 17.47 15.40 12.32 6.50 21.82 11.04 5.89 27.51
Madrid 23.25 0.00 19.97 12.56 24.33 28.34 21.53 33.89 24.96 6.31 ... 32.68 17.65 21.63 10.83 14.83 27.50 3.75 22.09 17.91 5.16
Rome 15.68 19.97 0.00 14.37 11.50 18.05 17.57 21.00 12.03 14.29 ... 27.67 17.12 2.42 9.73 7.27 16.10 17.40 9.14 13.19 23.54
Paris 11.01 12.56 14.37 0.00 12.67 15.87 9.49 23.83 14.86 10.33 ... 20.51 5.59 15.98 7.57 8.16 15.42 13.45 14.14 5.84 16.97
Vienna 7.28 24.33 11.50 12.67 0.00 6.91 9.92 11.50 2.53 18.04 ... 19.17 11.91 12.98 14.29 10.15 5.03 21.24 4.09 7.65 27.34
Warsaw 5.95 28.34 18.05 15.87 6.91 0.00 8.46 17.14 8.50 23.20 ... 17.05 11.96 19.57 19.96 16.79 3.51 26.38 10.68 10.84 32.48
Hamburg 3.10 21.53 17.57 9.49 9.92 8.46 0.00 20.61 11.64 17.99 ... 11.52 4.95 19.41 14.76 13.20 9.19 21.18 13.21 5.41 25.94
Bucharest 17.93 33.89 21.00 23.83 11.50 17.14 20.61 0.00 9.40 28.63 ... 30.21 23.47 22.92 23.95 19.95 13.93 31.70 12.00 19.16 37.67
Budapest 8.93 24.96 12.03 14.86 2.53 8.50 11.64 9.40 0.00 19.30 ... 20.77 13.97 13.60 14.91 10.87 5.98 22.48 3.48 9.88 28.62
Barcelona 18.63 6.31 14.29 10.33 18.04 23.20 17.99 28.63 19.30 0.00 ... 29.80 15.18 16.02 5.26 9.21 22.15 3.70 16.51 13.38 9.80
Munich 6.09 19.43 9.75 8.54 4.53 10.65 8.07 15.96 6.76 13.82 ... 18.12 8.51 11.53 10.54 7.00 9.09 16.93 5.88 4.24 23.12
Milan 11.39 16.09 6.12 8.87 8.86 15.45 12.27 18.54 9.47 10.57 ... 23.55 11.57 7.71 6.10 2.01 13.70 13.61 6.68 7.46 19.71
Sofia 16.67 30.03 17.09 22.08 10.35 16.32 19.48 5.29 8.17 24.53 ... 28.77 21.97 18.71 20.04 16.01 13.96 27.65 8.44 17.88 33.75
Prague 3.91 22.35 13.67 10.58 3.52 7.22 6.59 14.21 5.13 17.29 ... 15.73 8.93 15.34 13.92 10.55 5.40 20.34 7.30 5.54 26.44
Cologne 6.09 17.41 14.62 5.24 9.36 11.16 4.57 20.87 11.59 13.91 ... 16.06 2.95 16.29 11.55 9.92 11.20 17.97 11.36 2.18 21.83
Stockholm 12.48 32.68 27.67 20.51 19.17 17.05 11.52 30.21 20.77 29.80 ... 0.00 16.02 29.51 26.05 24.44 17.88 32.47 22.97 16.52 37.08
Amsterdam 6.89 17.65 17.12 5.59 11.91 11.96 4.95 23.47 13.97 15.18 ... 16.02 0.00 18.81 12.25 12.46 12.44 18.50 13.93 4.76 22.03
Naples 17.47 21.63 2.42 15.98 12.98 19.57 19.41 22.92 13.60 16.02 ... 29.51 18.81 0.00 11.38 8.93 17.85 19.05 10.84 14.69 25.16
Marseille 15.40 10.83 9.73 7.57 14.29 19.96 14.76 23.95 14.91 5.26 ... 26.05 12.25 11.38 0.00 4.98 18.96 8.38 11.98 10.00 14.48
Turin 12.32 14.83 7.27 8.16 10.15 16.79 13.20 19.95 10.87 9.21 ... 24.44 12.46 8.93 4.98 0.00 14.79 12.23 7.85 8.26 18.33
Krakow 6.50 27.50 16.10 15.42 5.03 3.51 9.19 13.93 5.98 22.15 ... 17.88 12.44 17.85 18.96 14.79 0.00 25.39 8.77 9.97 31.49
Valencia 21.82 3.75 17.40 13.45 21.24 26.38 21.18 31.70 22.48 3.70 ... 32.47 18.50 19.05 8.38 12.23 25.39 0.00 19.83 16.48 6.51
Zagreb 11.04 22.09 9.14 14.14 4.09 10.68 13.21 12.00 3.48 16.51 ... 22.97 13.93 10.84 11.98 7.85 8.77 19.83 0.00 9.60 25.70
Frankfurt 5.89 17.91 13.19 5.84 7.65 10.84 5.41 19.16 9.88 13.38 ... 16.52 4.76 14.69 10.00 8.26 9.97 16.48 9.60 0.00 22.49
Seville 27.51 5.16 23.54 16.97 27.34 32.48 25.94 37.67 28.62 9.80 ... 37.08 22.03 25.16 14.48 18.33 31.49 6.51 25.70 22.49 0.00

25 rows × 25 columns

Generate and save problems#

def build_qubo_time_encoding(n, scale):
    Q = defaultdict(float)
    offset = 0
    # cost function
    for i in range(n):
        for j in range(n):
            if j != i:
                for t in range(n):
                    k = i*n + t
                    l = j*n + (t + 1) % n
                    Q[k,l] += scale * COSTS.loc[CITIES[i]][CITIES[j]]
    # first constraint
    for i in range(n):
        for t1 in range(n):
            for t2 in range(n):
                k = i*n + t1
                l = i*n + t2
                Q[k,l] += 1
        for t in range(n):
            k = i*n + t
            Q[k,k] += -2
        offset += 1
    # second constraint
    for t in range(n):
        for i in range(n):
            for j in range(n):
                k = i*n + t
                l = j*n + t
                Q[k,l] += 1
        for i in range(n):
            k = i*n + t
            Q[k,k] += -2
        offset += 1
    return Q,offset

problems = defaultdict(list)
for instance,n in enumerate(range(3,len(CITIES)+1)):
    
    # generate BQM
    scale = 0.01  # if the constraints are satisifed, energy / scale will be the total drive time in hours
    Q,offset = build_qubo_time_encoding(n, scale=scale)
    variablemap = {i*n+t: f'x{i},{t}' for i in range(n) for t in range(n)}  # x_i,t = 1  <=>  traveller will be at city i at time t
    bqm = dimod.BQM.from_qubo(Q, offset)
    bqm.change_vartype(dimod.SPIN)
    bqm.relabel_variables(variablemap)
    nqubits = bqm.num_variables
    ncouplers = bqm.num_interactions
    nvalid = 2*n
    noptimal = 2

    # store optimum reference for benchmark
    tour = [CITIES.index(c) for c in TSP_DATA['OPTIMAL_TOURS'][f'{n}']]
    optimum = sum(COSTS.loc[CITIES[tour[i]]][CITIES[tour[(i+1)%n]]] for i in range(len(tour)))

    # generate information for save_ising_file
    hs, Js, offset = bqm.to_ising()
    qubitmap = {value: key for key,value in variablemap.items()}
    cities = CITIES[:n]
    metadata = {
        'n': n,
        'nqubits': nqubits,
        'ncouplers': ncouplers,
        'nvalid': nvalid,
        'noptimal': noptimal,
        'lambda': scale,
        'optimal_energy': optimum*scale,
        'optimal_cost': optimum,
        'optimal_tour': tour,
        'cities': cities,
        'scale': scale,
    }   
    filename = save_ising_file(instance, hs, Js, offset, qubitmap, metadata)
    print(f'Generated {filename}')

    # gather information for each problem
    problems['filename'].append(filename)
    problems['instance'].append(instance)
    problems['n'].append(n)
    problems['nqubits'].append(nqubits)
    problems['ncouplers'].append(ncouplers)
    problems['nvalid'].append(nvalid)
    problems['noptimal'].append(noptimal)
    problems['lambda'].append(scale)
    problems['optimal_energy'].append(optimum*scale)
    problems['optimal_cost'].append(optimum)
    problems['optimal_tour'].append(tour)
    problems['cities'].append(cities)
    problems['scale'].append(scale)

Generated ../problems/000.ising
Generated ../problems/001.ising
Generated ../problems/002.ising
Generated ../problems/003.ising
Generated ../problems/004.ising
Generated ../problems/005.ising
Generated ../problems/006.ising
Generated ../problems/007.ising
Generated ../problems/008.ising
Generated ../problems/009.ising
Generated ../problems/010.ising
Generated ../problems/011.ising
Generated ../problems/012.ising
Generated ../problems/013.ising
Generated ../problems/014.ising
Generated ../problems/015.ising
Generated ../problems/016.ising
Generated ../problems/017.ising
Generated ../problems/018.ising
Generated ../problems/019.ising
Generated ../problems/020.ising
Generated ../problems/021.ising
Generated ../problems/022.ising

pd.DataFrame(problems).set_index('instance',drop=True)
filename n nqubits ncouplers nvalid noptimal lambda optimal_energy optimal_cost optimal_tour cities scale
instance
0 ../problems/000.ising 3 9 36 6 2 0.01 0.5890 58.90 [0, 1, 2] [Berlin, Madrid, Rome] 0.01
1 ../problems/001.ising 4 16 96 8 2 0.01 0.5922 59.22 [0, 2, 1, 3] [Berlin, Madrid, Rome, Paris] 0.01
2 ../problems/002.ising 5 25 200 10 2 0.01 0.6232 62.32 [0, 3, 1, 2, 4] [Berlin, Madrid, Rome, Paris, Vienna] 0.01
3 ../problems/003.ising 6 36 360 12 2 0.01 0.6790 67.90 [0, 3, 1, 2, 4, 5] [Berlin, Madrid, Rome, Paris, Vienna, Warsaw] 0.01
4 ../problems/004.ising 7 49 588 14 2 0.01 0.6948 69.48 [0, 5, 4, 2, 1, 3, 6] [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
5 ../problems/005.ising 8 64 896 16 2 0.01 0.9048 90.48 [0, 5, 4, 7, 2, 1, 3, 6] [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
6 ../problems/006.ising 9 81 1296 18 2 0.01 0.9091 90.91 [0, 5, 4, 7, 8, 2, 1, 3, 6] [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
7 ../problems/007.ising 10 100 1800 20 2 0.01 0.9154 91.54 [0, 5, 4, 7, 8, 2, 9, 1, 3, 6] [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
8 ../problems/008.ising 11 121 2420 22 2 0.01 0.9505 95.05 [0, 5, 7, 8, 4, 10, 2, 9, 1, 3, 6] [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
9 ../problems/009.ising 12 144 3168 24 2 0.01 0.9745 97.45 [0, 5, 7, 8, 4, 10, 2, 11, 9, 1, 3, 6] [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
10 ../problems/010.ising 13 169 4056 26 2 0.01 1.0151 101.51 [0, 5, 7, 12, 8, 4, 10, 2, 11, 9, 1, 3, 6] [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
11 ../problems/011.ising 14 196 5096 28 2 0.01 1.0428 104.28 [0, 5, 13, 10, 4, 8, 7, 12, 2, 11, 9, 1, 3, 6] [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
12 ../problems/012.ising 15 225 6300 30 2 0.01 1.0460 104.60 [0, 5, 13, 10, 4, 8, 7, 12, 2, 11, 9, 1, 3, 14... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
13 ../problems/013.ising 16 256 7680 32 2 0.01 1.2550 125.50 [0, 5, 13, 10, 4, 8, 7, 12, 2, 11, 9, 1, 3, 14... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
14 ../problems/014.ising 17 289 9248 34 2 0.01 1.2880 128.80 [0, 5, 13, 10, 4, 8, 7, 12, 2, 11, 9, 1, 3, 16... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
15 ../problems/015.ising 18 324 11016 36 2 0.01 1.3281 132.81 [0, 5, 13, 10, 4, 8, 7, 12, 2, 17, 11, 9, 1, 3... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
16 ../problems/016.ising 19 361 12996 38 2 0.01 1.3360 133.60 [0, 5, 13, 10, 4, 8, 7, 12, 2, 17, 11, 18, 9, ... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
17 ../problems/017.ising 20 400 15200 40 2 0.01 1.3449 134.49 [0, 5, 13, 10, 4, 8, 7, 12, 2, 17, 11, 19, 18,... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
18 ../problems/018.ising 21 441 17640 42 2 0.01 1.3513 135.13 [0, 5, 20, 7, 12, 8, 4, 13, 10, 2, 17, 11, 19,... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
19 ../problems/019.ising 22 484 20328 44 2 0.01 1.3627 136.27 [0, 5, 20, 7, 12, 8, 4, 13, 10, 2, 17, 11, 19,... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
20 ../problems/020.ising 23 529 23276 46 2 0.01 1.3781 137.81 [0, 5, 20, 13, 10, 4, 8, 7, 12, 22, 2, 17, 11,... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
21 ../problems/021.ising 24 576 26496 48 2 0.01 1.4039 140.39 [0, 6, 15, 5, 20, 4, 8, 7, 12, 22, 2, 17, 11, ... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
22 ../problems/022.ising 25 625 30000 50 2 0.01 1.4831 148.31 [0, 6, 15, 5, 20, 4, 8, 7, 12, 22, 2, 17, 11, ... [Berlin, Madrid, Rome, Paris, Vienna, Warsaw, ... 0.01
Contents