Learning to Solve Quadratic Unconstrained Binary Optimization in a Classification Way

We sincerely appreciate your thorough review and constructive feedback on our manuscript. We are grateful for your insights and will address your concerns comprehensively in our revision.

To better illustrate our work and to improve the manuscript based on your comments and suggestions, we have added the following improvements:

1. Comparison with Exact Algorithm

We have added comparisons with QuBowl from [1], and the results are as follows, where VCM and VCMG outperform two exact solvers and can achieve almost all optimal solutions (19/20) within 10ms.

We have also added comparisons with Gurobi within 1s, and the results are as follows.

Clearly, compared to QuBowl and Gurobi, our VCM and VCMG are more efficient QUBO solvers.

2. Validation of practical problem

We extended our evaluation to include several MaxCut problem benchmarks. Data from [2], using the objective function as the indicator:

Data from [3], using the average approximation ratios as the indicator:

The results show that VCM provides impressive performance in MaxCut benchmarks, which validates its applicability to QUBO-related problems.

3. Comparison with Unsupervised Method

We appreciate your bringing this significant related work [4] to our attention, and we will include a citation and discussion of this paper in our revision. The unsupervised method, which directly uses the optimization objective function as the loss function, is intuitively appealing. We have trained VCM by the well-known supervised learning method [4] on size 50 under the same dataset and neural settings, which we call VCM-UnS. Its batch loss function in VCM can be concluded as follows. ${p_i}( \theta_{VCM}) = ({state}_i (\theta\_{VCM})+1)/2.$

$L(\theta_{VCM})=\frac{1}{B} \sum_{b=1}^B \sum_{k=1}^N{p}_i (\theta\_{VCM}) Q\_{ij}{p}_j(\theta\_{VCM})$

Details on the training process are shown in Figure 1 in the submitted PDF file and the optimal training GAP (%) of VCM and VCM-UnS are obtained as follows.

It is evident that GST provides a more efficient training process compared to UnS. UnS experiences significant fluctuations. In contrast, the GST training process is remarkably smooth. Compared to the unsupervised trainer UnS, which relies on self-driven model training, GST offers the following advantages in QUBO:

• Integration of both self-driven and heuristic-guided training processes.
• Current labels based on VCM’s performance.
• Provision of a clear learning target guided by heuristic, enabling the creation of more suitable labels for training and facilitating quicker and more stable model convergence.
• The ability to train the VCM without requiring global optimal solutions as labels.

4. The degradation in GCN

We used the GCN [5] to replace the DVN of VCM. In GCN, we used residual connections between hidden layers to facilitate the training of deeper models. The $l$-th layer in GCN is calculated as follows.

After the $L$ layer, the solution can be generated as follows.

We have trained GCN and VCM by GST on size 50 under the same settings. Details and optimal training gap trends are shown in Figure 2 and Figure 3 in the submitted PDF file and the best training GAPs (%) are obtained as follows.

Obviously, the GCN suffered from performance degradation, which is consistent with the conclusion in [5]. However, the performance of VCM steadily improves with increasing depth. Besides, the neural parameters in GCN layers are independent, whereas neural units in VCM depth are consistent, resulting in lower training costs under the same neural settings.

Overall

We are grateful for your in-depth review and valuable suggestions and hope these improvements will significantly enhance the quality and impact of our work. We remain open to addressing any additional questions or concerns you may have and sincerely invite you to reassess the contributions of our paper.

(Character limit, omitting part of ref information)

[1] Rehfeldt, D., et al. Faster exact solution of sparse MaxCut and QUBO problems.

[2] Khalil, E., et al. Learning combinatorial optimization algorithms over graphs.

[3] Nath, A., et al. A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization.

[4] Schuetz, M.J., et al. Combinatorial optimization with physics-inspired graph neural networks.

[5] Kipf, T. N., et al. Semi-supervised classification with graph convolutional networks.

Thank you for your thorough review and valuable feedback on our paper. Your comments are crucial for improving the quality of our work. We would like to address each of your points and suggestions.

1. Comparison

