BTBS-LNS: Binarized-Tightening, Branch and Search on Learning LNS Policies for MIP

Thanks for the comments and valuable suggesstions. We address each point and clarify in our revision at the updated paper version.

Q1: The proposed methods are not novel. The global branching idea is similar to [2] by learning from the global (near-)optimal solutions. While the local branching variant is similar to [1]. A detailed explanation of the differences from them should be included.

Thank you for your comments. The main contributions are described in Section 1, including Bound Tightening for MIP, step-by-step incorporation of global information with Global(Local) branching, and the problem encoding with an improved attention architecture. Regarding your primary concern about the comparison between our global (local) branching mechanisms and those in references [1] and [2], we would like to clarify the following points:

1. Different Targets and Decision Scopes: Our branching mechanism serves as a correction module for the RL-based LNS strategy, focusing on whether the LNS policy correctly fixes variables. It uses global-view information to evaluate and refine LNS decisions. While both our approach and [1] and [2] utilize global perspective information, such as optimal solutions or local branching constraints, the scope and target differs. References [1] and [2] make LNS decisions (fix/unfix) for the entire variable set or predict the optimal solution, whereas our branching mechanism complements LNS by correcting its variable fixing results without making decisions for the entire variable set, primarily judging the correctness of the LNS fixing decisions.
2. Different Representations and Architectures: Our method represents the problem as a tripartite graph, enabling more effective integration of information from the objective function into the decision-making process. By comparison, [1] and [2] employ a bipartite graph structure. Furthermore, we propose an improved attention-based GNN architecture, which demonstrates empirical effectiveness in enhancing the quality of decisions.

Q2: The paper is a little bit hard to follow. It includes a lot of information, it would be good to include a summary of takeaways for each experiment.

Thank you for your comments. Below is a detailed summary of the experimental work:

1. Datasets: We conducted tests on both integer programming (IP) and mixed-integer programming (MIP) problems. For IP, we used four well-known NP-hard binary integer programming problems: SC, MIS, CA, and MC. For MIP, we utilized two datasets from the Machine Learning for Combinatorial Optimization (ML4CO) Competition and the MIPLIB2017 benchmark set, a widely recognized standard for MIP solvers.
2. Baselines: We compared our model against numerous baselines, including commercial and open-source MIP solvers, classical heuristic-based Large Neighborhood Search (LNS) methods, and state-of-the-art learning-based approaches.
3. Evaluation: Our experiments evaluated the model's capabilities and performance across several dimensions, demonstrating its superior solving ability and stability compared to various baselines:
   • Solving efficiency: Performance on different datasets (Tables 2, 4, 5).
   • Scalability: Ability to handle problems of varying sizes (Table 3).
   • Real-world Potential: Comprehensive evaluation on the full MIPLIB2017 benchmark set, showcasing its applicability in real-world scenarios (Table 6 and Appendix A.8).
   • Solver Adaptability: Compatibility with different baseline solvers, including Gurobi (Appendix A.4) and SCIP.
   • Hardware Performance: Comparison of our BTBS-LNS on CPU and GPU, highlighting potential improvements with GPU optimization (Appendix A.5).
   • Anytime Performance: Model performance at different cut-off time (Appendix A.7).
   • Stability: Consistency and reliability of the model (Appendix A.6).

(Continue in the next response).

References:

[1] Vinod Nair, et al. Solving mixed integer programs using neural networks. arXiv preprint, 2020

[2] Qingyu Han et al. A gnn-guided predict-and-search framework for mixed-integer linear programming. ICLR, 2023.

We sincerely thank Reviewer bYsh for the positive feedback and precious suggestions! We have addressed each point and provided clarifications in the updated version of the paper.

Q1: Clarify the "global" information in the branching.

Thank you for your insightful comments. We appreciate the opportunity to clarify the meaning of "global information" in our work.

The term "global information" refers to the broader context that goes beyond the immediate observations available during the RL-based training and inference processes. In our framework, the network can observe the current and historical feasible solutions and leverage the problem structure (tripartite graph) to make decisions about fixing/unfixing variables. However, this process may lack a comprehensive evaluation of the current solving state, such as the distance to the optimal solution or the proximity of certain variables to their optimal values. These "global" perspectives provide additional insights that can enhance the accuracy of LNS decisions. Therefore, we introduced an additional branching network to incorporate these global perspectives, aiming to refine the LNS decisions from a holistic problem-solving viewpoint.

