Very Large Instances

Table 3 shows the results of problems of size 50k to 100k variables. CPLEX was unable to find the best-known solution to any of these problems in the time limit of 6 hours. AlphaQUBO quickly provided best known solutions for all problems, outperforming CPLEX in terms of solution quality and time. Note that these QUBO models are the largest reported on in the literature to date.

ID

Vars

Constraints

Density

CPLEX (OFV)

CPLEX (Time)

alphaQUBO (OFV)

alphaQUBO (Time)

spp50k

50,000

10,000

25

76903

18144

76402

2315

spp60k

60,000

12,000

25

92293

16060

91912

2876

spp70k

70,000

14,000

25

109168

19084

108112

272

spp80k

80,000

16,000

25

125139

18600

123890

175

spp90k

90,000

18,000

25

140223

15278

139269

1804

spp100k

100,000

20,000

25

154694

19509

154351

622

Table 3

Key Takeaway:

alphaQUBO solves large combinatorial optimization problems quickly and efficiently. This is clearly shown in the benchmark with CPLEX.