QUBO Instance Examples
Sample QUBO Instances
QUBO instances are the Upper Triangular Version.
Files are .cvs.gz and .utm.gz (File format).
Penalty for TSP and QAP are large constant value to satisfy one-hot encoding of QUBO instances. Penalty value is selected so that optimal solutions are one-hot and those of TSP/QAP are obtained correctly.
Random Instances
Randomly generated QUBO Instances. All elements are selected from -1000 to 1000 (excluding 0) independently and uniformly at random.
1024 bits: r1k.csv.gz, r1k.utm.gz
2048 bits: r2k.csv.gz, r2k.utm.gz
4096 bits: r4k.csv.gz, r4k.utm.gz
8192 bits: r8k.csv.gz, r8k.utm.gz
16384 bits: r16k.csv.gz, r16k.utm.gz
32768 bits: r32k.csv.gz, r32k.utm.gz
MaxCut
Converted from WK2000_1.rud, a randomly generated complete graph with weight -1/+1.
2000 bits: k2000.csv.gz, k2000.utm.gz. Best known solution: -33337 (QUBO), 33337 (Max Cut)
Converted from randomly generated complete graphs. All edge weights are selected from -1000 to +1000 (excluding 0) independently and uniformly at random.
10000 bits: k10000.csv.gz, k10000.utm.gz
32768 bits: k32k.csv.gz, k32k.utm.gz
TSP(Traveling Salesman Problem)
Converted from TSP instances in TSPLIB.
The first visiting city is fixed to city 1. The visiting order of remaining n-1 cities must be computed.
529 bits, Penalty=1000: gr24.csv.gz, gr24.utm.gz. Optimal solution:-21728(QUBO), 1272(TSP)
2209 bits, Penalty=1000: gr48.csv.gz, gr48.utm.gz. Optimal solution:-41954(QUBO), 5046(TSP)
2601 bits, Penalty=2000: berlin52.csv.gz, berlin52.utm.gz. Optimal solution:-94458(QUBO), 7542 (TSP)
5625 bits, Penalty=20000: pr76.csv.gz, pr76.utm.gz. Optimal solution:-1391841(QUBO), 108159(TSP)
14161 bits, Penalty=1000: gr120.csv.gz, gr120.utm.gz. Optimal solution:-112058(QUBO), 6942(TSP)
25500 bits, Penalty=1000: ch150.csv.gz, ch150.utm.gz. Optimal solution:-142472(QUBO), 6528(TSP)
QAP(Quadratic Assignment Problem)
Converted from QAP instances in QAPLIB.
400 bits, Penalty=100000000: tai20b.csv.gz, tai20b.utm.gz. Optimal solution:-1877544681(QUBO), 122455319(QAP)
676 bits, Penalty=10000000: bur26a.csv.gz, bur26a.utm.gz. Optimal solution:-254447561(QUBO), 5426670(QAP)
900 bits, Penalty=1000: nug30.csv.gz, nug30.utm.gz. Optimal solution:-23876(QUBO), 6124(QAP)
2500 bits, Penalty=1000000: tai50a.csv.gz, tai50a.utm.gz. Best known solution:-15058590(QUBO), 4941410(QAP)
10000 bits, Penalty=10000: sko100a.csv.gz, sko100a.utm.gz. Best known solution:-847998(QUBO), 152002(QAP)
22500 bits, Penalty=400000: tho150.csv.gz, tho150.utm.gz. Best known solution:-51866602(QUBO), 8133398(QAP)
N-QUEENS
The positions of n Queens are encoded in an nxn bit matrix so that the bit is1 if a queen is placed.
Since N-QUEEENS is a quite easy problem, it can be solved less than 1 second.
64 bits: nqueen8.csv.gz, nqueen8.utm.gz. Optimal solution: -8 (QUBO)
256 bits: nqueen16.csv.gz, nqueen16.utm.gz. Optimal solution: -16 (QUBO)
10000 bits: nqueen100.csv.gz, nqueen100.utm.gz. Optimal solution: -100 (QUBO)
32761 bits: nqueen181.csv.gz, nqueen181.utm.gz. Optimal solution: -181 (QUBO)