Are there any guidelines for optimizing chain strength?
I've been having trouble getting valid results when submitting my QUBO problem. The code works near perfectly on the simulated annealer which, along with lower noise, does not depend on variables like chain strength and the coefficients in front of my constraints. Are there any guidelines or tips I could use to find the optimal values for these constants?
Comments
I did also encounter this problem and made a little parameter sweep to find the best values.
I observed that for my problem (traveling salesman) that I'm working on, the paramater has a huge impact. I did run the same problem with chain_strength = 50,100,150,200,250 and I got the best performance with chain_strength = 150.
I guess the range where different chain_strengths yield good results depends on the weights of the other parameter in your QUBO.
Unfortunately I don't know any better way than trying out different values and would also appreciate guidelines or tips from others.
This sounds very similar to what I experienced with my problem (job-shop scheduling).
My range of chain strengths was much smaller than Florian's, I think it was between 2 - 10. I chose 10 as that would result in a penalty equal to the average energy of solutions in the sample (small problem). I believe that value was also close to 50% of the max energy for my problem. I did notice some improvements (10% lower average energy, 20% reduction in average chain_break_fraction) , but my results were so bad to start with that I still wasn't getting valid results.
Ultimately, my solution was better variable pruning. I have not re-tested chain strengths.
Florian, I'm curious how you picked your chain_strengths and how much if an impact it had on the final results
I did this coarse parameter sweep and evaluated it for the percentage of valid solutions. The impact can be seen in the plot below:
a valid solution is in my case (traveling salesman person) a result that defines route where every city is visited once. This valid routes can be found at the lower end of the energy spectrum. The energy landscape in this setup was approximately from -600 to 15000 and the qubo parameters were out of this set: (-100,1,2,3,4,5,6,7,8,9,100).
Changing the chain strength definitely brought some improvement, but I guess variable pruning was also in my case the best way to improve the quality of the obtained samples.
In the end I think it it's very important how the weights are set according to the other weights. E.g. in my case I have weights resulting from the penalties of invalid solutions (a city is visited twice, two cities visited at the same time), I have weights coming from the graph of the problem (distances between cities) and I have those chain_strengths. Those are all independently set, but I guess they should not.
I went ahead and did the same, however not for the problem I described in my post above. The results in that post were for when I did no variable pruning for my problem (job-shop scheduling), but the results below will be for the version with variable pruning. Similar to your TSP, I consider a valid solution for my JSP to be one that satisfies the main constraints (all tasks start exactly once, task precedence within a job, and a machine can only execute one task at any time).
Considering the total qubits used by the embedding (embedding length), I picked from the two extremes of the embeddings I have, fewer (96) and more (202). Previous results showed another embedding (95) performing unusually well, so I included it as well. My problem is small and the chains relatively short, and for now, these are the only embeddings I've done this test for. I'm not sure how the results will look for larger problems.
While embeddings 96 and 202 improved with a >1 chain strength, embedding 95 actually got worse. I'm sure the reason is in some property of the embedding, but I haven't taken the time to look at it yet.
Please sign in to leave a comment.