We appreciate your suggestion to discuss NeuralQP [1], a nice work targeting Quadratically Constrained Quadratic Programs (QCQPs). NeuralQP significantly enhances solution efficiency and convergence speed for large-scale QCQPs by utilizing a hypergraph-based neural prediction and iterative neighborhood optimization. It provides a new insight into the solver horizon which is very interesting, and we will discuss it in our revised manuscript.

Specifically, NeuralQP addresses a class of constrained QCQPs with continuous variables, while our work focuses more on providing a fast near-optimal solver for QUBOs, which is a novel attempt to improve computational efficiency and solution quality in unconstrained binary settings. Consequently, it is currently challenging to reformulate NeuralQP’s hypergraph problems into the QUBO formulation, making them difficult to solve with our VCM. However your remarkable suggestion has intrigued us a lot, and NeuralQP provides valuable insights for potential future applications of our VCM, which we intend to explore in future research.

To provide as valuable a benchmark as possible, we have added additional validations with Gurobi within 1s.

For larger datasets, we generated G instances with 10,000 and 20,000 nodes under two distributions for validation.

The results demonstrate that our VCM and VCMG represent more efficient QUBO solvers under the same time situation.

Furthermore, we tested VCM50 under test depth 100 with the SOTA exact algorithm QuBowl [2].

We have also supplemented the validation test results of GCN and we can see its performance degrades in QUBO problems as depth increases. Besides, we compared our proposed GST trainer with the unsupervised trainer from [3], highlighting the need to use self-driven and heuristic guidance in VCM training. These results are presented in our overall response, with figures included in the submitted PDF file.

2. Scalability

The test instances adopted in this study cover various variable sizes (20 to 7000) and data distributions (5 distributions in G instances and 31 benchmark instances represent diverse task distributions). VCM demonstrates consistent advantages across these instances, showcasing its strong scalability.

3. Hyperparameters

Two main hyperparameters include hidden size ($h$) and depth ($d$). Our experiments in Appendix F, show that increasing $h$ has a limited impact on model performance (less than 0.1% difference for sizes ranging from 32 to 256). On the contrary, the impact of $d$ is quite significant. VCM’s performance steadily improves as depth increases.

4. Applicability

The QUBO problem is a classical nonlinear optimization problem that is fundamental to many combinatorial optimization challenges. The proposed VCM aims to provide a new insight to solve this fundamental formulation. However, the way to recast other combinatorial optimization problems into a QUBO formulation is a significant yet challenging work. Over the past decades, researchers have actively advanced this area of study. Some linear or quadratic problems with linear constraints and bounded integer variables can be re-formulated as QUBO using quadratic penalties P [4]. For several simple constraint examples [4], appropriate quadratic penalties can be directly applied.

Therefore, a feasible approach to applying the VCM to solve various problems is to explore methods for reformulating these problems into QUBO.

In response to your feedback and that of other reviewers, we have expanded our evaluation to MaxCut benchmarks. It is clear that both VCM and VCMG outperform state-of-the-art methods on these benchmarks, validating their practical applicability.

Data from [5], using the average objective function as the indicator:

Data from [6], using the average approximation ratios as the indicator:

Overall

We appreciate your thorough review and remain open to addressing any additional questions or concerns you may have.

(Character limit, omitting part of ref information)

[1] Xiong Z, et al. NeuralQP: A General Hypergraph-based Optimization Framework for Large-scale Quadratically Constrained Quadratic Programs.

[2] Rehfeldt, D., et al. Faster exact solution of sparse MaxCut and QUBO problems.

[3] Schuetz, M.J., et al. Combinatorial optimization with physics-inspired graph neural networks.

[4] Kochenberger, G., et al. The unconstrained binary quadratic programming problem: a survey.

[5] Khalil, E., et al. Learning combinatorial optimization algorithms over graphs.

[6] Nath, A., et al. A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization.

Thank you for your thorough and comprehensive response to my review comments. I appreciate the detailed explanations and additional validations you provided, which have addressed my concerns effectively.

I am particularly impressed with the additional benchmark comparisons and the insights you shared regarding the scalability and applicability of the VCM. Your efforts to clarify the distinctions between your work and other models, such as NeuralQP, as well as the potential for future research directions, are very much appreciated.

