D-Wave vs CPLEX Comparison. Part 1: QAP
JeanFrancoisPuget 2700028FGP Visits (5545)
Why am I discussing again the D-Wave quantum computer vs CPLEX comparison paper publ
Here are new results for the quadratic assignment problem test series. Our results for the other tests series in will be reported in subsequent posts. To cut a long story short, our results are better than those in the paper. Are these results strong enough to change the conclusion of the paper? You'll see. (I am not answering now to make sure you read the entire post series, clever isn't it?)
Let me also say upfront that I won't discuss D-Wave capacity or how it compares to other software approaches here. I will stick to discussing how to get better performance when using CPLEX.
So, how could we improve CPLEX performance? There are basically three means to consider:
The first two are nobrainers. Modeling is a bit different, and worth a discussion here.
A quadratic assignment problem (QAP) is defined by three items:
The problem is to find a permutation p of the integers in 1..n that minimizes this function
sum Aij Bp(i)p(j)
The 33 QAPs used in the test series were taken from the QAPLIB site. This site also provides information on best published solutions and best bounds when the optimality of the solution isn't proved yet. All the instances used in the test have known optimal solutions.
CPLEX 12.3 didn't do well according to the paper. It could not find any solution on 5 of the 33 test problems within a 30 minute time limit. And for the other 28 problems it only found the best solutions in 2 cases. It was not able to prove the optimality of these solutions. It never found a solution better than the heuristic methods (D-Wave black box or Tabu search).
How could we improve CPLEX performance? We need to model the QAP in a way that would be CPLEX friendly beside running the latest version on a multi core machine .
The main sweet spot for CPLEX is Linear Programing (LP), because there are efficient and scalable (read polynomial time worst case complexity) algorithms for it. Is LP applicable to QAP? Not really, because QAP are combinatorial problems. The next sweet spot for CPLEX is Mixed Integer Programming (MIP). It is a much harder class of problems than LP. However, it is also the class of problems where we spent most time and energy improving CPLEX, which yielded steady perf
Let's try to model QAP as MIP then. We start with a straightforward translation of the mathematical definition of QAP. which can be expressed this way in our OPL modeling language:
int n = ...;
As a matter of fact, it is a cons
int n = ...;
This is a mathematical optimization problem with linear constraints, quadratic objective, and binary variables, ie a Mixed Integer Quadratic Programming (MIQP) problem. The way to move to a MIP is to replace the product of two binary variables xy by a new variable z such that
x + y - z <= 1
This transformation is valid because the objective coefficient of the xy product is non negative. It results in this MIP
int n = ...;
In fact, the release 12.5.1 of CPLEX auto
With this model the situation looks much better than in the paper. Using my laptop, and 4 threads, CPLEX 12.5.1 finds feasible solutions (not very good ones though) in less than 0.01 second on average (versus not being able to find a feasible solution in 30 minutes for 5 of the problems in the paper). It also finds the optimal solution in 4 of the problems (vs 2), and proves optimality in 2 of them (vs 0). For problem esc32d it even finds the optimal solution of cost 200 that none of the methods studied in the paper could find.
These are quite dramatic improvements, aren't they? Are they all due to a more recent CPLEX version and a better machine? Not really. The main improvement comes from the model.
We use a MIP (automatically generated from a MIQP) whereas McGeoch and Wong tried to get to D-Wave sweet spot, which is Quadratic Unconstrained Binary Optimization Problems (QUBOs). These are MIQP problems with only binary variables, and no constraints. It means that they had to get rid of the row and col constraints in the MIQP model above. They did it by modeling the violation of these constraints via additional quadratic terms in the objective (no details are provided in the paper). It may be the right way to use D-Wave black box, but it isn't the best way to use CPLEX as our experiments show.
This said, best solutions CPLEX could find in 30 minutes are still worse than the best ones found using D-Wave black box or Tabu search in 29 problems, equal in 3, and better in only one problem. This is partly explained by the fact that CPLEX not only tries to find good feasible solutions, but it also spends a fair amount of time trying to prove optimality.
In short, we dramatically improved CPLEX results, but it does not really change the fact that heuristic methods (D-Wave blackbox and Tabu) are finding better quality solutions in a limited amount of time. QAP are definitely not CPLEX sweet spot, at least using the simple MIQP model above.
Update on June 17.
The QUBO tests results are discussed in the second post of this series: D-Wa
Update on July 22.
New Weighted Max2SAT problems are reported in the D-Wa