Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters

Thanks for your valuable feedback and suggestions.

Response to Weakness 1

Baselines: We will clarify in the introduction that our method primarily focuses on primal heuristics. However, we believe that comparing our approach with general MILP solvers like SCIP and Re_Tuning is still essential. These solvers are commonly used benchmarks within the field. For instance, heuristic methods by Han et al. and Huang et al. also use SCIP as one of their baseline comparisons.

Response to Weakness 2 and Question 1

Warm start baseline: The baseline Re_Tuning includes a similar approach. It specifically addresses cases with minor problem changes by incorporating heuristic design methods in various SCIP solving modules. In the presolving module, it stores all past feasible solutions and constructs partial solutions based on variable-value pairs that are consistent across a high percentage of previous solutions. In SCIP, a heuristic called completesol captures these hints to find feasible solutions by solving a sub-MIP.

SCIP-WS: In Appendix C.7, we report the effectiveness of "SCIP-WS", which solely utilizes the solution hints from Re_Tuning to guide the completesol heuristic, without employing other heuristic methods.

SCIP settings: The SCIP setup uses all default settings without disabling any features, including the default preprocessing and reoptimization modules.

Response to Weakness 3

Ablation experiment: We conduct an ablation experiment using Re-GNN for initial solution prediction in LNS and traditional GNN with the Thompson Sampling (TS) algorithm. We report the average gap_rel, where "inf" means no feasible solution was found. Re-GNN improves performance over traditional GNN in the LNS framework. The method combining traditional GNN with TS also quickly finds feasible solutions. The combined approach, VP-OR, achieves the best results across all datasets.

Response to Weakness 4

We expand our experiments to include large-scale MILP experiments and add a comparison with the ML-guided LNS method of Huang et al. (ConPas).

Large-scale MILP experiments: We generate large-scale datasets IS and CA using the code from Gasse et al., consistent with those used by Han et al. The Gurobi and SCIP solvers could not reach an optimal solution within 3600 seconds for these instances. We run Gurobi for 3600 seconds to record the incumbent solution. For evaluation, we impose a 30-second time limit and update the incumbent solution if a better one is found. VP-OR achieves more significant acceleration than PS and ConPas during the early stages of solving on both Gurobi and SCIP.

CA:

IS:

Response to Question 2

The term "end-to-end" is based on Han et al.'s classification of ML efforts for optimization. End-to-end learning refers to using machine learning to predict solutions based directly on the input problems and their final results. This approach leverages the capabilities of machine learning to facilitate efficient problem-solving by directly linking the problem's structure and solution values. Our method can also be considered end-to-end.

Response to Question 3

The loss function: We use a categorical cross-entropy loss function to train the GNN. For binary variables, the model predicts probabilities that are directly compared with the actual binary values to compute the optimal solution. For integer and continuous variables, they are first represented as 8-bit binary numbers using the method described in Section 4.1.2, which involves using the binary representation of the logarithmic value. These binary representations are then used as labels and compared with the predicted probabilities.

The sampling step: We do not propagate a gradient through the sampling step. We prioritize speed in each iteration and online training and inference during the sampling process would negatively affect solving efficiency.

Thanks for your valuable feedback and suggestions.

Response to Comment 1

There is no contradiction in the statement. Reusing branching strategies and adjusting solver parameters improve efficiency by saving time on generating the branching strategy and by enabling the solver to find better solutions faster. They focus on improving the way the problem is solved, not changing its size.

Response to Comment 2

The claim of the prediction accuracy: Table 10 in the appendix provides evidence for our statement. We will move this table to the main text in the final version. It shows the number of incorrectly predicted variables for traditional Graph Neural Networks (GNN) and our approach (Re_GNN). In datasets bnd_2 and bnd_3, the table indicates that more than one-third of the continuous variables were predicted incorrectly.

Response to Comment 3, 4

We will restructure the paper to separate the components into distinct paragraphs. Our approach builds upon the framework by Han et al., with modifications mainly in feature extraction and prediction algorithms for integer and continuous variables. The GNN architecture and training method remain the same as theirs. For data generation, we utilize the datasets provided by the existing reoptimization competition.

We use a categorical cross-entropy loss function to train the GNN. For binary variables, predictions are compared directly with actual binary values for computing the optimal solution. Integer and continuous variables are represented as 8-bit binary numbers following the method in Section 4.1.2, which uses the binary representation of the logarithmic value. These binary representations serve as labels for comparison with predicted probabilities.

The use of binary representation and logarithmic transformation addresses practical computational constraints. In our datasets, maximum integer values exceed 100,000, which would require at least 18 bits for binary representation. Using a direct approach without these transformations during testing resulted in out-of-memory errors due to large output dimensions. The logarithmic transformation allows us to represent integers as 8-bit binary numbers, distinguishing potential value ranges without predicting exact values.

Response to Comment 6, 8

Large-scale experiments: Please refer to our Response to Reviewer MNmC's Question 1 for details.

Response to Comment 7

Ablation experiment: Please refer to our Response to Reviewer MNmC's Question 2 for details.

Response to Comment 9, Question 2

1. We evaluate the accuracy of predicted bounds for integer and continuous variables as follows: if the optimal value of a variable lies within the predicted lower and upper bounds, the predicted bounds are considered accurate; otherwise, they are not.

2. Continuous and integer variables are treated similarly, with the key difference being that continuous variables are rounded during preprocessing.