We fully acknowledge your point that these "global" perspectives are not directly observable during the inference stage. Consequently, we use offline training to capture the relationship between local decisions and global perspectives. Specifically, the training signals indicate whether the LNS policy produces a correct fixing compared to the optimal solution. The trained network is then applied during inference to make more informed decisions. It differs slightly from the LNS policy in that it focuses on the LNS fixed variable set, rather the entire variable space. Essentially, the branching network functions as a strategy correction mechanism for LNS, leveraging global perspectives during training and applying them in inference.

Q2: Multiple policies can be better ensembled together using standard ensemble methods, because they are policies for the same objective which are just trained differently. Or, LNS policy could be initialized by these branching policies for transfer learning.

Thank you for your insightful comments. We appreciate your suggestions regarding the integration of branching networks into LNS.

In our current implementation, the branching network serves as a strategy correction module for the LNS policy. It is an empirical solution that has proven effective in practical applications. However, we fully recognize the value of your suggestions for more natural ways to combine these policies. Your ideas, such as using standard ensemble methods or initializing the LNS policy with the branching policies for transfer learning, offer promising avenues for more efficiently integrating different strategies. These approaches could potentially enhance the robustness and performance of our framework, especially in real-world scenarios. We agree that these are more natural ways and plan to explore these methods in our future research.

Q3: Clarification for the contributions in the attention-based tripartite graph.

Thank you for your valuable suggestions. We have updated the descriptions in the revised version of the paper, with the changes marked in blue.

Q4: How are substitute variables for integer variables represented? Features in Table 7 does not seem to discuss it.

We apologize for omitting some key information. The encoded substitute variables are also characterized by static and dynamic features. For static features, the variable type and bounds are set to binary and 1/0, respectively, while other features are directly inherited from the original integer variables. For dynamic features, the solution value for each substitute variable is determined based on the encoded results. For example, for a general integer variable with a range of [0, 7], if the current solution value is 5, the solution values of the three substitute variables would be 1, 0, 1. Additionally, the connections between the substitute variables and other nodes are directly inherited from the original integer variables.

We have included these details in Appendix A.2 of the revised version of the paper, with the changes marked in blue.

Thank you for your valuable comments. We have addressed each point and provided clarifications in our revision.

Q1: High Complexity: The approach combines multiple advanced techniques, potentially making it computationally intensive, particularly in scenarios requiring extensive parameter tuning or high-dimensional data.

Thank you for your insights. Our framework integrates RL-based LNS with imitation learning-based branching strategies. To address the complexities in training and inference, we implemented the following optimizations:

1. Training on Small-Scale Instances: We trained the model on relatively simple instances and then applied the learned policies to more complex problems. This approach significantly reduces training complexity and enhances applicability to high-dimensional real-world data.
2. Time-Limited Data Collection: For label collection in the offline branching training, we did not require globally optimal solutions. Instead, we limited the solving time to 200 seconds to obtain high-quality feasible solutions for training.
3. Generalized Hyperparameter Settings: We avoided dataset-specific hyperparameter tuning. Most parameters remained consistent across different datasets, as detailed in Section 4, to enhance the generalizability and usability of our framework.
4. Time-Constrained Testing: All experiments were conducted within a specified time limit, taking into account the inference time of all learned policies. The experimental results demonstrate the time efficiency of our approach.

Q2: Dependence on Initialization: The method relies on an initial feasible solution generated by baseline solvers. Poor initialization could impact overall performance, as the effectiveness of the LNS-based policy might depend on the quality of the starting solution.

Thank you for your insightful comments. The quality of the initial feasible solution can indeed influence the performance of the performance. However, starting the search from an initial feasible solution is a common practice in LNS, allowing for the exploration and optimization of nearby solutions. In our implementation, we use the first feasible solution found by SCIP as the initial point. To ensure a fair comparison, all LNS methods, except for the MIP solvers (SCIP and Gurobi), start from the same initial point. As demonstrated in Tables 2, 3, 4, 5, and 6, BTBS-LNS consistently exhibits superior performance, even outperforming Gurobi on some instances, including the MIPLIB2017 benchmark set.

To further assess the impact of different initial solutions, we conducted additional experiments in Appendix A.4, where we replaced the baseline solver from SCIP to Gurobi, which may theoretically provide a better initial feasible solution for each instance. The results indicate that a better initial point can help improve the final solution quality to some extent, while our BTBS-LNS has consistently demonstrated its effectiveness over all the competing baselines.

Q3: Local Optima: While the branching network mitigates local optima issues, the reliance on imitation learning and reinforcement learning can still lead to convergence to suboptimal solutions in complex or highly irregular MIP landscapes.

Thank you for your valuable insights. Our proposed method, which incorporates branching on top of LNS, helps the learned policies to escape local optima to some extent. Figure 4 visually illustrates this point, showing that branching can refine the decisions made by LNS, particularly in the later stages of optimization. Extensive experimental results also demonstrate the effectiveness of our framework.

