Effective Generation of Feasible Solutions for Integer Programming via Guided Diffusion

Thank you for reviewing our work! We try to address your major concerns as follows

Fair comparison and Gurobi: The main goal of this paper is to generate good and complete initial feasible solutions end-to-end using neural network approaches, which is different from both SCIP and Gurobi solves: they aim for producing optimal solutions using initial feasible solutions as a starting point by using the branch and bound algorithm within a fixed time window. Hence, we compare the heuristic solutions obtained from SCIP and solutions after completing from Neural Diving. To further ensure the comparison comprehensive, in the paper, we have added additional results of the best heuristic solutions from Gurobi, as well as the best heuristic solutions from the PS+Gurobi algorithm, as suggested by Reviewer wgcj. The results show that the complete solutions generated by our methods have comparable quality to the best heuristic solutions from Gurobi in the SC dataset and better objectives in the CF and IS datasets. The partial solutions produced from our methods, combined with the CompleteSol heuristic, further improve the quality of solutions beyond all baseline methods. For more details, please refer to table 1 and table 2 in Section 5 in the updated manuscript (or check Table 1 and Table 2 in our global responses).

Small $C$ and Qualitative analysis: We have to point out some misunderstanding in the reviewer's comments. Our algorithms do not require small $C$ to ensure feasibility because they have a high probability of generating complete solutions. Please refer to the result of IP Guided DDIM in table 1 in section 5, which shows that the complete solutions generated by our method alone have a feasibility ratio of at least 90%. Besides, in section 5.1, we provide an illustrative example to demonstrate the distinction between our methods and Neural Diving. The example highlights that IP Guided DDIM is capable of obtaining the optimal solution during sampling without the reliance of Solvers, whereas Neural Diving requires the Solver to complete the partial solution. In addition, we have discovered that randomly sampling a certain portion of variables from the generated solutions, with completion from the CompleteSol heuristic, further improves solution quality.

Moreover, we have included qualitative analysis of the generatived solutions: we sampled 1000 solutions from a single instance of the SC and IS datasets and plotted the distribution of corresponding objectives, see Section 5.3 in the updated manuscript (or see here for the distribution of SC instance and here for the IS instance ). The majority of solutions (over 95%) from our methods have better quality than the Gurobi heuristic. Furthermore, when combining our methods with the CompleteSol heuristic,the distributions of solutions are even closer to the optimal values.

We try to address your minor concerns as follows:

• [Partial solution] No, our approach does not need CompleteSol to generate complete feasible solutions.

• [Coverage ratio] We empirically observed that for the CF dataset, when the value of $C$ is set to above 0.2, the feasibility ratio of partial solutions obtained from Neural Diving is consistently low. On average, less than 40% of the 3000 samples (30*100 instances) were found to be feasible. When $C$ is set to 0.3, none of the generated solutions were found to be feasible.

• [Repeated solutions] See our qualitative analysis.

Thank you for reviewing our work!

More experiments: We added more experimental results comparing our method with Gurobi and the baseline suggested by the reviewer. Please check the results in the Section 5 of the manuscript (or check Table 1 and Table 2 in our global responses). Results show that our methods consistently produce higher quality solutions than these two baselines.

We also report toal training time and total sampling time for 3000 solutions on a workstation equipped with two Intel(R) Xeon(R) Platinum 8163 CPUs @ 2.50GHz, 176GB RAM, and two Nvidia V100 GPUs. During the inference phase, IP Guided DDIM exhibits faster performance than IP Guided DDPM, with average time of 0.46s-1.68s for sampling each solution (see Appendix A.8 or Table 3 in global responses for more detail).

Q1: Yes, to the best of our knowledge, our approach is the first that generates complete and feasible solutions using pure neural techniques, without relying on any solvers.

Q2: loss and inference algorithm

The loss in Eq.(3) utilizes noisy embeddings to reconstruct the original embeddings as the objective. Intuitively, this helps enhance denoising capability in the neural networks, and facilitates the simultaneous training of the solution decoder via estimating $\mathbf{z} _{\mathbf{x}}$. Regarding the inference algorithm, as mentioned in Section 2, in the reverse process, the mean of $\mathbf{z} _{\mathbf{x}}^{(t-1)}$ can be approximated by adding $\mathbf{z} _{\mathbf{x}}^{(0)}$ as a condition