To evaluate how tight these bounds become after training and across different optimization stages, we use I_o and C_o to denote the average difference between original upper and lower bounds for integer and continuous variables, respectively. I_p and C_p represent the average predicted bounds gap for integers and continuous variables. In cases where there are no integer or continuous variables in a dataset, we use 'NA' as a placeholder.

Response to Comment 10

The '-' symbol does not indicate empty rows. Instead, it means that no feasible solution was found during testing, resulting in a gap of infinity. To prevent confusion, we will adjust the '-' to '>10.0' in the final version.

Response to Question 3

Each instance uses only one GPU for both training and inference.

Response to Question 4

Our relaxation mechanism addresses infeasible instances by dividing the fixed variables into ten groups and subsequently solving each without these variable sets. When a feasible solution cannot be found, we repeatedly apply the relaxation mechanism, building upon previous relaxations. Each iteration of this mechanism reduces the number of fixed variables. With enough iterations, the variables causing conflicts with the constraints are filtered out.

Thanks for your valuable feedback and suggestions.

Response to the Question 1

Large-scale MILP experiments: We expand our experiments to include large-scale MILP experiments with more instances (200 for training and 100 for testing) and add a comparison with the ML-guided LNS method of Huang et al.[2] (ConPas). The results are reported for both Gurobi and SCIP. We generate large-scale datasets IS and CA using the code from Gasse et al.[3], consistent with those used by Han et al.[1] The Gurobi and SCIP solvers could not reach an optimal solution within 3600 seconds for these instances. We run Gurobi for 3600 seconds to record the incumbent solution. For evaluation, we impose a 30-second time limit and update the incumbent solution if a better one is found. VP-OR achieves more significant acceleration than PS[1] and ConPas[2] during the early stages of solving on both Gurobi and SCIP.

CA:

IS:

Response to the Question 2

Ablation experiment: We conduct an ablation experiment using Re-GNN for initial solution prediction in LNS and traditional GNN with the Thompson Sampling (TS) algorithm. We report the average gap_rel, where "inf" means no feasible solution was found. Re-GNN improves performance over traditional GNN in the LNS framework. The method combining traditional GNN with TS also quickly finds feasible solutions. The combined approach, VP-OR, achieves the best results across all datasets.

Response to the Question 3

Re-GNN includes traditional features like variable coefficients in the objective function, variable types, and initial bounds. Additionally, it captures features from leaf nodes where the best solution was found during solving. For each leaf node, it records the local bounds of each variable, the LP relaxation solution, and whether each variable is basic in this solution. These data come naturally from the solving process in SCIP and Gurobi without extra computation. All the features are listed in Table 5.

Reference:

[1] Han Q, Yang L, Chen Q, et al. A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming[C]//The Eleventh International Conference on Learning Representations.

[2] Huang T, Ferber A M, Zharmagambetov A, et al. Contrastive predict-and-search for mixed integer linear programs[C]//Forty-first International Conference on Machine Learning. 2024.

[3] Gasse M, Chételat D, Ferroni N, et al. Exact combinatorial optimization with graph convolutional neural networks[J]. Advances in neural information processing systems, 2019, 32.

Thanks for your valuable feedback and suggestions.

Response to the Question 1

Generalization: In our tests, we indeed observed instances where the GNN model made errors in predicting variables. To address this challenge, approaches like those by Han et al.[1] and Huang et al.[2] leverage an LNS framework and our VP-OR uses sampling methods. These strategies introduce a level of tolerance for prediction errors, enhancing the model's applicability and extending its utility to different problem instances.

Large-scale MILP experiments: We expand our experiments to include large-scale MILP experiments with more instances (200 for training and 100 for testing) and add a comparison with the ML-guided LNS method of Huang et al.[2] (ConPas). The results are reported for both Gurobi and SCIP. We generate large-scale datasets IS and CA using the code from Gasse et al.[3], consistent with those used by Han et al.[1] The Gurobi and SCIP solvers could not reach an optimal solution within 3600 seconds for these instances. We run Gurobi for 3600 seconds to record the incumbent solution. For evaluation, we impose a 30-second time limit and update the incumbent solution if a better one is found. VP-OR achieves more significant acceleration than PS[1] and ConPas[2] during the early stages of solving on both Gurobi and SCIP.

CA:

IS:

Response to the Comment 1

Definition of "gap_abs" and "gap_rel": For the evaluation, we first solve the problem without a time limit and record the optimal solution’s objective value as OPT. Then, we apply a time limit of 10 seconds for each method. The best objective value obtained within the time limit is denoted as OBJ. We define the absolute and relative primal gaps as: gap_abs=|OBJ-OPT| and gap_rel= |OBJ-OPT| / ( |OPT|+$10^{-10}$ ), respectively.

The reason some methods show a 0.00 relative gap but still have a non-zero absolute gap is due to the rounding approach used in calculating "gap_rel". We retain two decimal places for "gap_abs" and "gap_rel", so when the relative error is sufficiently small (less than 0.004), the error rounds to 0.00, although a minor absolute error may still exist.

Response to the Comment 2

Yes, the 10-second evaluation does include both the model inference and refinement iterations. We will explicitly state this in the final version to ensure clarity.

[1] Han Q, Yang L, Chen Q, et al. A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming[C]//The Eleventh International Conference on Learning Representations.

[2] Huang T, Ferber A M, Zharmagambetov A, et al. Contrastive predict-and-search for mixed integer linear programs[C]//Forty-first International Conference on Machine Learning. 2024.

[3] Gasse M, Chételat D, Ferroni N, et al. Exact combinatorial optimization with graph convolutional neural networks[J]. Advances in neural information processing systems, 2019, 32.