Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Learning to Select Nodes in Branch and Bound with Sufficient Tree Representation
Authors: Sijia Zhang, Shuli Zeng, Shaoang Li, Feng Wu, Xiangyang Li
ICLR 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments have three main parts: Experiment (1) Evaluate our approach on three classical MILP problems and three challenging MILP problem benchmarks from diverse application areas. Experiment (2) Perform carefully designed ablation studies to provide further insight into TRGNN. Experiment (3) Test whether TRGNN can generalize to instances significantlly larger than those seen during training. |
| Researcher Affiliation | Academia | Sijia Zhang, Shuli Zeng, Shaoang Li, Feng Wu , Xiang-Yang Li School of Computer Science and Technology, University of Science and Technology of China EMAIL EMAIL |
| Pseudocode | Yes | Algorithm 1 General Node Selection Procedure Require: Node list L, parent node bounds, probability Prob of heuristic integer solution calculation 1: for each node P in L do 2: Select node P according to the node selection strategy. 3: Update the lower bound of P, LB(P) = lbparent, where lbparent is the lower bound of parent node of P. 4: Solve the LP relaxation of node P, getting the solution Sol1 and objective function value Obj1. 5: Update the upper bound of P, UB(P) = Obj1. Propagate the updated upper bound upward. 6: if Obj1 LB(P) then 7: Prune node P. 8: else 9: if Sol1 is an integer solution then 10: Update the lower bound of P, LB(P) = Obj1. Propagate the updated lower bounds upward. 11: end if 12: Call the heuristic to calculate an integer solution with probability Prob, resulting in Sol2 and Obj2. 13: if Obj2 > LB(P) is an integer solution then 14: Update the lower bound of P, LB(P) = Obj2. Propagate the updated lower bounds upward. 15: end if 16: Branch at node P and add the children nodes to list L. 17: end if 18: end for |
| Open Source Code | No | The codes are modified from Labassi et al. (2022). The model implemented in Py Torch (Paszke et al., 2019) and optimized using Adam (Kingma & Ba, 2014) with training batch size of 16. The paper does not provide an explicit statement or a link for the open-sourcing of their own code (TRGNN). |
| Open Datasets | Yes | (1) Synthetic datasets comprise three widely used synthetic MILP problem benchmarks: Fixed Charge Multicommodity Network Flow (FCMCNF) (Hewitt et al., 2010), Maximum Satisfiability (MAXSAT) (Ans otegui & Gab as, 2017) and Generalized Independent Set (GISP) (Colombi et al., 2017). (2) Real-world datasets comprise MIK (Atamt urk, 2003), CORLAT (Gomes et al., 2008), and the Anonymous problem, inspired by a large-scale industrial application (Gasse et al., 2022). |
| Dataset Splits | Yes | We generate extensive synthetic datasets, consisting of 10,000 training samples and 1,000 test samples. From these, we randomly select 1,000 samples for the SVM, Rank Net, and GNN models training and 100 samples for testing within each problem. Additionally, we generate 1,000 larger-scale datasets, randomly selecting 50 samples from each to evaluate the transfer capability of our method. For the real-world dataset, each problem set is split into training and test sets with 80% and 20% of the instances. |
| Hardware Specification | Yes | The training process is conducted on a single machine that contains eight GPU devices(NVIDIA Ge Force RTX 4090) and two AMD EPYC 7763 CPUs. |
| Software Dependencies | Yes | Throughout all experiments, we use SCIP 8.0.4 (Bestuzheva et al., 2021) as the backend solver |
| Experiment Setup | Yes | We denote a parameter m to normalize the path switching steps. The path switching steps are denoted as s, the normalized reward for path switching steps is Rs = s m 1. In this function, if the path switching steps are less than m, Rs > 0; otherwise, the model receives a penalty. The value of m depends on the size of the problem. We use m = 15 for the FCMCNF, Max SAT, GISP, MIK and CORLAT datasets and m = 50 for the Anonymous dataset. Moreover, we take the weight values w1 = w2 = w3 = 1. ... we set n = 5 ... training batch size of 16. ... the learning-based node selection method is only called before the primal bound is updated four times. After four updates, we switch to the Breadth-First Search method. |