Given the quality of your responses and the robustness of your model's performance across various tests, I would like to raise my score to 7.

We sincerely appreciate your thorough review and the opportunity to clarify our work regarding the datasets and specific problems solved. We are grateful for the chance to provide a more comprehensive description.

1. Datasets

Our study utilized datasets described in the format "dataset+instance size+(number of instances)". The instance size here represents the nodes in the graph.

These datasets include:

1) Generated Dataset (G):

• Q matrix elements are integers uniformly randomized within [-100, 100], following the benchmark data format [1].
• Used for training (512,000 instances), validation (1,000 instances), and test (1,000 instances) for various instance sizes (10, 20, 50, 100 for training and validation, and 20, 50, 100, 200, 500, 1000 for test).
• To further evaluate VCM's distribution generalization ability, we regenerated 1,000 test instances by invalidating matrix elements in G instances to zero with probabilities of 10% (R-0.9), 40% (R-0.6), 70% (R-0.3), and 90% (R-0.1). Additionally, we generated G-RN-1 following a standard normal random distribution (RN-1).

2) Well-known Datasets (31 instances):

• B2500(10) from ORLIB [1].
• P3000(5), P4000(5), P5000(5), P6000(3) and P7000(3) from [2].
• Q matrix elements are integers within [-100, 100], with varying percentages of zero elements across instances. These 31 instances from well-known datasets represent diverse task distributions and we have included a visualization of distributions in Figure 4 the submitted PDF file.

The test instances adopted in this study cover various variable sizes and data distributions, posing significant challenges to model performance.

2. Applicability

The QUBO problem is a classical nonlinear optimization problem fundamental to many combinatorial optimizations. Numerous combinatorial optimization problems can be recast into standard QUBO formulations, which can be solved using QUBO methods. In recent years, researchers have actively promoted related research [3], [4]. It can introduce the penalty function P to liberate constraints and establish QUBO formulations [5]. For several simple constraint examples, appropriate quadratic penalties can be used directly.

Following your comment and those of other reviewers, we extended our evaluation to include several MaxCut problem benchmarks. We applied the VCM50 under testing depth 100 for validation and the results are shown below. The results obtained demonstrate that VCM's solving performance is consistent with the advantages shown in our test instances, further validating its applicability.

Results from [6], using the average objective function as the indicator:

Results from [7], using the average approximation ratios as the indicator:

Additionally, we provide comparison results with GCN to verify that GCN’s performance degrades as the layer increases in QUBO problems. We also demonstrate that our trainer GST outperforms the unsupervised trainer (UnS) from [8], emphasizing the effectiveness of self-driven and heuristic guidance for VCM training. These results are presented in our overall response, with figures included in the submitted PDF file.

Overall

We believe these additions significantly improve the clarity and impact of our work, providing readers with a more comprehensive understanding of VCM's performance across various QUBO problem instances. Thank you again for your valuable feedback. We look forward to your further comments and are prepared to address any additional questions or concerns you may have.

[1] Beasley, J. E.,1996. Obtaining test problems via internet. Journal of Global Optimization, 8, 429-433.

[2] Palubeckis, G., 2004. Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Annals of Operations Research, 131, 259-282.

[3] Glover, F., Kochenberger, G., Hennig, R., & Du, Y., 2022. Quantum bridge analytics I: a tutorial on formulating and using QUBO models. Annals of Operations Research, 314(1), 141-183.

[4] Glover, F., Kochenberger, G., Ma, M., & Du, Y., 2022. Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange. Annals of Operations Research, 314(1), 185-212.

[5] Kochenberger, G., Hao, J. K., Glover, F., Lewis, M., Lü, Z., Wang, H., & Wang, Y., 2014. The unconstrained binary quadratic programming problem: a survey. Journal of combinatorial optimization, 28, 58-81.

[6] Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L., 2017. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30.

[7] Nath, A., & Kuhnle, A., 2024. A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization. arXiv preprint arXiv:2406.11897.

[8] Schuetz, M.J., Brubaker, J.K. and Katzgraber, H.G., 2022. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4), pp.367-377.

I thank the authors for the detailed answer.. I increase my score