CAMBranch: Contrastive Learning with Augmented MILPs for Branching

Thanks for your valuable insights and suggestions. Here are our responses:

Thanks for pointing this out. Actually, we have displayed the table-format results in Appendix Table 5. In the revised version, we will place Table 5 into the main text.

Maybe missing a bibliography [1]. Could you please add it? Thanks for your feedback!

In Gasse et al. (2019), experiments results have demonstrated that GCNN outperforms other ML approaches by a large margin. Therefore, we did not include these ML approaches and CAMBranch will certainly outperform them now that CAMBranch’s performance is close to GCNN’s.

Furthermore, it's essential to note that CAMBranch is a plug-and-play method, ensuring ease of implementation without conflicts with other auxiliary methods in most cases, and can be combined with other auxiliary methods. This adaptability and compatibility contribute to its versatility and potential for integration with other methods.

Currently, the model architecture of CAMBranch follows Gasse et al. (2019) and it only has ~10k parameters, light enough compared with those extremely deep graph neural networks like DeeperGCN. The hidden size is only 64 and extremely small for graph neural networks. The hidden layer is only one.

To explore whether lighter GNN with less expert data can achieve similar IL accuracy or not, we conducted additional experiments. In our additional experiments, conducted with the same 10% training data (less expert data), we trained the GCNN while adjusting the hidden size to 32 and 16. Imitation results on Set Covering are shown in the following. The results highlight that merely reducing the hidden size leads to negligible performance changes. In contrast, our proposed CAMBranch significantly outperforms these approaches.

Significantly, when considering MILP solving, while imitation learning (IL) accuracy holds importance, it isn't the primary metric of concern. In contrast, time, Nodes, and wins are the primary metrics and can actually measure the performance of a neural branching strategy. This discussion is detailed in the Appendix E Discussion section. It's crucial to note that while Strong Branching serves as the expert strategy for imitation learning, it might not represent the optimal branching strategy. Therefore, IL accuracy in imitating Strong Branching merely stands as an intermediate result and cannot fully demonstrate the models’ performance.

The true essence lies in the metrics evaluated during the inference stage—solving instances fast, and generating fewer nodes. Figures 2, 3, and 4 display the results, demonstrating CAMBranch's superior performance in these crucial metrics, especially evident in handling significantly harder instances.

Thank you for your further suggestions. Regarding the comparison of training overhead, we acknowledge that CAMBranch requires additional computations compared to the original GCNN in Gasee et al. (2019). To this end, we evaluated the computational burden for both models, measured in terms of training time per batch. Below are the results of training on Set Covering with each batch containing 64 samples. From the results, we can see that, despite the introduced computation by CAMBranch, the observed difference in computational speed is deemed acceptable—merely a matter of several milliseconds. In summary, the training overhead associated with CAMBranch is within acceptable bounds.

We appreciate your second suggestion as well. Aligning with established works in this domain, such as Gasse et al. (2019) and Gupta et al. (2020), we presented the results of our proposed method on four classical datasets. These results underscore the potential of our approach. Then, as you pointed out, the industry presents more challenging MILPs with prolonged collection processes. In such scenarios, CAMBranch's augmentation component outpaces Strong Branching solving in generating labeled expert samples. Unlike the latter, CAMBranch removes the need to solve NP-hard instances, directly generating samples based on the collected small parts of data.

Here, we first consider the Capacitated Facility Location Problem, which exhibits the lowest collection efficiency among the four MILP benchmarks in our paper. Generating 100k expert samples using Strong Branching to solve the instances takes 84.79 hours. In contrast, if obtaining the same quantity of expert samples, CAMBranch requires 8.48 hours (collecting 10k samples initially) plus 0.28 hours (generating the remaining 90k samples based on the initial 10k), totaling 8.76 hours—an 89.67% time savings. The advantages will probably be more pronounced in more challenging benchmarks. Although our current results are based on the four classic benchmarks, the underlying idea of CAMBranch is promising and will promisingly offer insights to the community, which will also lead to further efforts for this community. We appreciate your valuable suggestion and will be committed to further exploration and contribution to our community based on your insights.

Thanks for your valuable feedback. Maybe there are misunderstanding and we will clarify it in the following responses.

Response to the questions 1.

Thanks for pointing this out. There may be some misunderstanding for "generalize across diverse MILP instances". In our work, we follow Gasse et al. (2019) and focus on homogeneous MILP solving, i.e., the training and test MILP instances are the same type of problems, which is a popular setting in industry practice. Such models do not need to generalize across diverse MILP instances in the homogeneous setting but need to generalize across the same type of instances, i.e., those with different coefficients and different scales of variables and constraints.

Within this specialized context, we prefer to choose light graph neural networks due to their high efficiency during the inference phase. Following Gasse et al. (2019), we leverage the GCNN as CAMBranch’s backbone model. GCNN can capture the features of MILP bipartite graphs and exhibits robust learning capabilities from expert samples during the imitation learning phases.

