BTBS-LNS: A Binarized-Tightening, Branch and Search Approach of Learning Large Neighborhood Search Policies for MIP

We sincerely thank Reviewer uy5T for the positive feedback and precious suggestions! Below we address each comment in detail:

Q1: Detail explanation on the "Binarize and Tighten" approach.

Thanks for your comments. For general integer variables, we propose a "Binarize and Tighten" scheme. At first, in the binarization phase, general integer variables were encoded to $d = \lceil{\log_{2}{(ub-lb)}}\rceil$ substitution variables. For example, a general integer variable $x$ with range $[0, 7]$ can be encoded to 3 variables ($x_1, x_2, x_3$) to represent the original variable with decreasing significance. In this way, we transform the LNS decision for the original variable to 3 different decisions on substitution variables. Then, when either variable is fixed by LNS, it indicates current solution reliable at corresponding significance. The decisions are utilized to tighten the bounds of original variables sequentially, rather than directly fixed, at current step illustrated in Alg.1.

Q2: Explanation on the branching components, as it doesn't actually carry out the branching part of this procedure.

Thanks for your insightful comments. The meaning of branching in this paper mainly refers to the one used in the previous work [1]. In other words, we identify the potentially wrongly decided variables by LNS and optimize them by adding the local branching constraints. It takes effect on top of LNS, making them closer to global optimum and serves as a further optimization scheme to the learned LNS policy.

Q3: In order to understand how the authors defined a neighborhood for their large neighborhood search procedure, I again had to consult the appendix. This is a critical detail of a large neighborhood search algorithm and should be made much more clear.

Thanks for your suggestions. We will update the paper and place some critical descriptions back to the main text if page permits.

Q4: I cannot tell what data was used to train these models in any of the experiments.

As illustrated in Sec 4.1, for SC, MIS, CA and MC, we generate several training instances following the same distribution with the testing set, except for different problem sizes. Then the LNS and branching policy will be sequentially trained on these instances. The features and states for the instances are given in Table 7 in the appendix.

As for heterogeneous instances like MIPLIB, we performed cross-validation. Specifically, at each round, we split them into training, validation, and testing sets by 70%, 15%, and 15%. In this way, the whole dataset can be tested sequentially to make fair comparison.

References:

[1] Liu D, Fischetti M, Lodi A. Learning to search in local branching[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2022, 36(4): 3796-3803.

We sincerely thank Reviewer zCZB for their valuable suggestions. Summary of responses and revisions are as follows:

Q1: Could there be meaningful MIP instances other than MIPLIB where variables exist simultaneously with no upper or lower bounds? If it exists, can BTBS-LNS handle it? Are there serious robustness problems with ignoring such instances?

We really appreciate your insightful comments. Although rare, there may be instances that contain variables simultaneously with no upper or lower bounds (called "free" variables). In our current implementation, we will leave them unfixed (untightened). We argue that it was not serious robustness problems, as the presolve technique in MIP solvers can handle most of the cases into single unbounded or totally bounded. The few remaining variables being unfixed will not contribute to heavy computational costs. To be more convincing, we will test our approach on those instances to further evaluate its generalization ability, in our next round of response with updated experiments.

Q2: On page 8, in 'Hyperparameters' under section 4.1, the authors mention the use of SCIP as the default solver, noting that this is the blue box part of Fig.1. In my understanding the SCIP solver should correspond to the 'MIP solver' on the right hand side of Fig.1, and the boxes for Neighborhood Search and Branching Policy on the left hand side are similarly blue, is this a minor graphing and writing error, or am I misunderstanding that SCIP is equally involved in these stages?

Sorry for some misunderstanding. SCIP only corresponds to the 'MIP solver' on the right hand side of Fig.1. We will make it clear in the updated paper version.

Q3: As described in the experiment part, the authors conduct experiments on those MIP instances that are encoded from other combinatorial problems, including set covering, maximal independent set, combinatorial auction, and maximum cut. Actually, there are specific optimization solvers for each of those combinatorial optimization problems, and MIP solvers do not represent the state of the art in solving those problems. As a submission to a top-tier conference, it is required to compare their proposed method against the real state of the art.

Thanks for your insightful suggestions. Similar to the MIP solvers, our proposed approach was designed for general instances, rather than specific problems. We don't finetune our structures or frameworks specifically for each problem. In this respect, except for the specific problems, we also compared our BTBS-LNS on more heterogeneous instances (MIPLIB) from diverse problems, and it also delivers superior performance compared with the MIP solvers, further demonstrating the generalization ability. However, we really appreciate your valuable suggestions. Comparison with specific optimization solvers may be an interesting topic to further improve and demonstrate the performance of our proposed BTBS-LNS, and we will try to supplement some experiments, in our next round of response with updated experiments.

Q4: In fact, there exist standard benchmarks for evaluating MIP solvers, i.e., Hans Mittelmann's benchmarks (https://plato.asu.edu/bench.html). Why don’t the authors test their proposed method and baseline solvers on those standard benchmarks?

Thanks for your comments. We have evaluated our proposed approaches on these standard benchmarks. The anonymous MIPLIB (AMIPLIB) tested in Table 3 contains of a curated set of instances from MIPLIB, which are benchmark instances to test MIP solvers from Hans Mittelmann (https://plato.asu.edu/ftp/milp.html). And to make full comparison, we have also tested the whole 240 benchmark instances from MIPLIB in Appendix A.5, and detailed performance analysis are reported in Appendix B. In general, our proposed BTBS-LNS can achieve competitive performance even on these standard cross-distribution instances.

Owing to the limited characters of only one response and we want to answer your questions in detail, we have to add another reply in the following!

Q10: Is there an inherent reason why the bound tightening works in powers of two?

We really appreciate your valuable comments. Intuitively, we utilized a similar binarization encoding scheme to efficiently control the encoded variable counts, avoiding heavy computational costs. And on the other hand, considering that the general integer variables may deliver different ranges, an adaptive bound tightening scheme may be more suitable to deal with the dynamic ranges across variables. With the current scheme, each encoded variable can represent the original integer variable at different significance, utilized to sequentially tighten the bounds.

Q11: Why do you claim that MIPs are more difficult than IPs? Please cite the CS theory that says this is the case.

Sorry for some confusing expressions, and we will update them to make it clear. In this paper, the difficulty of MIP compared with IPs mainly lie in that the continuous variables may require different treatment in learning-based approaches, as they can rarely be fixed. While in general, the difficulty of both MIP and IPs can vary depending on the characteristics of the specific problems being considered. Different problem instances may present unique challenges that impact the complexity and feasibility of finding optimal solutions.

References:

[1] Wu, Yaoxin, et al. "Learning large neighborhood search policy for integer programming." Advances in Neural Information Processing Systems 34 (2021): 30075-30087.

[2] Song J, Yue Y, Dilkina B. A general large neighborhood search framework for solving integer linear programs[J]. Advances in Neural Information Processing Systems, 2020, 33: 20012-20023.

[3] Huang T, Ferber A M, Tian Y, et al. Searching large neighborhoods for integer linear programs with contrastive learning[C]//International Conference on Machine Learning. PMLR, 2023: 13869-13890.

[4] Williams R, Gomes C P, Selman B. Backdoors to typical case complexity[C]//IJCAI. 2003, 3: 1173-1178.

[5] Achterberg T. Constraint integer programming[J]. 2007.

Owing to the limited characters of only one response and we want to answer your questions in detail, we have to add another reply in the following!

Q6: The paper makes several claims/arguments that I just do not follow/support, e.g., backdoor variables.

Thanks for your insightful comments. Backdoor variables refer to a set of variables, such that when set correctly, the sub-solver can solve the remaining problem [4]. LNS may benefit from the backdoor variables due to its partial fixing mechanism. If we can find the backdoors and fix them correctly as soon as possible, the LNS may deliver significantly better performance. In this paper, we extend the meaning of backdoor variables to those with different solutions compared with global optimum (BTBS-LNS-G), which may be confusing to some extent. We have clarified its meaning in the abstract. To identify and optimize those variables efficiently, we propose an extra branching policy on top of LNS at each step.

Q7: The paper argues that current approaches "become ensnared in local optima", which has to be explained

We really appreciate your comments, and we will update some expressions to make it clear. As you mentioned, the descriptions for LNS and local optimum may be inaccurate. In fact, the drawbacks and limitations of current learning based LNS approaches may derive from limited learning accuracy or performance. Driven by the learning complexity of MIP problems, current approaches may be easy to be ensnared in local optima. It has nothing to do with LNS as a framework. In other words, what we claimed "ensnared in local optima" totally refers to the non-optimal learning based LNS policies, rather than the LNS itself. Hybrid policies or adaptive neighborhood size were both strategies to deal with the limitations of learning-based approaches. Specifically for our BTBS-LNS, it can be regarded as an improved LNS approach by identifying and optimizing the potentially wrongly decisions by the learned LNS policy. And therefore, it can help the LNS decisions getting closer to global optimum, jumping out of local optimum in some cases.

Q8: The experiments are all given 200 seconds for solving, which may be unreasonable.

Thanks for your comments. As illustrated above, our BTBS-LNS was an improved primal heuristic to search for better feasible solutions, while not prove optimality. In MIP solvers, multiple primal heuristics are called iteratively at each branch and bound node, with strong time/iteration/node constraints to ensure efficiency. They try to find feasible solutions of good quality in a reasonably short period of time [5]. And to make fair comparison, both Gurobi and SCIP was fine-tuned with the aggressive mode to focus on improving the objective value, rather than proving optimality. The time limit 200s was set following similar protocols with the previous publication [1], and within 200s, some approaches can already deliver quite close gaps compared with the global optimum on most of the instances. To make comparisons in detail, anytime performance within 200s timelimit was reported in Fig.4 and Fig.6, 7, 8, 9 in the appendix, revealing the superior performance over competing baselines almost anytime from 0s to 200s.

Q9: The experiments do not provide sensitivity analysis or ablation in the main text beyond comparing different branching schemes. Maybe there is more in the appendix, but those are critical details for the main text.

Thanks for your valuable suggestions. In Sec 4.4, we make sensitivity analysis on the branching variable ratios. And detailed sensitivity analysis on other important hyperparameters will be supplemented in our next round of response.

As for the ablation study, we tested the degraded versions of our BTBS-LNS by removing each component separately, including

• LNS-TG: where we replace the tripartite graph with the widely used bipartite graph.
• LNS-Branch: where we remove the branching policy.
• LNS-IBT, LNS-IT: where we remove the binarize & tighten mechanism separately.
• LNS-ATT: where we replace our attention-based graph attention network with the widely used GNN.

As can be seen from Table 1, 2, 3, they all performed slightly worse, revealing the effectiveness and necessity of each component.

Note that owing to the limited characters of only one response and we want to answer your questions in detail, we have to add another reply in the following!

We thank reviewer 38AJ so much for the careful review and insightful comments! Below we would like to illustrate some details.

Q1: This paper is not well written and results in a variety of issues and typos.

Thanks for your suggestions. We will check the overall expressions and writing in detail and correct some typos in the updated paper version.

Q2: Key contributions of the paper are barely even discussed in the main text. Furthermore, the bound tightening scheme seems somewhat arbitrary -- there are many tightening/filtering strategies, see the CP literature.

Thanks for your valuable suggestions. We will place some important components, e.g., branch and search method, tripartite graph, back to the main text if page permits.

As for the bound tightening scheme, it was designed for general integer variables. The intuition is to balance between complexity and exploration scope. In this respect, we designed a binarize-then-tighten scheme. The binarization was utilized to encode them with several substitute decision variables, utilized to evaluate the reliability of current solution at different significance. And afterwards, the bitwise LNS decisions were applied to the bound tightening sequentially. When either bit indicates the current solution reliable, we tighten the bounds that maintains a pivotal position close to (or precisely at) the midpoint of the recalibrated bounds. We argue that when the current solution sits precisely at the midpoint of variable bounds, no further bound tightening should be performed as it shows no preference for either direction, which drives us to design the current bound tightening scheme, tightening the bounds on the far side iteratively.

Q3: There are experiments at the start of the paper before the reader can even really understand what is being tested, on what instances, etc. This is essentially a visualization for marketing purposes rather than science.

We really appreciate your insightful comments. The existence of Fig.2 was utilized to intuitively illustrate the potential limitations and drawbacks of current learning based LNS approaches on instances from Maxcut and MIPLIB. However, it may be confusing for the readers to some extent in the methodology section. It may be better to illustrate the limitations in a clear way.

Q4: The conclusion is essentially non-existent, nor do the authors discuss weaknesses of their work.

Thanks for your suggestions, and currently the conclusion and weaknesses given in Sec 5 were not sufficient. In general, we have proposed a binarized tightening branch and search approach to learn LNS policies in this paper. It was designed to efficiently deal with general MIP problems, and delivers superior performance over competing baselines on ILP, MIP datasets and even heterogeneous instances from MIPLIB. Sufficient ablation studies demonstrate the effectiveness of each component, including the tripartite graph, binarize and tighten scheme, and the extra branching at each step.

However, the proposed BTBS-LNS is only a primal heuristic to search for better feasible solutions, while cannot prove optimality, which are also common limitations of LNS-based approaches. Implementing them into MIP solvers as primal heuristics may be a possible solution. However, interaction with current existed primal heuristics, and the rule to take effect, are key challenges in practical implementation. In general, applications of the learning-based approach in real-world scenarios will be our future directions.

Q5: I take great issue with the big claim in the abstract that the approach performs competitively with Gurobi and SCIP. As best I can tell, this approach is a heuristic, meaning this is an apples and oranges comparison.

Thanks for your valuable comments. Our proposed approach is an improved primal heuristic to search for better feasible solutions. Similar to all the heuristic based LNS methods, it cannot prove optimality. As you mentioned, MIP solvers, like Gurobi and SCIP, will simultaneously find feasible solutions and prove the optimality. To make fair comparison, both Gurobi and SCIP were fine-tuned with the aggressive mode to focus on improving the objective value, rather than proving optimality. It follows the same protocol as previous publications [1, 2, 3]. Compared with the hybrid multiple primal heuristics implemented in MIP solvers, our proposed BTBS-LNS can deliver better solutions within the same timelimit, demonstrating its effectiveness.

Note that owing to the limited characters of only one response and we want to answer your questions in detail, we have to add another reply in the following!

We sincerely thank Reviewer 5yM1 for the detailed feedback and precious suggestions! Below we address every comment in detail.

Q1: The writing for some important parts is difficult to understand. In Fig.1, are the neighborhood search and branching policy two separate local searches in one iteration?

Thanks for your comments. The large neighborhood search (LNS) and branching are two separate learned policies. At each iteration, current problem states will be firstly fed into the learned LNS policy network, and obtain the fix/unfix decisions, denoted as $n_i^t$. Afterwards, the neighborhood search decisions, along with the problem states, will serve as inputs for the branching networks (see Sec 3.4 for detail), and the branching decisions for the potentially wrongly fixed variables by LNS can be obtained, denoted as $b_i^t$. In this respect, branching policy are indeed on top of LNS to optimize some potentially wrong LNS decisions. Then as illustrated in Alg.2, $n_i^t$ and $b_i^t$ are utilized to jointly optimize the current solution.

Q2: Details on how you implement the branching policy are totally missing, e.g., how you collect data and train. The variant BTBS-LNS-L looks very similar to Sonnerat et al. The design for the branching policy is not well-justified conceptually.

Thanks for your valuable suggestions. Training pipeline for the branching policy was briefly introduced in Alg.3 in the appendix. Specifically, we propose to learn the branching policy with an offline manner. The inputs are tripartite graph-based features (same as LNS policy learning), where we additionally append the LNS decisions at each step as variable features, as we only focused on the fixed variables for extra branching. In this respect, branching can be seen on top of LNS, which was significantly different from Sonnerat et al [1]. Then the graph-based features are fed into a similar graph attention network as described in Sec 3.3 to update the node/edge representations. We finally process the variable nodes by a multi-layer perceptron to obtain the branching probability for each variable at this step. Cross-entropy loss was utilized to train the branching network to bring the outputs closer to the collected labels

Specifically for the data collection, with the learned LNS policy, we solve the training instances for each problem again. The tripartite graph-based features were collected at each step, along with the LNS decisions. Label collection were different between the two branching variants. In the local branching, labels are collected by incorporating the following constraint at each step:

$\sum\limits_{i \in {\mathcal B} \cap {\mathcal F}} {|x_i^{t + 1} - x_i^t| \le k}$

where ${\mathcal F}$ denotes the fixed variables selected by LNS. With this extra constraint, the re-defined sub-MIP can be solved, and up to $k$ branching variables are selected from ${\mathcal F}$, serving as branching labels. In the global branching variant, it gathers labels also from the fixed variables by LNS at each step and contrast them with the global optimal solution. Variables that exhibit differing values are indicative of potentially misclassified variables within the current LNS decisions.

In general, the intuition of the branching component is to select and optimize those wrongly fixed variables by the learned LNS policy at each step. The global and local branching variants are designed at a global (local) view, to identify the variables that sit far from the global optimum and optimize them with an extra branching process. To further evaluate its effectiveness, we compared our BTBS-LNS with LNS-Branch, where we remove the extra branching policy at each step. Below are the results on complex MIP problems (item placement and AMIPLIB), and the full comparison results can refer to Table 1, 2, and 3.

• Balanced item placement

• Anonymous MIPLIB (AMIPLIB)

As can be seen, our BTBS-LNS achieves consistently and significantly superior performance over LNS-Branch, revealing the necessity of extra branching on top of LNS.

Note that owing to the limited characters of only one response and we want to answer your questions in detail, we have to add another reply in the following!