IBM Watson researcher Sanjeeb Dash mixed-integer linear programs version CPLEX can solve 20,000 node Dwave problems thousands of times faster

Arxiv – A note on QUBO instances defined on Chimera graphs

Dwave indicates Selby and Dash solved different problems

Geordie Rose (CTO of Dwave Systems) indicates that the author of this paper solved the wrong problems. Neither Selby nor Dash were actually solving the problems the hardware solved, which is the source of the speed-ups they are reporting (the problems they solved are known to be easy). Cathy has contacted both, and hopefully both will acknowledge they jumped the gun and those results are incorrect.

Also note that the formulation Dash used was the one we used (conversion to MILP) which he would have known if he’d read the paper. This transformation is known to be the right way to solve sparse QUBOs using CPLEX. Cathy, together with David Johnson, started the DIMACS challenge and pretty much invented the field of experimental algorithmics. It’s puzzling to me how people don’t assume she knows how to use CPLEX properly. Also it was Troyer (different paper, different science!) that responded to Smolin’s paper, which has nothing to do with benchmarking and was about signatures of quantum annealing.

The Dash Paper

McGeogh and Wang (2013) recently obtained optimal or near-optimal solutions to some quadratic unconstrained boolean optimization (QUBO) problems using a 439 qubit D-Wave quantum computer in much less time than with the IBM ILOG CPLEX mixed-integer quadratic programming solver. The problems studied by McGeogh et. al. are defined on subgraphs of 512 node Chimera graphs. We observe that after a standard reformulation of QUBO problems defined on 512 node Chimera graphs as mixed-integer linear programs (MILP), they can be solved to optimality with the CPLEX MILP solver in time comparable to the time reported by McGeogh and Wang for the D-wave quantum compute

They compare the solution times for QUBO-miqp and QUBO-milp solved with the respective solvers of CPLEX. Even for instances based on small graphs such as C4, the difference in time can be significant. The mean solution time for QUBO-milp is 0.03 sec onds, the maximum solution time is 0.09 seconds, and the standard deviation in solution times is 0.015. The corresponding numbers for QUBO-miqp are 36.62 seconds, 1355.85 seconds, and 195.33. Therefore, in the worst case, the running time for QUBO- miqp is over 10,000 times the running time for QUBO-milp.

Why does this happen? We believe it is more because of formulation differences rather than differences in solver quality (though CPLEX-MILP is much more mature, given its relative importance for practical applications).

If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks