MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

Question

I missed the opportunity to ask this on OR.SE by 24 days! I asked it at CS.SE on 6 May 2019 and OR.SE entered Private Beta on 30 May 2019.

• It's a problem about minimizing a sum of terms that are quadratic in its integer variables.
• It's a QUBO (quadratic unconstrainted binary optimization) problem, and QUBO questions have been fairly well received here at OR.SE (e.g. this, this, and this) whereas at CS.SE there was interest from only one user that wrote comments.
• While We're beyond the 60-day limit to "migrate" a question, I'll follow Robert Cartaino's advice and re-ask it here.

---

The Question:

A paper was published recently in Science where the authors minimized the following function:

$$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$

where $s_i$ denotes the $i$th Ising spin, which takes a value of 1 or -1, $s = (s_1 s_2 \cdots s_N)$ is the vector representation of a spin configuration, and $J_{i,j}(=J_{j,i})$ is the coupling coefficient between the $i$th and $j$ spins ($J_{i,i}=0$). The problem is to find a spin configuration minimizing the Ising energy. This problem is mathematically equivalent to a famous combinatorial optimization problem named MAX-CUT (5, 17, 18, 39): divide the nodes of a weighted graph into two groups maximizing the total weight (called "cut value") of the edges cut by the division. By setting the coupling coefficient as $J_{i,j} = - w_{i,j}$ ($w_{i,j} = w_{j,i}$ is the weight between $i$th and $j$th nodes), we can solve MAX-CUT using Ising machines.

In particular, it appears that they are solving instances of weighted MAX-CUT where the input graph is the complete graph on 2000 vertices with edge weights assigned from $\{-1,1\}$ independently and uniformly at random.

They say they found solutions in 0.5 ms and the other specifics such as the criteria for calling something a "solution" are also given.

They say in the abstract that 0.5ms is 10 times faster than the Coherent Ising Machine (a type of quantum calculator), but I would like it to instead be compared to state-of-the-art for conventional algorithms on classical computers.

It should be possible to generate the same type of random instances of MAX-CUT as the authors, and solve the problem with a conventional algorithm for classical computing (e.g. CPUs, GPUs, FPGAs), and compare the performance to what is claimed in the paper, when using the same criteria for what is considered a good enough solution.

Are there any algorithms or codes apart from just general SAT/CSP solvers, that could be applied to this specific problem?

Answer 1

Have a look at MQLib, which contains efficient implementations of many published algorithms. Their paper is awesome too.

You can find a lot of code for QUBO online, one of the most publicized being qbsolv from Dwave. It is meant as a demonstrator of how much better quantum algorithms are, and the method is very basic. In general, I would take any hype on quantum or classical annealers with a hefty grain of salt.

Answer 2

Maxcut with CPLEX CPOptimizer in https://github.com/AlexFleischerParis/howtowithopl/blob/master/maxcutcpo.mod

using CP;

execute
{
  // time limit 10 s
  cp.param.timelimit=10;
}

int n=400;
range r=1..n;

// Random graph  
float edge_prob=0.5;
int  weight_range=10;
int big=100000;
 
tuple t
{
  int i;
  int j;
}

{t} s={<i,j> | ordered i,j in r};

int w[i in r][j in r]=(i<=j)?((rand(big)<=big*edge_prob)?rand(weight_range):0):0;

// end of random graph

//int n=4;
//range r=1..n;
//float w[r][r]=
//
//[[ 0. , 8. ,-9. , 0.],
// [ 8. , 0. , 7. , 9.],
// [-9. , 7.  ,0., -8.],
// [ 0. , 9., -8. , 0.]];

assert card(s)==n*(n-1) div 2;

 // x is the unknown and 0 or 1 means in one or the other side of the fence
 dvar boolean x[r];
 
 dexpr float obj=2*sum(<i,j> in s) w[i][j]*(x[i]!=x[j]);
 
 maximize obj;
 
 subject to
 {
   // break symmetry
   x[1]==1;
 }
 
 {int} x1={i| i in r:x[i]==1};
 
 execute
 {
   writeln("objective = ",obj);
   writeln("x set to 1 : ",x1);
 }

With CPLEX MP at https://github.com/AlexFleischerParis/howtowithopl/blob/master/maxcut.mod

int n=400;
range r=1..n;

// Random graph  
float edge_prob=0.5;
int  weight_range=10;
int big=100000;
 
tuple t
{
  int i;
  int j;
}

{t} s={<i,j> | ordered i,j in r};

int w[i in r][j in r]=(i<=j)?((rand(big)<=big*edge_prob)?rand(weight_range):0):0;

// end of random graph

//int n=4;
//range r=1..n;
//float w[r][r]=
//
//[[ 0. , 8. ,-9. , 0.],
// [ 8. , 0. , 7. , 9.],
// [-9. , 7.  ,0., -8.],
// [ 0. , 9., -8. , 0.]];

assert card(s)==n*(n-1) div 2;

 // x is the unknown and 0 or 1 means in one or the other side of the fence
 dvar boolean x[r];
 
 dexpr float obj=2*sum(<i,j> in s) w[i][j]*x[i]*(1-x[j]);
 
 maximize obj;
 
 subject to
 {
   
 }
 
 {int} x1={i| i in r:x[i]==1};
 
 execute
 {
   writeln("objective = ",obj);
   writeln("x set to 1 : ",x1);
 }

and IBM Quantum Qiskit at https://qiskit.org/documentation/tutorials/optimization/6_examples_max_cut_and_tsp.html