simulated-bifurcation-algorithm
simulated-bifurcation-algorithm copied to clipboard
bqth29
VRP
Hello, I am using the DSB algorithm to solve the VRP problem and converting it into a Qubo matrix. SQA can achieve the expected effect, but using dSB cannot achieve the ideal effect. The matrix size is 150 * 150, and changing the coefficients such as time. step is useless. The result violates the constraint objective function and cannot achieve the ideal effect. I would like to ask how I can adjust it. Looking forward to your reply.
May I ask if there are any requirements for the matrix size or complexity limit that this project deals with
And I want to know if the fundamental difference between SBM on amplify.fixstars is the lack of auto tuning
Hello @sb12q,
The VRP problem can indeed be converted to a QUBO model so the SB algorithm can be used to approximate a solution. However, the VRP quadratic formulation must include constraints which can be hard for SB to respect. Based on our experiments, SB performs better with unconstrained problems. Keep in mind that SB is a heuristic algorithm so there is no guarantee of optimality in the results it provides.
We can still try to solve your problem. The good news is that there is no matrix size limitation (except your hardware memory) so your 150 x 150 matrix should work fine.
Can you please provide us with more detailed information regarding your exact problem (what are you trying to solve, source data, etc.) so we can have a look a it?
Finally, there are many differences between SBM and our implementation. The SBM is a specific hardware designed by Toshiba for running SB algorithm computations. Our implementation is meant to be fully open-source and free. It runs on any computer and on GPUs to take advantage of the tensor operations on which SB relies. (it also includes more tuning regarding the stopping criteria of the algorithm and a multi-agent search).
您好 ，
VRP 问题确实可以转换为 QUBO 模型，因此 SB 算法可用于近似解。但是，VRP 二次公式必须包括 SB 可能难以遵守的约束。根据我们的实验，SB 在处理无约束问题时表现更好。请记住，SB 是一种启发式算法，因此无法保证它提供的结果是最优的。
我们仍然可以尝试解决您的问题。好消息是没有矩阵大小限制（除了您的硬件内存），因此您的 150 x 150 矩阵应该可以正常工作。
您能否向我们提供有关您的确切问题的更多详细信息（您要解决什么、源数据等），以便我们查看一下？
最后，SBM 和我们的实现之间有很多不同之处。SBM 是 Toshiba 为运行 SB 算法计算而设计的专用硬件。我们的实施旨在完全开源且免费。它可以在任何计算机和 GPU 上运行，以利用 SB 所依赖的张量运算。（它还包括有关算法停止条件的更多调整和多代理搜索）。
Hello, thank you for your reply. I will organize the data and send it to you for review. My problem is a regular VRP problem and does not include capacity. For small-scale problems, I adjust the penalty coefficient to convert it into a Qubo matrix. The SQA simulated quantum annealing algorithm can obtain a similar value that is close to or even equal to the exact solution value. Large scale problems require a large penalty coefficient, and I am currently adjusting it. However, for the SBM algorithm 150 * 150 matrix of this small-scale project, the solution obtained is very unreasonable, violating constraints or not violating constraints. Its target value is particularly large, far greater than the value of the exact solver. I am currently seeking improvement. I asked a professional who said it is because compared to Toshiba's SB algorithm, this project lacks automatic parameter tuning function. The two major features of SB algorithm are parallel computing and automatic parameter tuning, which has not been disclosed. I would like to ask if this is the case? Therefore, I would like to ask if there are any successful cases (relatively large-scale or medium scale 500 * 500) in this project that have constrained the punishment transformation of the Qubo matrix for similar cases. If you have had successful cases before, I will continue to try. If not, I need to consider feasibility? Because it is uncertain whether there is room for adjustment.
@sb12q Here is the paper describe how toshiba adjust the paramter. https://arxiv.org/html/2503.23966v1
Hello @sb12q and sorry for the late reply,
We are currently working on the use of the SB algorithm for "classical" NP-hard problems. This includes a proper API and scaling parameters and constraints.
From our first observations, it appears that constraints are often violated and this is most likely - as you mentionned it - due to the hardcoded SB parameters that could benefit from fine-tuning.
We will open an issue to start working on parameters fine-tuning, hoping this can help you on your task.
All the best!
Hello @sb12q and sorry for the late reply,
We are currently working on the use of the SB algorithm for "classical" NP-hard problems. This includes a proper API and scaling parameters and constraints.
From our first observations, it appears that constraints are often violated and this is most likely - as you mentionned it - due to the hardcoded SB parameters that could benefit from fine-tuning.
We will open an issue to start working on parameters fine-tuning, hoping this can help you on your task.
All the best!
I opened it here #105, if anyone wants to take part to the dicussion you are welcome!