In paper [1], they use the following formula (2) from the forward process

to replace $\mathbf{z} _{\mathbf{x}}^{(0)}$. It implies that

The last equation holds because $\alpha _t:=1-\beta _t$ and $\bar{\alpha} := \prod _{s=1}^t \alpha _s$. Therefore, we obtain the original sampling method of DDPM (Ho et al., 2020). In our work, since we use the neural network to predict $\mathbf{z} _{\mathbf{x}}^{(0)}$, we can directly use Eq.(1) to estimate the mean of $\mathbf{z} _{\mathbf{x}}^{(t-1)}$ in sampling phase as shown in Appendix A.4 in the updated manuscript. In the experiments, we use the same variance estimation as DDPM (see Eq.(7) in Ho et al. (2020)). Based on Eq.(2), we also produce the estimation of $\mathbf{\epsilon}$ by using $\mathbf{z} _{\mathbf{x}}^{(t)}$ and predicted $\mathbf{z} _{\mathbf{x}}^{(0)}$ and use it in the inference phase for DDIM.

[1]. Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.

Other related works. We thank the reviewer for sharing many papers. However, it appears that there may have been some misunderstanding regarding the relationship between our work and other papers. Therefore, we would like to provide further context in order to clarify our position and help the reviewer better understand our contribution.

It is true that numerous works have been undertaken to apply deep learning methods to solve Integer Programming problems. But the underlying ideas are quite different to each other. Particularly, Bengio et al. (2021) categorize existing methods into three main groups (see Appendix A.12 in our update manuscript for a detailed discussion):

• Group 1 End-to-end learning, which refers to the training of a machine learning model to directly generate solutions based on input instances. In the context of solving integer programming (IP) problems, this involves learning to construct solutions, as demonstrated by methods like Neural Diving (Nair et al.,2020; Taehyun Yoon, 2022) and Predict-Search framework (Han et al., 2023). However, these methods still need to rely on a solver to generate complete solution. Another line in end-to-end learning focuses on learning to improve solutions, i.e., neighborhood search techniques (Sonnerat et al., 2021; Wu et al., 2021). It is noteworthy that these methods typically require a solver to acquire an initial solution.

• Group 2 Complex optimization algorithms usually have a set of hyper-parameters left constant during optimization. This area use machine learning to select the values of hyper-parameters.

• Group 3 Learning alongside optimization: This field focuses on developing existed CO algorithms, typically the branch-and-bound framework, that continuously utilize a machine learning model throughout their execution, including techniques such as learning to branch (Gasse et al., 2019) and learning to node selection (Khalil et al., 2022). These works aim to generate high-quality solutions by combining ML method with the branch-and-bound framework in solvers.

Our approach falls into learning to construct solutions of Group 1. Importantly, to the best of our knowledge, our approach is the first that generates complete and feasible solutions using pure neural techniques, without relying on any solvers.

The papers mentioned by the review fall into other groups and study different research questions. Specifically, the papers (Sonnerat et al., 2021; Wu et al., 2021) falls into learning to improve solutions of Group 1 since they focus on learning methods for enhancing solution quality using neighborhood search techniques, not directly related to solution generation. The papers Khalil et al., (2022) falls more into Group 3 and primarily focuses on node selection and also proposes the policy of producing a partial solution through a prescribed rounding threshold, which is then completed using SCIP, similar to Nair et al. (2020) and Taehyun Yoon (2022).

References for part 2:

[1] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A GNN-guided predict-and-search framework for mixed-integer linear programming. In International Conference on Learning Representations, 2023.

[2] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021.

[3] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020.

[4] Taehyun Yoon. Confidence threshold neural diving. CoRR, abs/2202.07506, 2022. URL https://arxiv.org/abs/2202.07506.

[5] Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning a large neighborhood search algorithm for mixed integer programs. arXiv preprint arXiv:2107.10201,2021.

