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.