In CAMBranch, as detailed in our paper, “we leverage this principle by viewing a MILP and its corresponding AMILP as positive pairs while considering the MILP and other AMILPs within the same batch as negative pairs.” This follows the simplest way of negative sampling strategy in contrastive learning, and our results already demonstrate its contribution to superior performance. Moreover, incorporating more advanced hard negative sampling strategies is a choice to further improve the model’s performance.

Since the CAMBranch pipeline operates in two stages, the exploration-exploitation trade-off isn't our concern. Specifically, we first collect expert samples for imitation learning, followed by the training of the policy model after this collection phase. Once the model is trained, it becomes directly available for inference without the necessity to address mechanisms preventing premature convergence.

Given that our CAMBranch methodology imitates Strong Branching, it aligns with Strong Branching decisions in most cases. The interpretability of neural branching remains an ongoing research focus and an open problem in this field, and we intend to explore this further in our future work.

Response to the weaknesses

1. As depicted in the results presented by Gasse et al. (2019), the imitation learning paradigm demonstrates remarkable superiority in this domain. Since CAMBranch follows Gasse et al. (2019), CAMBranch also demonstrates superior performance. Therefore, there is no such concern.

2. Indeed, our CAMBranch model demands modest computational resources during training phases. For the inference phases, it is the same as the models in Gasse et al. (2019), both of which show faster solving speed, especially in hard instances.

3. Since our CAMBranch follows Gasse et al. (2019) and the model backbone are extremely light graph neural networks, grid search for hyperparameter tuning does not need too many resouces. Actually, both CAMBranch and Gasse et al.(2019) are not sensitive to the hyperparameter tuning, further streamlining the optimization process.

4. As responding in Question 1, “we focus on homogeneous MILP solving, i.e., the training and test MILP instances are the same type, which is a popular setting in industry practice.” From the results in our paper, CAMBranch as well as GCNN in Gasse et al. (2019) obviously generalize well in homogeneous MILP instances. Therefore, no such concerns.

Dear Reviewer 8jS2,

We have revised our paper according to the other three reviewers' suggestions.

We would appreciate it if you could confirm that our responses address your concerns. We are happy to answer more if you have any remaining concerns or questions.

Best,

Authors

Thanks for your valuable feedback. CAMBranch aims to mitigate issues of the extremely long collection time of expert samples by innovatively generating new expert samples from existing ones. Notably, CAMBranch leverages only a small fraction of the expert samples, compared to the GCNN method in Gasse et al., (2019). Its adaptable nature makes it a plug-and-play solution, seamlessly integrated into various neural branching methods for B&B applications.

Response to the weaknesses: 1.

Thanks for highlighting this. While CAMBranch might not consistently outperform GCNN in a small subset of easy and medium instances, it's important to note that the differences are marginal in these scenarios. However, the true strength of CAMBranch shines through in harder instances.

For instance, in Table 5, which is the primary focus of this paper, the Combinatorial Auction Problem at the medium level reveals that CAMBranch performs with a mere 0.3s difference compared to GCNN(10%), specifically 12.68s versus 12.38s. This trend is consistent across most cases where CAMBranch doesn't outperform GCNN (10%), as similarly observed in Table 8.

However, when tackling genuinely challenging instances, especially in Set Covering, Capacitated Facility Location, and Maximum Independent Set (problems significantly more complex than the hard Combinatorial Auction Problem, evident from the solving times and the number of instances successfully solved), CAMBranch distinctly demonstrates its superiority in solving these intricate problems. For instance, in Set Covering, CAMBranch has a solving time of 1427.02s compared to GCNN 10%'s 2385.23s. This exemplifies the practical utility of CAMBranch since real-world instances are rarely as simple as the Combinatorial Auction Problem; most instances pose challenges of much higher complexity, such as hard Set Covering problems.

Taking this into account, CAMBranch serves as a robust, plug-and-play solution, especially in scenarios where inefficient data collection hampers performance. It consistently exhibits high efficacy in MILP problem-solving while requiring fewer resources, making it a compelling choice for improving methodologies in such settings.

CAMBranch, its plug-and-play nature facilitates easy implementation, specifically enhancing the neural branching decision part in the B&B algorithm. While the primary focus of CAMBranch is on the branching part, it's worth noting that the core idea of generating expert samples sharing identical decisions from the original ones holds potential insights for other decision parts within B&B solvers, such as node selection and cutting planes. The fundamental idea of generating new labeled expert samples from original expert decisions holds promise for broader applicability within the B&B framework.

The CAMBranch method is proposed to alleviate challenges arising from inefficient expert sampling. Therefore, in such contexts, it is more meaningful to use CAMBranch when facing data-scarce issues. While CAMBranch is primarily tailored to address data scarcity issues, its adaptability allows users to combine this methodology with a full training dataset. This integration aids in the form of data augmentation, further fostering improvements in the training process.