[6] Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighborhood search policy for integer programming. Advances in Neural Information Processing Systems, 34:30075–30087, 2021.

[7] Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.

[8] Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 10219–10227, 2022.

Thank you for reviewing our paper! We try to address your concerns and answer the raised questions below.

First concern and Q1: More empirical comparisons. We added more experimental results comparing our method with Gurobi and a more recent baseline method (Han et al., 2023) suggested by Reviewer wgcj, which shows that our methods consistently produce higher quality solutions than these two baselines. Please check Table 1 and Table 2 in Section 5 for more detail (or check Table 1 and Table 2 in our global response).

Other concerns and Q4: ablations and training time. Further, we ablated on the contrastive learning, i.e., with and without contrastive learning for the embeddings. Specifically, we include an ablation experiment in which we train IP and solution embeddings directly via the training produce of diffusion and decoder (Algorithm 2 in appendix A.3 in the updated manuscript) without using CISP, the results were updated in the Appendix A.9 of the updated manuscript (or check Table 4 in the global responses ).

The results show that CISP plays a crucial role in ensuring that the solutions produced by our methods are more feasible. We found that the advantage of contrastive learning is its ability to extract meaningful representations for IP instances and solutions, which is achieved by the assumption that instances should stay close to their feasible solutions and away from their infeasible ones. This can further integrate features from different forms, as the instance is represented using a bipartite graph and the solution is represented in a vector space. In contrast, this cannot be simply achieved by supervised learning.

As for the training time and computation usage, all our evaluations were conducted on a workstation equipped with two Intel(R) Xeon(R) Platinum 8163 CPUs @ 2.50GHz, 176GB RAM, and two Nvidia V100 GPUs. We have provided the total training time and the total inference time for generating 3000 solutions below (also see appendix A.8 in the updated manuscript). During the inference phase, IP Guided DDIM exhibits faster performance than IP Guided DDPM, with average time of 0.46s-1.68s for sampling each solution (see Appendix A.8 or Table 3 in global responses for more detail).

Q2. We think there is misunderstanding of some parts of our work possibly due to some misleading discussions in our paper. We agree with the reviewer that Gasse et al. (2019) proposed using a bipartite graph structure to model an IP instance and applied GCN to extract variable representations. But their primary focus was on learning the branching policy, i.e., selecting the variable for partitioning the node's search space. Follow-up studies, such as Nair et al. (2020), Yoon Taehyun (2022) and Han et al. (2023) confirm that directly using the bipartite graph and GCN to learn solutions for an IP instance may result in infeasible solutions, and thus extended this method by using partial assignments and CompleteSol heuristic to obtain complete feasible solutions. We clarified this in the revised manuscript in the paragraph 2 of Section 1.

Q3. We agree with the review that the conversion increases the number of constraints. But the point we tried to make is that our approach is generic enough to solve more general integer programming problems. In fact, with the aforementioned computation space, our approach can solve sizable IP problems: the largest instance (CF dataset) solved by our approach has about 5000 variables and 5000 constraints. These sizes can be further improved with more computation resources and more pre-training on typical small-size IP instances.

References for part 1:

[1] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A GNN-guided predict-and-search framework for mixed-integer linear programming. In International Conference on Learning Representations, 2023.

[2] Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.

[3] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020.

[4] Taehyun Yoon. Confidence threshold neural diving. CoRR, abs/2202.07506, 2022. URL https://arxiv.org/abs/2202.07506.

Dear Reviewer jBX3, thank you again for your time and efforts. We appreciate your constructive suggestions to our paper. We hope our response can address your concerns and would like to hear your feedback again. Please forgive our eagerness and impatience, we are very keen to improve our paper and really appreciate the response from an expert like you!

Thank you for your suggestion! We have employed Gurobi to solve each dataset instance for 100 seconds, aiming to obtain the best possible solutions as optimal values. In the updated manuscript, we have included the average optimal values for each dataset in Table 1 and Table 2 in Section 5 (we also reported these results in Table 1 and Table 2 in the global responses). The experimental results demonstrate that our feasible solutions achieve a gap of 7% to 34% compared to the optimal values. This performance is superior to the heuristic methods from Gurobi and SCIP.