However, as you pointed out, due to the nature of local search, even the combination of LNS and branching may not completely avoid issues related to local optima. Addressing this challenge will be a key direction for our future research.

Q4: How does the performance of BTBS-LNS scale with increasing problem size, especially compared to state-of-the-art solvers like Gurobi, in terms of both time complexity and solution accuracy?

In Table 3, we detail the transferability of our learned policies across different problem scales. Specifically, we apply policies learned from smaller instances to larger ones with 2 to 4 times the number of variables and constraints, while maintaining the same distribution (see Table 8 for details). The cutoff solving time is set to 200 seconds, and the inference time for both policies are taken into account. The results show that our proposed method consistently outperforms all LNS baselines and the open-source solver SCIP across different datasets. Compared to Gurobi, our method yields better results on SC2, SC4, CA2, CA4, and MC4, and is only slightly inferior on the remaining three groups.

(Continue in the next response)

We appreciate your insightful comments and valuable suggestions. In response, we have addressed each point and provided clarifications in the revised version of the paper.

Q1: The writing can be improved.

Thank you for your valuable suggestions. We have corrected the typos and reviewed the paper using Grammarly to make further improvements, as reflected in the updated paper.

Q2: The GNN architecture is essentially the same as that of Ding et al.’s. I am not sure that it stands on its own as a contribution. Rather, I view this as an architecture tuning step that is rather incremental.

We thank you for your valuable comments. Although the GNN architecture does exhibit similarities with prior works, we have enhanced the attention mechanism by eliminating the softmax normalization, which has been empirically validated to improve performance. To better emphasize our contributions, we have revised the introduction as recommended by the reviewer bYsh, with the modifications highlighted in blue.

Q3: The corrective mechanism in section 3.4 requires labeled data, namely near-optimal solutions either globally or locally. This increases the data collection cost which now includes this labeling via a MILP solver in addition to RL simulations. Given that the MILPs of interest are NP-Hard to optimize, it is unclear to me that relying on this solving step during data collection is justified.

Thank you for your comments. As you pointed out, label collection for NP-Hard MILPs is particularly time-consuming, especially for large-scale instances. To address this, we adopted the following strategies:

1. Only in the training: We collected (near-) optimal solution labels only for the training phase, which typically involves smaller and easier-to-solve instances. The trained policy can then be directly applied to other instances, including large-scale and difficult ones.
2. Solution Quality: We do not require globally optimal solutions. Instead, we run MIP solvers (e.g., Gurobi) with a restricted cutoff time of 200 seconds. The best incumbent solutions obtained within this time are used as the solution labels. To assess the impact of solution quality, we increased the solving time limit from 200s to 300s on Maximum Cut instances, and potentially better solutions can be obtained to train our method, and other hyperparameters remain unchanged. The results are summarized below.

As evident from the results, BTBS-LNS-G trained with higher-quality solutions achieves slightly better performance.

Q4: The bound tightening method is not described sufficiently clearly. Perhaps a small numerical example can help Illustrate what you’re doing in Algorithm 1.

Thank you for your suggestions. Here we provide a small numerical example to illustrate the process, and we have included it in Appendix A.9 for clear understanding of Algorithm 1. Consider a general integer variable $x_0$ with a range of $[0, 15]$ and a current solution of $3$. This variable is encoded using 4 substitution binary variables: $x_{0,1}$, $x_{0,2}$, $x_{0,3}$, and $x_{0,4}$.

At each LNS iteration $t$, distinct actions $a_{0,1}^t$, $a_{0,2}^t$, $a_{0,3}^t$, and $a_{0,4}^t$ are taken for each substitution variable, controlling the range of the original variable at different levels of significance. Specifically, the decision actions $a_{0,j}^t$ for all $j$ are evaluated sequentially, and the upper and lower bounds are tightened around the current solution whenever $a_{0,j}^t = 0$, as described in Lines 11-12 of Algorithm 1. Here are some examples:

1. If $a_{0,1}^t = 0$ and the others are 1, the updated bounds for $x_0$ will be $[0, 10]$.
2. If $a_{0,1}^t = a_{0,2}^t = 0$ and the others are 1, the updated bounds for $x_0$ will be $[0, 8]$.
3. ...
4. If all decision actions are 0, the updated bounds for $x_0$ will be $[0, 6]$, with the current solution precisely at the midpoint of the variable bounds. Similarly, when the current solution is $12$, the updated bounds will be $[9,15]$.

Importantly, this bound-tightening process is conducted independently at each step, always initiating from the original variable bounds.