Thanks for pointing these out. In the introduction part, we report that collecting 100k expert samples for four types of problems requires 26.65 hours, 12.48 hours, 84.79 hours, and 53.45 hours, respectively. Therefore, collecting 20k experts（20% of the whole data) needs about 20% of the former time periods.

The 10% means 10% expert samples, not MILP instances. Generating MILP instances is trivial, but acquiring the expert samples is challenging since numerous NP-hard MILP instances need to be solved, making it a time-consuming endeavor.

Additionally, it's worth noting that Gasse et al. (2019) extensively explored the relationship between the number of solved MILP instances and expert samples in their Appendix Section 1. Our proposed methods have nearly identical observations to Gasse et al. (2019).

Response to the question:

Yes, it is an interesting observation and we've thoroughly investigated this observation through multiple experiments, consistently confirming its occurrence. One potential reason is that Strong Branching is not always the optimal expert strategy for branching and sometimes may lead to sub-optimal decisions, even if it makes high-quality decisions most of the time. This aligns with similar observations outlined in recent studies by Scavuzzo et al. (2022), Dey et al. (2023), and Gamrath et al. (2020). Refer to our Appendix Discussion part, “Recent studies by Scavuzzo (2022), Dey (2023), and Gamrath (2020) have even suggested that Strong Branching may underperform in certain cases, falling short of problem-specific rules.” This intriguing observation inspires us to delve into this phenomenon, for more exploration in future work.

Thanks for your valuable feedback and suggestions. The inspiration behind the CAMBranch project stems from real-world challenges encountered in the industry, i.e., the low sample efficiency observed during the collection of expert samples for imitation learning. To mitigate this, CAMBranch introduces a solution by generating labeled expert samples from the original datasets. This approach alleviates the need to collect a large quantity of expert samples. With a relatively small amount of data, we achieve superior and acceptable performance. The implications of this approach are highly meaningful in real-world applications.

Response to the weaknesses:

Thanks for pointing this out. Your concern is that “it is unknown whether it limits the potential of imitation learning-based MILP methods.” While we understand that discussing CAMBranch (100%) compared to GCNN (100%) is one approach to alleviate this concern directly, we would like to propose an alternative way, i.e., to compare CAMBranch (10%) and GCNN (10%) since you can assume the full datasets have 10k expert samples which are also enough for training usually and the performance for GCNN (10%) is still acceptable in most of the cases. Therefore, after comparing GCNN (10%) and CAMBranch (10%), we can observe that CAMBranch (10%) shows high superiority. Thus, this observation suggests that CAMBranch will probably not limit the potential of imitation learning-based methods. Experiments for CAMBranch (100%) are also as the following. Here for combinatorial auction problem. The same observations are obtained.

Easy

Medium

Hard

In fact, In practical scenarios, it is hard to measure the exact number of samples required to obtain an acceptable policy model. For some problems, maybe 10k is enough, while for others 100k, 200k, or more will lead to a better performance. In such contexts, CAMBranch is proposed to ensure that with any available dataset, one can use CAMBranch’s augmented approach to train a powerful policy model. Notably, CAMBranch initiates the process with data augmentation, enabling the generation of Hundreds of Thousands of labeled samples that are totally different data one another for neural networks. CAMBranch significantly mitigates the time-intensive data collection process by providing an abundance of augmented expert samples. The results demonstrate CAMBranch’s superiority and highlight its value.

Table 5 follows the paper by Gasse et al. (2019), a format also employed by other papers within this domain. We have presented Figures 2-4 as a visual representation of the data in Table 5, as we believe it provides a clearer comparison of the gaps between different methods in different difficulty levels. We are open to exploring alternative methods to present the results and welcome any suggestions you may have. Thank you for your input.

Thank you for your advice. While we aspire to include Table 8 in the main text, space constraints have compelled us to make the paper as concise as possible. Given the abundance of intriguing observations that warrant discussion, we have chosen to place Table 8 in the Appendix to ensure a comprehensive exploration.

Response to the question:

Utilizing the shifted geometric mean for metric calculations stands as a widely accepted practice in MILP benchmarking within the community, which is also employed by Gasse et al. (2019) and Zarpellon et al. (2021), two representative papers in this domain. Shifted geometric means have the advantage of neither being compromised by very large outliers (in contrast to arithmetic means) nor by very small outliers (in contrast to geometric means).

The solving time for different instances, even the same instance solved with different seeds, inherently has the potential for substantial variations due to the NP-hard nature. Therefore, the community use shifted geometric mean to facilitate a more equitable comparison. In such contexts, $s$ in our paper is set to 1 for time and 100 for Nodes, following the previous work.

References:

Gasse, M., Chételat, D., Ferroni, N., Charlin, L., & Lodi, A. (2019). Exact combinatorial optimization with graph convolutional neural networks, NIPS.

Zarpellon, G., Jo, J., Lodi, A., & Bengio, Y. (2021, May). Parameterizing branch-and-bound search trees to learn branching policies. AAAI.