Poor solutions for structured problems

[idnm]

Hi there!

I'm excited to try your CIM simulator, which looks like a very well-written tool. I'm trying to benchmark CIM performance on some structured problems, and so far getting very poor results. By structured, I mean problems like TSP in QUBO formulation, as opposed to generic MaxCut or Sherrington-Kirkpatrick instances.

As an example, consider the following linear assignment problem

$$\sum_{i=1}^n x_{i,j}=\sum_{j=1}^n x_{i, j}=1$$.

Typically there will some objective function in such problems, but here I'm simply looking for feasible solutions. The constraints are converted to QUBO form in the standard way, so that the full objective becomes

$$obj = \sum_{j} (\sum x_{i, j}-1)^2+\sum_{i}(\sum_j x_{i, j}-1)^2$$.

For $n=2$, the case with 4 variables, cim-optimizer works well. But already for $n=3$, i.e. 9 variables, I can't find hyperparameters that would give any decent success probability. Here is an example.

import numpy as np
from cim_optimizer.solve_Ising import Ising

J = np.array([
    [-0.5 ,  0.25,  0.25,  0.25,  0.  ,  0.  ,  0.25,  0.  ,  0.  ],
    [ 0.25, -0.5 ,  0.25,  0.  ,  0.25,  0.  ,  0.  ,  0.25,  0.  ],
    [ 0.25,  0.25, -0.5 ,  0.  ,  0.  ,  0.25,  0.  ,  0.  ,  0.25],
    [ 0.25,  0.  ,  0.  , -0.5 ,  0.25,  0.25,  0.25,  0.  ,  0.  ],
    [ 0.  ,  0.25,  0.  ,  0.25, -0.5 ,  0.25,  0.  ,  0.25,  0.  ],
    [ 0.  ,  0.  ,  0.25,  0.25,  0.25, -0.5 ,  0.  ,  0.  ,  0.25],
    [ 0.25,  0.  ,  0.  ,  0.25,  0.  ,  0.  , -0.5 ,  0.25,  0.25],
    [ 0.  ,  0.25,  0.  ,  0.  ,  0.25,  0.  ,  0.25, -0.5 ,  0.25],
    [ 0.  ,  0.  ,  0.25,  0.  ,  0.  ,  0.25,  0.25,  0.25, -0.5 ]
])

h = np.array(
    [1., 1., 1., 1., 1., 1., 1., 1., 1.]
)

target_energy = -10.5 
solution = Ising(-2*J, -h).solve(
    num_timesteps_per_run=10_000,
    num_runs = 50, 
    num_parallel_runs=50,
    use_GPU=True,
    target_energy = target_energy, 
    hyperparameters_autotune = True
)

Matrices $J, h$ here are hardcoded here, but originate from the assignment problem described above (the target energy is correct, it is reached occasionally). Running this code gives 0 success probability.

External Field Detected
Best combination of epsilon, lambda, and scaling constant: epsilon = 0.1; lambda = 0.1; scaling constant = 10.0
Target Ising Energy: -10.5.
Best Ising Energy Found: -8.5.
Corresponding Spin Configuration: [-1. -1. -1. -1. -1.  1. -1.  1. -1.].
Time Elapsed: 111.53347992897034.
Number of Runs Completed: 50.
Success Probability: 0.0.

This depends on the run (is it possible to set a random seed, by the way?), but overall the success probability seems to be less than 1 percent. The best hyperparameters found also seem to fluctuate a lot. Substituting them in the next run does not seem to improve the success probability. The following code still gives me 0 success prob.

target_energy = -10.5 
solution = Ising(-2*J, -h).solve(
    ahc_ext_eps=1.0,
    ahc_ext_lambd=0.01,
    num_timesteps_per_run=10_000,
    num_runs = 50, 
    num_parallel_runs=50,
    use_GPU=True,
    target_energy = target_energy, 
    hyperparameters_autotune = False,
    hyperparameters_randomtune = False
)

I'm getting much better performance on random instances of MaxCut, for example. I appreciate any comments or advice on how to make progress on structured problems. Thanks!