Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Authors: Sijia Zhang
Shuli Zeng
Shaoang Li
Feng Wu
Shaojie Tang
Xiangyang Li
Venue: ICML 2025 poster (2025)
Keywords: Mixed Integer Linear Programming; reoptimization;
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: This paper introduces VP-OR, a two-stage reoptimization framework for MILP with dynamic parameters. It uses  GNN for variable prediction and Thompson Sampling for refining solutions,  finding better solutions under strict time limits.

Abstract: Many real-world applications, such as logistics, routing, scheduling, and production planning, involve dynamic systems that require continuous updates to solutions for new Mixed Integer Linear Programming (MILP) problems. 
These systems often require rapid updates to their solutions to accommodate slight modifications in constraints or objectives introduced by evolving conditions.
While reoptimization techniques have been explored for Linear Programming (LP) and certain specific MILP problems, their effectiveness in addressing general MILP is limited. In this work, we propose a two-stage reoptimization framework for efficiently identifying high-quality feasible solutions. Specifically, we first utilize the historical solving process information to predict a high confidence solution space for modified MILPs, which is likely to contain high-quality solutions. Building on the prediction results, we fix a part of variables within the predicted intervals and apply the Thompson Sampling algorithm to determine which variables to fix. This is done by updating the Beta distributions based on the solutions obtained from the solver. Extensive experiments across nine reoptimization datasets show that our VP-OR outperforms the state-of-the-art methods, achieving higher-quality solutions under strict time limits.

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Sijia Zhang' Shuli Zeng' Shaoang Li
Feng Wu
Shaojie Tang² Kiang-Yang Li'
Abstract
and production planning (Dunke & Nickel, 2023; Cedillo- Robles et al., 2020), involve systems that change dynami- cally over time. Thus, throughout the continuous operation of such systems, it is required to compute solutions for new Mixed Integer Linear Programming (MILP) problems, which are similar to the previous instances but differ in some parameters in specific model elements such as objective functions, constraints, and variable bounds. Traditionally, each of these new MILP instances is solved from scratch, which overlooks the opportunity to leverage valuable infor- mation from the previously solved instances. This approach can be computationally expensive. Additionally, it chal- lenging to generate high-quality operational plans within a short timeframe for time-critical applications.
Many real-world applications, such as logistics, routing, scheduling, and production planning, in- volve dynamic systems that require continuous updates solutions for new Mixed Integer Linear Programming (MILP) problems. These systems often require rapid updates to their solutions to accommodate slight modifications in constraints or objectives introduced by evolving conditions. While reoptimization techniques have been ex- plored for Linear Programming (LP) and certain specific MILP problems, their effectiveness in ad- dressing general MILP is limited. In this work, we propose two-stage reoptimization framework for efficiently identifying high-quality feasible so- lutions. Specifically, we first utilize the histori- cal solving process information to predict a high confidence solution space for modified MII.Ps, which is likely to contain high-quality solutions. Building on the prediction results, we fix a part of variables within the predicted intervals and apply the Thompson Sampling algorithm to de- termine which variables to fix. This is done by updating the Beta distributions based on the solu- tions obtained from the solver. Extensive exper- iments across nine reoptimization datasets show that our VP-OR outperforms the state-of-the-ee methods, achieving higher-quality solutions under strict time limits.
Reoptimization techniques have been well-studied for the LP case (John & Yildınm, 2008) and heuristic algo- rithms for some special MILP problems, e.g.. the rail- way planning problem (Blair, 1998), general assignment problems (NAUSS, 1974) and other combinatorial prob- lems (Libura, 1996; 1991; Sotskov et al., 1995). However, these techniques have limited applicability to general MILPs. The current reoptimization techniques for general MILP in- stances (Ralphs & Güzelsoy, 2006; Ralphs al., 2010; Gamrath et al., 2015; Patel, 2024) can be divided into three categories: (1) reuse of historical optimal solutions (2) reuse of branch-and-bound trees (3) adjustment of parameters. The limitations of their approach are twofold. Firstly, the optimal solution from the original problem may no longer be valid for the new problem. This because the range of variable values for the optimal solution shift sig- nificantly, even with small modifications to the problem's parameters (Guzelsay, 2009). Secondly, reusing branching strategies and adjusting parameters primarily saves time on dicision-making within the branch-and-bour algorithm itself, such as selecting variables, generating heuristics, and constructing cutting planes. However, this approach does not reduce the overall size complexity of the problem.
1. Introduction
Traditional combinatorial optimization problems require finding solutions for a single instance. However, many real-world scenarios, such as system control (Marcucci & Tedrake, 2020), railway scheduling (Zhang et al., 2020)
'School of Computer Science and Technology, University of Science and Technology of China 'Department of Management Science and Systems, State University of New York at Buffalo. Correspondence to: Xiang- Yang Li <xiangyangliee witpevaanngiuutt.eu..om Feng Wu <wufeng02 @ww...cdu.ut..........
Recently, there has been an increased interest in end-to-end problem solving that generate high-quality solutions for MII.Ps (Nair et al., 2020; Han et al., 2023; Khalil et al., 2022; Ye et al., 2023; 2024). Previously, Neural Diving (ND) (Nair et al., 2020) is proposed to generate a Bernoulli distribution for the solution values of binary variables. They employ a selectivenet (Geifman & El- Yaniv, 2019) to learn
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Lcrge-scale MILP
Initial Variable Prediction
Iterative Online Refinement
Unsolved MILP
Dipartite Graph
GNN Model
Update
B
maz c' x
A'220 2,EZEEZ
Input
Bin.
05
Marginal Probabilities
Solution
INT.
Historical
Solving Process
Probabilities to Select
Solver
Output
A SENNEE
CONT.
um
Vars.
Update B
Figure 1. Illustration our proposed two-stage reoptimization framework. Our approach first predicts a marginal probability of each binary variable and the feasible ranges of integer and continuous variables utilizing a graph neural network (GNN), and then employs the Thompson Sampling algorithm to iteratively select the variable to apply the interval.
which variables' predicted values to be fixed. The main disadvantage of ND is that fixing variables can lead to low- quality or infeasible solutions if the selectivenet fails to identify variables with inaccurate predictions. To mitigate the issue, current end-to-end methods (Han al., 2023; Ye et al., 2024; Huang et al., 2024) employ Predict-and- Search (PS) framework. They utilize large neighborhood search (LNS) (Carchrae & Beck, 2009) to explore solutions near the predicted values. These LNS-based approaches do not differentiate between variables predicted with greater accuracy. Instead, they predetermine the number of vari- ables to search around (controlled by hyperparameters) and uniformly apply uncertainty neighborhoods around these binary variables. These methods are not directly suited for reoptimization scenarios, which urgently require quickly ob- taining high-quality feasible solutions (Marcucci & Tedrake, 2020; Zhang et al., 2020). For example, instances in the "bnd 3' dataset from the reoptimization competition (Bolu- sani et al., 2023) cannot find primal solution within 300 seconds using these methods.
per iteration compared to traditional LNS strategies, as shown in Table 2. Different from ND and PS (Han et al., 2023), we utilize Thompson Sampling (Thompson, 1997) to differentiate between variables predicted with greater accuracy. We fix subset of variables apply the predic- tion intervals and iteratively improve the sampling based on solution results from each round.
Empirically, we compare VP-OR against the leading reop- timization method (Patel, 2024), two end-to-end machine learning- baselines (Nair et al., 2020; Han et al., 2023), solver SCIP (Bestuzheva et al., 2021) across nine reoptimization datasets. The results indicate that VP-OR outperforms the other methods in delivering highly accurate solutions under strict time limits. In addi- tion, we evaluate the performance over a longer duration, revealing that VP-OR converges more rapidly, achieving smaller primal gaps compared to the other methods.
and the
2. Related work
In this paper, we primarily focus on finding primal solutions for MILP problems with dynamic parameters. We propose a two-stage reoptimization framework, which consists of a Variable Prediction model and an Online Refinement module (VP-OR). We find that over 26.6% integer and con- tinuous variables cannot be accurately predicted if relying solely optimal solution values, shown in Table 10. To overcome this, we propose method to predict the bounds for these variables, leveraging historical branch-and-boul bound processes from previously solved instances. Inspired by the recent success for variable prediction (Han et al., 2023; Huang et al., 2024), VP-OR employs graph neural networks (GNNs) (Gori et al., 2005) analyze changes in problem structure and significantly improves the accuracy of variable predictions. To meet time-critical demands, the online re- finement module adopt a fixing strategy similar to ND (Nair et al., 2020), achieving solving times at least 10 times shorter
Reoptimization for MILPs Early methods (Ralphs & Güzelsoy, 2006; Ralphs et al., 2010) were primarily based on duality theory and focused on sequences of MILPs where only the right-hand side changes. These approaches lever- aged dual information obtained through primal algorithms to enable "warm starting", accelerating the resolution of subsequent problems. Subsequent research (Gamrath et al., 2015) extended these methods to handle broader scenarios, incorporating techniques such as reusing branch-and-bont bound trees. In these approaches, the modified problem is treated as a subproblem of the base problem, or, if only the objective function changes, the search can "continue" from the last known search boundary. Specifically, these methods use the leaf nodes of the base problem's 's branch-and-bound tree as starting points for solving the modified problem. Building this, more recent work (Patel, 2024) addressed even more complex reoptimization scenarios, where, apart from the
2

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
objective function but also other parameters-such as variable bounds, matrix coefficients, and constraint right-hand side values-can undergo upward or downward perturbations. In the approach, series of past solutions is preserved, allow- ing the method to reuse these solutions for the new problem. They also explore the reuse of branching strategies and the adjustment of parameters related to the cutting planes and heuristic algorithms, fine-tuning the solver's behavior to better tackle the modified problem. They primarily relied on heuristic adjustments, lacking the ability to predict the changes in optimal solutions.
optimality. They provide not only the optimal solution but also detailed records of intermediate computational steps, such as selected branches and basis variables at each node's s LP relaxation. These records can be strategically leveraged in the reoptimization algorithm to accelerate the solving process for the modified instances.
Bipartite graph for MILPs An MILP problem can be effectively represented as a weighted bipartite graph G (V U C, E) (Nair et al., 2020; Gasse et al., 2019). Each vertex in V corresponds to variable of the MILP, and each vertex in C represents a constraint. An edge (v,, 9)) connects a variable vertex Vi with a constraint vertex Cj if the variable is involved in the constraint. The edge set E E mxxxxe represents the edge features, where m and n denote the number of constraints and variables, respectively, and indicates the dimension of the edge attributes.
Prediction for integer variables. Many real-world scenar- ios that rely on reoptimization techniques naturally involve both integer and continuous variables. For example, pro- duction quantities in manufacturing are integers (Cedillo- Robles et al., 2020), while power levels in energy opti- mization problems are continuous variables (Yokoyama et al., 2002). Despite this, most existing end-to-end machine learning-based methods (Han et al., 2023; Khalil et al., 2022; Huang et al., 2024) primarily focus on predicting solutions for binary variables. Neural Diving (Nair et al., 2020) (ND) first proposed to represent integer variables in binary form and predict each bit's value. To address the issue of repre- senting integer variables with excessively many bits, ND considered the first few bits as the most significant during the solving process and introduced a hyperparameter to con- trol the maximum number of bits predicted for each variable. Building on ND, Ye et al. (2024) introduced generalized confidence threshold method. However, predicting each binary bit's actual value can lead to inaccuracies, causing overall prediction errors.
Online contextual thompson sampling. Thompson Sam- pling is a heuristic strategy used in decision-making scenar- ios like the multi-armed bandit (MAB) problem (Agrawal & Goyal, 2012; Zhao, 2022). This method is used for choos- ing actions according to their expected rewards, which are continuously updated using Beta probability distributions Beta( (a, 3) (Gupta & Nadarajah, 2004). The Beta distribu- tion forms a family of continuous probability distributions over the interval (0, 1). The probability density function (pdf) of a Bela (or, 33 distribution, where a > 0 and ,3 > O, r(a-8)
is given by: f(z; a, 3) r(a)r(()) x T(-) is the Gamma function. The mean of the Beta(a, B) distribution is a and as the parameters a and ,3 in- a+.3. crease, the distribution becomes more concentrated around the mean. The beta distribution is useful for Bernoulli re- wards because if the prior is a Beta(a, 33 distribution, then after observing a Bernoulli trial, the posterior distribution is simply Beta(a + 1,33) or Beta(a, 3 + 1), depending on whether the trial resulted in a success or failure, respec- tively.
(1 1:a1(11
==)811, where
3. Preliminaries
Mixed integer linear programming(MIIPP) Given a set of decision variables æ E IR"", the MILP problem formulated as follows:
min x
4. Methodology
s.t.
Ax 2 b, 1 S u, E (0. 13" 7 x Ra-p-q
In this section, we present the insights and details of our VP-OR framework. We start by utilizing the historical infor- mation to predict a feasible interval containing the modified problem's optimal solution in Section 4.1. Then, we em- ploy the Thompson Sampling algorithm to refine the solving space in Section 4.2. Figure I shows the overall procedure of our VP-OR framework.
where e E R" is the objective coefficients, A E gm is the constraint coefficient matrix, E Rm is the right-hand side vector, I, u E R" are the variable bounds.
Modified MILP problem. We consider scenarios similar to the previous reoptimization work (Patel, 2024), involving series of MILP instances based on MILP (historical instance) taken from a specific application. Each subse- quent instance (modified instance) is modified from the previous one with random perturbations and rotations to parameters such as the objective vector, constraints, and variable bounds. The previous instances has been solved to
4.1. Initial variable prediction
4. 1.1.1. GRAPH REPRESENTATION
The feature extraction process is divided into two parts: the historical instance and the modified instance. For the modi-
3

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Table 1. Comparison of variables across different types (binary. integer, and continuous) when using GNN-based predictions. Mispredicted variables represent those whose predicted bounds or values differ from the optimal solution.
variahle prediction accuracy for different datasets. This table presents the number of variahles and mispredicted
Var. num.
bnd_1
bnd 22
bnd_3 3
mat_1 1
obj.1 I
obj 2
rhs 1
rhs 2
rhs_3
binary var. mispredicted binary var.
2993.0
1457.0
1457.0
500.0
360.0
355.0
12510.0
500.0
500.0
8.2
6.7
4.5
37.4
5.6
0.2
64.3
0.0
0.0
integer
124.0
0.0
0.0
0.0
0.0
150.0
0.0
0.0
0.0
mispredicted integer var.
17.4
0.0
0.0
0.0
0.0
5.0
0.0
0.0
0.0
continuous var.
0.0
301.0
301.0
302
0.0
240.0
250.0
500.0
500.0
mispredicted continuous var.
0.0
0.0
2.0
0.0
0.0
16.8
0.0
1.6
4.7
fied instance, we represent it using classic bipartite graph structure (Gasse et al., 2019). For the historical instance, we aim extract additional historical solving information to predict how the optimal solution may change under small perturbations in the MILP.
lusani al., 2023), there are 27,710 variables but only 400 binary variables.
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. In the datasets, maximum integer values exceed 100,000, which would require at least 18 bits for binary representation. Us- ing direct approach without these transformations results in
In MILP, integer variables are often relaxed to continuous values to apply duality concepts. However, the dual problem from the relaxed problem may not directly reflect the rela- tionship between the optimal solution and constraints under integer restrictions. We address this challenge by leveraging a key property of branch-and-boundt trees: the final leaf node that yields the MILP optimal solution has the characteristic that its LP relaxation solution is also an integer solution. The Icaf node represents a subproblem of the original MILP, distinguished by the addition of series of branching con- straints. We include the feasible basic variables and dual solutions of the leaf node as features, which are commonly applied in LP sensitivity analysis (Higle& & Wallace, 2003), aiming to capture which variables and constraints are sen- sitive to parameter changes. This approach significantly improves the accuracy of binary variable predictions com- pared to traditional end-to-end solving methods, which rely solely on modeling the problem as a bipartite graph and optimal solution values. In Appendix E.5, we present the comparison results between the reuse of historical solving information and the traditional vanilla bipartite graph pre- dictions. The features used in the graph representation is detailed in Table 5 in Appendix A.
errors due to large output dimensions. Therefore, for integer and continuous variables, they are first represented as 8-bit binary numbers using the method deseribed in Appendix B, which involves using the binary representation of the logarithmic value. The use of binary representation and logarithmic transformation addresses practical computational constraints. These binary repre- sentations are then used as labels and compared with the predicted probabilities.
Prediction confidence processing. We apply the confi- dence threshold method (Yoon, 2022) to filter the predicted probabilitics and distinguish between confident and uncer- tain predictions. For the binary digits with high confidence, the binary digits are fixed to their predicted values. For un- certain binary digits (i.c., those with probabilities between 1 and 0.9), we allow them to vary between () and 1. We establish the upper and lower bounds of the predicted binary encoding by setting the uncertain binary digit to its maxi- mum value 1 for the upper bound and its minimum value 0 for the lower bound.
4.1.2. GNN-BASED INITIAL VARIABLE PREDICTION
Classic end-to-end approaches (Khalil et al., 2022; Han et al., 2023) are specifically designed for binary vari- ables and predict n-dimension vector (po(2) = M)) to represent the conditional
4.2. Iterative online refinement
1.2. OBSERVATION
1; I:M),..., probability of p binary variables. However, these methods can not work well in many real-world scenarios, which mainly contain integer and continuous variables. For in- stance, in the dataset named "'varymmar _matrix_nni .rss bounds" in the MIP Workshop 2023 Computational Competition (Bo-
We test the prediction accuracy of CNNN-based models on a variety of datasets, which were carefully selected to repre- sent different types of parameters, including variable bounds, objective function coefficients, matrix parameters, and right- hand side constraints. Table provides the number of vari- ables and the mispredicted variables for each dataset. The
4

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Table Comparison of the solving time (sccond) using variahle fixing and large neighborhood search (INSS) methods, with different percentages of variables (50% and 70%). For LNS methods, feasible solutions are searched around the predicted values for these variables. For variable fixing methods, these variables are set to the predicted values.
Solving time
bnd_st .1
bnd_s2
bnd x3
mat_s1
obj
obj_s2
rhs .1
rhs_s2
rhs_s3
SCIP original solving time
356.09
314.35
574.72
541.78
570.69
200.10
546.40
68.67
90.24
LNS (50% binary variables)
328.50
146.38
427.19
111.54
123.71
306.21
287.91
59.85
77.08
LNS (70% binary variables)
335.51
265.82
307.43
497.24
703.86
307.78
247.45
81.27
80.08
Fix 50% variahles (only binary)
17.61
13.44
77.83
0.60
65.61
5.71
9.99
29.00
25.13
Fix 70% variables (only binary)
4.92
6.46
32.94
0.38
4.22
3.08
5.42
13.78
12.41
Fix 50% variables (all)
3.87
2.76
7.42
0.57
49.65
0.24
2.71
3.97
8.73
Fix 70% variables (all)
0.71
2.44
4.02
0.37
1.04
0.23
0.47
3.53
4.18
results indicate that inaccuracies in predicted values are typ- ically concentrated in a small subset of the variables. This is especially evident with integer and continuous variables, where less than 14% of the ranges deviate from the true feasible regions.
search (LNS) methods. In cases where incorrect variable fixing caused infeasibility, we randomly select variables multiple times and compute the average time taken to find feasible solutions across these selections. The results show that we can increase the problem solving efficiency to 3-10 times by fixing only the binary variables when we add the estimated integer and continuous variables. It motivates us to choose variables based on the feedback of each solution, and gradually update the initial values of predictions based the solution values of the binary variables.
With this observation, it is reasonable to accelerate the solving process for MILP problems by fixing variables in the partial solution. To simplify the formulation, we denote the constraint space of the modified instance as: S = {I E 13, x 2 x R--9-9 (A + AA)æ 2 (b + Ab), (1 + AI) S x < (u+ + Au)}. Specifically, the sub-problem of an instance using the fixing strategy with the predicted binary value ह; the predicted lower bound and upper bound ū can be formulated as:
4.2.2. ONLINE VARIABLE FIXING STRATEGY
Our approach is based on a simplifying assumption com- monly used in prior work (Han et al., 2023) that treats each variable as independent of others. This assumption enables us to update the values of a and 3 separately for each vari- able. During the initial presolve phase, follow the ap- proach of previous reoptimization work (Patel, 2024) by pro- viding solutions from previous instances as hints to support the "completesol" heuristic method, effectively leveraging the historical solution as a warm start.
min ses
(c+ Ac)
(2)
where the learning-based constraint set S(i, I) is defined as: S(ž, I) {a E 13 i, E
2a x R"-p-g 24 nI <= <= j + 2....,n} n.. and f; represents the predicted probabil- ity for binary variables Tj, and I, and uij are the predicted lower and upper bounds for integer or continuous variables ry. Here, I is subset of {1, 21...... n), representing the set of selected related variables in the constraint set. However, for i E T, if & # x if 1, > 2 or vij < 27, where x; denotes the optimal value of the variable in the modi- fied problem, the fixing strategy may lead to suboptimal solutions or even infeasible sub-problems. Identifying the appropriate set I to avoid these inaccurate predictions is challenging, particularly when handling large-scale prob- lems where the search space is vast, and the number of variables is substantial.
Problem statement. We model our problem as stochastic multi-armed bandit (MAB) problem (Zhao, 2022). In the context of the solving process of MILP discussed, which variables to be apply the predicted values is analogous to an arm in a contextual MAB setup. At each round f, the corresponding variable set are fixed to their predicted values, which reduces the original problem to a subproblem. We then solve this subproblem and obtain a reward ra. E (00, 1}. If the solution obtained in this iteration improves upon all previous solutions, we set r', 1; otherwise, Ta, 0. The objective is to discover better solutions with as few iterations as possible, approaching the optimal solution ef- ficiently. This aligns with the typical MAB goal of maxi- mizing the expected total reward over a time horizon T, i.e., E [ To. where ag represents the arm played at time i, and the expectation is taken over the random choices of
Interestingly, through a number of experimental tests, as shown in the Table 2, we found that when fixing a portion of the variables, the solution time of the problem can become very short. For comparison, we included the solving times of the default SCIP and those obtained by large neighborhood
5

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Table 3. Number of solved problems within 10s time limit for each method across datasets.
Methods
bnd_1
b
bnd_3
obj_1
obj_2
mat_1
rhs_1
rhs.2
rhs_3
SCIP
5/5
0/5
0/5
5/5
5/5
5/5
5/5
5/5
5/5
ND
0/5
0/5
0/5
5/5
5/5
0/5
0/5
0/5
0/5
PS
5/5
0/5
0/5
5/5
5/5
5/5
5/5
5/5
5/5
Re.Tuning
5/5
3/5
3/5
5/5
5/5
5/5
5/5
5/5
5/5
VP-OR((Urr)
5/5
5/5
5/5
5/5
5/5
5/5
5/5
5/5
5/5
aj made by the algorithm.
solutions within the 10-second time limit. Experiment 2: Assess the quality of the feasible solutions obtained within the 10-second limit. Experiment 3: To provide a more intuitive comparison of solution convergence speeds, we plot the relative primal gap over time under larger time limit of 100 seconds.
We do not directly use the solution's objective value as the reward, as the reward may cause the model to favor solutions that are "good but not optimal", reducing the moti- vation for exploration. By rewarding only when the current solution is better than all previous ones, we can more clearly distinguish which arms lead to true improvements.
5.1. Experimental setup
We employ an iterative thompson sampling approach to re- fine solutions. Following the results from each iteration, we update the beta distributions of variables for the subsequent round of optimization. For binary variables, the prior dis- tribution is initialized as Beta(p; + 10-5, p; + 10 10-5), where p. represents the marginal predicted probability of the binary variable being fixed to 1. For integer and continuous variables, the prior is set as Beta(1, 1). The value 14, sam- pled from the Beta distribution, represents the probability of achieving better solution (i.e., obtaining r 1) by fixing binary variables to I or by imposing predicted bounds integer variables. We select the top a% of these variables based on their Pú values. The priors are updated according to the solving values for the unselected variables and based on whether the current solution improves for the selected variables. In our algorithm, we aim to avoid being trapped in local optima. To encourage exploration, given when the current solution performs worse than previ- ous iterations. Details of our thompson sampling algorithm are presented in Appendix C.
Benchmarks. We select 9 series of instances from the MIP Computational Competition 2023 (Bolusani et al., 2023) to evaluate our approach. Each series has 50 similar instances with one or more components changing across instances. These instances need SCIP to solve from 60 to 600 sec- onds. Depending on the series, one of the following input can vary: (1) objective function coefficients (obj-1, obj 2), (2) variable bounds (bnd_1, bnd_2, bnd_3), (3) constraint right-hand sides (rhs 1, rhs 2, rhs 3), (4) constraint coeffi- cients (mat_l.. Most of these series are based on instances from the MIPLIB 2017 benchmark library (Gleixner et al., 2021), which a well-known and widely used collection of benchmark problems in the field of MILP. They are fre- quently maintained and updated include diverse set of test problems sourced from various real-world applications and industries. Some of other series are collected from the real-world industrial use case and traditional problems. They are highly relevant to real-world reoptimization sce- narios. Due to limited space, please see Appendix F. for details of these datasets.
penalty is
We propose the relaxation mechanism to address infeasible instances, which is detailed in Appendix D. It divides the fixed variables into ten groups and subsequently solves each without these variable sets. When 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.
Training, Each dataset contains 50 instances. To facilitate the experiments, we pair the instances in groups of two, resulting in 25 groups, including 20 groups in the training set and 5 groups in the test set. The first instance in each group serves as the historical instance, for which interme- diate solving information required for feature extraction is pre-recorded. The specific features are detailed in the Ap- pendix A. All numerical results are reported for the test set. To further increase the number of test samples, we generate similar datasets using bnd. / as testing example, employ- ing a method consistent with that published by the compe- tition organizers. The results presented in Appendix E.8 are consistent with the tests shown in Table 4 of the main text. The model was implemented in PyTorch (Paszke et al.,
5. Experiments
Our experiments consist of three main parts: Experiment
1: Evaluate different methods on nine public reoptimization datasets, focusing on whether they can quickly find feasible
6

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Table 4. Policy evaluation the datasets, where "." represents cases where the method could not find feasible
solution. The best performance is marked in bold.
Methods
bnd 1
bnd
bnd 3
gap abs
gap rel
wins
gap abs
gap rel
wins
gap abs
gap rel
wins
SCTP
1974.20
0.16
1/5
ND PS
9665.20
0.81
0/5
Re Tening
1425.5
0.12
0/5
VP-OR(Ours)
299.40
0.02
4/5
40.20
0.11
5/5
28.60
0.06
5/5
Methods
mat
obj
obj 2
gap abs
gap
rel
wins
gap abs
gap rel
wins
gap abs
gap rel
wins
SCTP
14.10
0.23
0/5
11,40
0.00
0/5
626.52
0.39
0/5
ND PS
11.40
0.00
0/5
674.21
0.44
14.10
0.23
0/5
13,40
0.00
0/5
266. 10
0.21
0/5
Re. Re.Tuning
30.06
0.48
0/5
10,25
0.00
0/5
74.10
0.09
0/5
VP-OR(Ours)
10.09
0.16
5/5
3.28
0.00
5/5
0.64
0.00
5/5
Methods
rbs 1
rhs 2
rhs 3
gap abs
gap rel
wins
gap abs
gap rel
wins
gap abs
gap rel
wins
SCIP
173.08
0.50
0/5
12.29
0.00
0/5
15.01
0.00
0/5
ND
PS
67090.50
193.04
0/5
22.25
0.00
0/5
18.00
0.00
0/5
Re. Tuning VP-OR(Ours)
6.40
0.02
0/5
2.24
0.00
0/5
0.40
0.00
0/5
0.73
0.00
5/5
1.85
0.00
5/5
0.26
0.00
5/5
2019) and optimized using Adam (Kingma & Ba, 2014) with training batch size of 16. The training process is ducted on single machine that contains eight GPU devices (NVIDIA GeForce RTX 4090) and two AMD EPYC 7763 CPUs. Each instance uses only one GPU for both training and inference.
generate large-scale datasets IS and CA using the code from Gasse et al. (Gasse et al., 2019) and provide the results in Appendix 1010.
Evaluation metrics. For each instance, we first solve the problem without a time limit and record the optimal solu- tion's objective value as OPT. Then, we apply time limit of 10 seconds for each method. The best objective value ob- tained within the time limit is denoted OBJ. We define the following performance metrics: (1) Solve number: This is the most fundamental metric, tracking the number of times method successfully finds feasible integer solution within the 10-second time limit. (2) Gap: We define the absolute and relative primal gaps as: gap_abs = JOBJ - OPT and gap_rel |OBJ OPT]/[[PP]] 10-100011,,0 19), respectively, and use them as performance metrics. Clearly, smaller primal gap indicates stronger performance. (3) Wins: This metric counts the number of instances where each method achieved the closest solution to the optimal one within the same time limit, relative to the total number instances.
Baselines. We compare our approach against four baselines: the state-of-the-art open-source solver SCIP (Bestuzheva et al., 2021), ), the leading reoptimization method Re_ Tunnng (Patel, 2024), which won first place at the MIP Workshop 2023 competition (Bolusani et al., 2023) and does not rely on machine learning, and two GNN-based machine learning methods. In this paper, we compare ND (Nair et al., 2020) and PS (Han al., 2023) representative end-to-end approaches, both of which have gained significant popularity in recent years. PS is primarily based on the large neighborhood search (LNS) method, while ND utilizes a variable-fixin strategy for optimization. Please see Appendix E.2 for implementation details of these baselines. To provide more comprehensive comparison with our approach, we also provide results for SCIP using the historical solution as warm-start strategy in Appendix E.7. Due to the space limit, we
Throughout all experiments, we use SCIP 8.0.4 (Bestuzheva et al., 2021) as the backend solver, which is widely used in research of machine learning for combinatorial optimiza-

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
1.0
1.0
1.0
Ro. Tuning
Re. Tuning
Ro. Tuning
P5
P5
PS
Avg. gap Feree
(Our))
VP-OR(OUrs)
Avg. gap.app... rel
VP-OR[Ours)
0.6
Avg. gap
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.0
20
80
100
0.0
40
60
100
0.0
60
80
time(s) (s)
time(s)
time(s)
Figure Performance comparisons bnd_1, mat_1 rl where the y-axis is average relative primal gap; each plot represents one benchmark dataset.
tion (Chmiela et al., 2021; Khalil et al., 2022; Gasse et al., 2019). We keep all the other SCIP parameters to default and emphasize that of the SCIP solver's advanced features, such presolve and heuristics, are open.
average relative gap close to 0.1 in 10 seconds, while other methods struggle to provide feasible solutions within 100 seconds. Additionally. Re Tuning outperforms both SCIP and end-to-end prediction- methods on most datasets. ND and PS might be more suitable for problems that not time-sensitive and allow for longer solving times.
5.2. Experimental results
In our experiments, we include only one parameter: the percentage of fixed variables P. In this section, we present the results for P 0.7. Results for other values of P are provided in Appendix E.3.
Experiment 3. To provide a more intuitive comparison of solution convergence speeds, we plot the relative primal gap over time with a larger time limit of 100 seconds in Figure 2, highlighting how our approach converges com- pared other methods. We observe that VP-OR is more suitable for scenarios that require rapidly obtaining high- quality solutions in the short term. It converges quickly to find high-quality feasible solutions in the early stages of solving, but in the global scope, we also found that our method may encounter the possibility of getting stuck at suboptimal solutions. While Re Tuning and LNS also show potential, it's noteworthy that in certain cases, SCIP per- forms better than some of the optimization methods. Due to space constraints, only present the results from three datasets in this section, with additional results pro- vided in Appendix E.4.
Experiment 1. The results in Table 3 show how each method performs under the 10-second time constraint to find a feasible solution, which reflects the real-world need for quickly obtaining high-quality reoptimization solu- tions (Marcucci & Tedrake, 2020; Zhang al., 2020). We observe that only method, VP-OR successfully found feasible solutions across all datasets within the time limit. The reoptimization method, Re Tuning, also performed rel- atively well compared to other methods. This improved performance can be attributed to its use of warn-starting with solutions from previous instances and parameter tuning using historical solving information.
We evaluate the quality of the best fea- sible solutions found by different methods within the 10- second time limit. The evaluation is conducted across vari- ous datasets, with performance measured by absolute gap (gap_abs), relative gap (e),,rel), and the number of wins (wins), where wins indicate the number of instances for which a method achieves the best solution. The results are shown in Table 4, where "." represents cases where the method could not find feasible solution. In terms of wins and eap_rel, VP-OR surpasses all baseline methods. VP-OR performs exceptionally well in scenarios involving changes to variable bounds, matrix coefficients, and constraint right- hand sides. Specifically,, in datasets where variable bounds are altered (c.g., 2, and bnd_3). VP-OR achieves the
Experiment 2.
6. Conclusion
This paper proposes VP-OR, two-stage reoptimization framework for MILPs with dynamic parameters. VP-OR first trains GNN model to predict the marginal probability of each binary variable and the feasible ranges of integer and continuous variables in the modified MILP instance. Further, the Thompson Sampling algorithm employed to iteratively select which variables apply the predicted in- tervals. Experimental evaluations demonstrate that VP-OR significantly improves the solution quality in the reoptimiza- tion setting under very strict time limits over the baselines. We anticipate and encourage further efforts to extend the applicability of VP-OR in ultra- scenarios.
8

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Acknowledgements
Carchrae, T. and Beck, C. Principles for the design of large neighborhood search. Journal of Mathematical Modelling and Algorithms, 8(3):245-270, 2009.
The research is partially supported by China National Natural Science Foundation with No. 62132018, "Pio- neer" and "Leading Goose" R&D Program of Zhejiang". 2023C01029, the University Synergy Innovation Program of Anhui Province with No. GXXT-2019-024, and the USTC Gumpeng-Ascent Scientific and Educational Innovation Ex- cellence Center.
Cedillo-Robles, J. A., Smith, N. R., González-Raairee G., Slono--Stccker, J.,
J., and Askin, R. G. A production planning milp optimization model for manufacturing company. In International Conference of Production Research-Americat pp. 85-96. Springer, 2020.
Impact Statement
Chmiela, A., Khalil, E., Gleixner, A., Lodi, A., and Pokutta, S. Learning to schedule heuristics in branch and bound. Advances in Neural Information Processing Systems, 34: 24235-24246, 2021.
This paper presents work whose goal is advance the field of machine learning for combinatorial optimization. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Dunke, F. and Nickel, S. Exact reoptimisation under grad- ual look-ahead for operational control in production and logistics. International Journal of Systems Science: Op-
References
erations & Logistics, 10(1):2141590, 2023.
Agrawal, S. and Goyal, N. Analysis of thompson sampling for the multi-armed bandit problem. Conference on learning theory, pp. 39-1. JMLR Workshop and Confer- ence Proceedings, 2012.
Gamrath, G., Hiller, B., and Witzig, J. Reoptimization tech- niques for mip solvers. In Experimental Algorithms: 14th International Symposium, SEA 2015, Paris, France, June 29-Jul) 1, 2015, Proceedings 14, pp. 181-192. Springer, 2015.
Angulo, G., Ahmed, S., and Dey, S. Improving the integer I-shaped method. INFORMS Journal on Computing, 28 (3):483-499) 2016.
Gasse, M., Chételat, D., Ferroni, N., Charlin, L., and Lodi, A. Exact combinatorial optimization with graph convolu- tional neural networks. Advances in neural information processing systems, 32, 2019.
Baugh, C. R. and Wooley, A two's complement paral- lel array multiplication algorithm. IEEE Transactions on computers, 100(12):1045-1000 1973.
Geifman, Y. and EI- Yaniv,,, R. Selectivenet: A deep neural network with an integrated reject option. In International conference machine learning, pp. 2151-2159. PMLR, 2019.
Bestuzheva, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doommalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., Gouwwal, I.., Graczyk, C., Halbig, K., Hoen, A., Hojny, C., van der Hulst, R., Koch, T., Lübbecke, M. Maher, S. J., Matter, F., Mühmer, E., Müller, B., Pfetsch, M. E., Rehfeldt, D., Schlein, S., Schlösser, F, Serrano, F., Shinano, Y., Sofranac, B., Turner, M., Vigerske, S., Wegscheider, F., Wellner, P., Weninger, D., and Witzig, The SCIP Optimization Suite 8.0. Technical report, Optimization Online, December 2021. URL wine.ii... org/ html.
Gleixner, A., Hendel, G., Gamrath, G., Achterberg, T. Bastubbe, M., Berthold, T., Christophel, P., Jarck, K., Koch, T., Linderoth, J., et al. Miplib 2017: data-driven compilation of the 6th mixed- mixed-integer programming li- brary. Mathematical Programming Computation, 13(3): 443-490, 2021.
Gori, M., Monfardini, G., and Scarselli, F. A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks, 2005., volume 2, pp. 734. IEEE, 2005.
http:/ http://www. wwt.oooatttit..................t DE HTMML2021/12//
Blair, C. Sensitivity analysis for knapsack problems: A negative result. Discrete Applied Mathematics, 81(1-3): 133-139, 1998.
Gupta, A. K. and Nadarajah, S. Handbook of beta distribu- tion and its applications. CRC press, 2004.
Guzelsoy, M. Dual methods mixed integer linear pro- gramming. Lehigh University PhD, 2009.
Bolusani, S., Besançon, M., Gleixner, A., Berthold, T., D' A'mbrosi,,, C., Muñoz, G., Paat, J., and Thomopulos, D. The MIP Workshop 2023 computational competition on reoptimization, 2023. URL http: htap:///axxivv aaraiivdoo org/ abs/2311 14834.
Han, Q., Yang, L.,, Chen, Q., Zhou, X., Zhang, D., Wang, A., Sun, R., and Luo, X. A gnn-guided predict-and- search framework for mixeeeintteger linear programming.
9

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
In The Eleventh International Conference on Learning Representations, 2023.
deep learning library. Advances in neural information processing systems, 32, 2019.
Higle, I.. and Wallace, S. W. Sensitivity analysis and uncertainty in linear programming. Interfaces, 33(4): 53-60, 2003.
Patel, K. K. Progressively strengthening and tuning mip solvers for reoptimization. Mathematical Programming Computation, pp. 1-29, 2024.
Huang. T., Ferber, A. M., Zharmagambetov, A., Tian, Y., and Dilkina, Contrastive predict- sedlict-and-seee search for mixed integer linear programs. In Forty-first International Con- ference Machine Learning, 2024.
Ralphs, T. and Güzelsoy, M. Duality and warm starting in integer programming. In The proceedings of the 2006 NSF design, service, and manufacturing grantees and research conference, 2006.
Jiménzz-Cordero, A., Morales, M., and Pineda, Warm- starting constraint generation for mixed-integer optimiza- tion: A machine learning approach. Showledge-Basee Systems, 253: 109500, 2022.
Ralphs, T., Güzelsoy, M., and Mahajan, A. Sym- phony 5.2. 3 user's manual. Online: www. coin-or.
orgloondud//inryySYPPPON 2010.
Sotskov, Y. N., Leontev, V. K., and Gordeev, E. N. Some con- cepts of stability analysis in combinatorial optimization. Discrete Applied Mathematics, 58(2):169-190, 1995.
John, and Yıldırı,, E. A. Implementation of warm-start strategies in interior-point methods for linear program- ming in fixed dimension. Computational Optimization and Applications, 41 (112)1151-83, 2008
Tanner, M. W. and Ntaimo, L. lis branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation. European Journal of Oper- ational Research, 207(1):290- 2010.
Khalil, E. B., Morris, C., and Lodi, A. Mip-gnn: A data- driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 36, pp. 10219-10227, 2022.
Thompson, M. Theory of sample surveys, volume 74. CRC Press, 1997.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv: httl::/422..000 412.6980, 2014.
Ye, H., Xu, H., Wang. H., Wang, C., and Jiang, Y. Gnn&gbdt-guide fast optimizing framework for large- scale integer programming. In International Conference on Machine Learning, pp. 09864-39878 PMLR, 2023.
Libura, M. Sensitivity analysis for minimum hamiltonian path and traveling salesman problems. Discrete Applied Mathematics, 30(2-3):197-211 1991.
Ye, H., Xu, H., and Wang, Light-milpope Solving large- scale mixed integer linear programs with lightweight op- timizer and small-scale training dataset. In The Twelfth International Conference on Learning Representations, 2024.
Libura, M. Optimality conditions and sensitivity analysis for combinatorial optimization problems. Control and cybernetics, 25: 168-1180, 1996.
Marcucci, T. and Tedrake, R. Warm start of mixed-integer programs for model predictive control hybrid systems. IEEE Transactions on Automatic Control, 66(6):2433- 2448, 2020.
Yokoyama. R., Hasegawa, Y.. and Ito, K. milp decompo- sition approach to large scale optimization in structural design of energy supply systems. Energy Conversion and Management, 43(6):771-799) 2002.
Nair, V., Bartunov, S., Gimeno, F., Von Glehn, L,, Li- chocki, P., Lobov, I., O'Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., al. Solving mixed in- teger programs using neural networks. arXiv preprint 11X1292012.13349, 2020.
Yoon, T. Confidence threshold neural diving, arXiv preprint arXi::2202.07506, 2022.
Zhang, Y., Zhong, Q. Yin, Y., Yan, X., and Peng, Q. A fast approach for reoptimization of railway train platforming in case of train delays. Journal of advanced transporta- tion, 2020(1):5600)) 2020.
NAUSS, M. PARAMETRIC INTEGER PROGRAMMING. University of California, Los Angeles, 1974.
Ntaimo, L. Disjunctive decomposition for two-stage stochas- tic miixrd-binary programs with random recourse. Opera- tions research, 58(1):229-24 2010.
Zhao, Q. Multi-armed bandits: Theory and applications to
online learning in networks. Springer Nature, 2022.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L.,, et Pytorch: An imperative style, nigf-peee
10

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
A. More details of graph features.
The feature extraction process is split into two parts: the historical instance and modified instance. For the historical instance, we extract a richer set of graph features, including intermediate solving information. For the modified instance, we focus on structural information as Gasse et al. (2019). A list of the features used in our graph representation of the historical instance is detailed in Table 5.
Table 5. Description of the constraint, variable and edge features in our graph representation the historical instance.
Category
Feature
Description
lb
Original lower bound.
ub
Original upper bound.
objective coeff
Objective coefficient.
Type (binary, integer and continuous) as one-hot encoding.
var type
variable vertex
Lower bound of the leaf node which contains the optimal solution.
leaf_Ib
Upper bound of the Icaf node which contains the optimal solution.
leaf_ub
depth
Depth of the leaf node.
estimate
Estimate value of the leaf node.
If the variable is a basic variable in the LP relax of the leaf node.
isBasic var
Variable value in the optimal solution.
optvalue
constraint edge
coef
Constraint coefficient.
rhs
Right-hand side of the constraint.
constraint vertex
Constraint type feature (eq. geq) as one-hot encoding.
cope
If the constraint is a basic vector in the LP relax of the leaf node.
isBasic.coms
B. More details of logarithmic transformation
To reduce the dimensionality of integer variables, we apply a logarithmic transformation before converting the integer values into binary representations. This is suitable for our problem because we only focus on the prediction interval to reduce problem scales but do not need to predict an accurate value for continuous and integer variables. In this process, the integer values can potentially be negative. While two's complement is typically used to represent negative numbers in binary form (Baugh & Wooley, 1973), is less intuitive for tasks that involve magnitude interpretation, such logarithmic transformations. Instead, we introduce sign bit (0, 1} to separately capture the sign of the variable, making the magnitude and sign easier to handle. Specifically, we record the optimal value i; of the variable x; in the historical instance, we calculate its logarithmic scale and binary sign bit as follows:
00 if S 10-5 otherwise.
b(v:) bin (Llog2(1u) + 1)]),

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
where the vector b(b;)) represents the binary representation of the logarithmic value of v/ prefixed by the sign bit 8, and bin(.) denotes the binary conversion.
C. More details of thompson sampling algorithm
Algorithm Overall thompson sampling framework.
Input:
Predicted marginal probabilities p, for binary variables Ti,
Predicted bounds for continuous/integer variables z--- Initialize prior distributions:
ag 33 Beta p + 10 10-3
p; 1) for binary variables,
ag. ~ Beta(1, (1, 1) for continuous/integer variables.
for each time step = 1,2, 2, do
Sample μ4 Beta (B,) for all binary variables
Sample (4 ~ j 83) for all continuous/integer variables æj
Select Variables:
Rank and select the top a% for binary and continuous/integer variables
Fix Selected Variables:
For binary variables, fix values using Bernoulli distribution with probability μ4:
For continuous/integer variables, apply predicted bounds Solve subproblem with selected variable values to obtain solution and objective 25 Update Parameters:
if 21 is better than the best objective value 2 from previous iterations then
Update values of a, /3 for variables (detailed in Algorithm
2t
end if
if solution becomes infeasible then Apply relaxation mechanism (detailed in Algorithm 3
end if end for
The Parameter update process algorithm is designed to update the parameters of the pior distributions for binary and continuous/integer variables based on the outcomes of the current solution. The goal is to refine these parameters to improve the performance of the Thompson Sampling approach in subsequent iterations. We adjust our fixing strategy using the Beta distribution parameters, a and B. The mean of the Beta 3) distribution is -a a+B3 As these parameters increase, the distribution becomes more concentrated around the mean. With prior of Beta(a, 3), the posterior updates to Beta(a + 1, B) or Bela(o, / + 1).
In each iteration, we fix a percentage a% of the variables. When we find better solution, we update the Beta distribution for the remaining 1-a% of unfixed variables based on this new solution. We also compare the current strategy to the one from the previous round that gave the best solution. If a variable was fixed before but left unfixed in the current iteration, it indicates the previous strategy limited the solution quality. We update the Beta distributions for these variables to reflect this. In the next round, we resample the fixing strategy using these updated Beta distributions.
Update o, 3 for binary variables. For binary variables v;, i E { PP), we rank variables based on min(44, 1 - 1-4)). selecting the lowest a%, and sample fixed values from the Bernoulli distribution with probability μ4: At each iteration f, the priors for unselected binary variables are updated based on their observed outcomes: For unselected binary variables, we set a; a, + 1 when x; and set B, 3, + 1 when z; 0. For selected binary variables, if the current solution æ, better than the previous best 2; compare the set of selected variables a with the previously best set a;_ For variables where the current value is but was 0 in a;_1 (or was not selected), we set or as + 1. If the current value is 0. and it was
1 in -i (or was not selected), we set B 3, + 1.
Update a, 33 for integer and continuous variables. For integer and continuous variables, we select the top a% of these variables based on their Hy values and apply the predicted upper and lower bounds. The priors for continuous/intger variables are updated as follows: For unselected variables, if the variable's ss actual value in the solution falls within the
12

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
predicted bounds, set a O3 + 1. If it does not satisfy the predicted bounds, set 3, By For selected variables, when the current solution 2; is better than the previous best -; (i.e., rt 1), compare the set of selected variables ds and the previously best set a;-1. If z; was unselected in but was selected in d;-1, set ßJ Bj 1. In contrast, if variable žj was selected in but not in a no immediate conclusion about its benefit can be drawn, since the objective is to rule out incorrect bound predictions.
Algorithm The parameter update process algorithm.
Input: Current solution Tt, Best solution x" from previous iterations, Best objective value x² if 2, is better than then
Set rt- =
Update the best solution x 2t
Update priors for binary variables i:
for each unselected binary variable do if 2; = 1 then
a; - 0; +
else
B, - B, + end if
end for
for each selected binary variable do
if x; = and x= 0 then
a, < 0; +
else if r; = 0 and x² = 1 then
B. < Bg +
end if
end for
Update priors for continuous/integer variables j: for each unselected continuous/integer variable do
if æj violates predicted bounds then
By + Bg + else
a,- + -- +1
end if
end for for each selected continuous/integer variable j do if æ. wasn't ' selected in the previous best solution " then
- +1
end if
end for
else
Set ri
end if
D. More details of relaxation mechanism
When faced with infeasible instances, it typically indicates that some variable predictions are incorrect, resulting in conflicts with constraints. Our relaxation mechanism addresses this by dividing the conflicting variables into Gi groups and subsequently solving each without these variable sets. We choose G 10 in our evaluation.
To further determine the variables' feasible ranges, the upper and lower bounds are converted back into their corresponding integer forms, denoted as kub and kıg, For positive variables (s = 1). we represent the variable's 's value of the optimal solution in the form 2 + m, where à 2 0, 0 < m < 2 1. From the inequality < [log (1 0 + 1) S + 1, the predicted range for the variable lies between n and 2hub-1 For negative variables (s = 0), the ranges are symmetrically calculated, spanning from 21 to 2 + 1. For continuous variables, we first round them to the nearest integer and then process
13

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
them similarly integer variables.
When feasible solution cannot be found, repeatedly apply the relaxation mechanism, building upon previous relaxations. Each iteration of this mechanism reduces the number of fixed variables. Therefore, theoretically, with enough iterations, we can ensure that the variables causing conflicts with the constraints are filtered out. However, in practice, it usually takes only a few iterations to obtain a feasible solution. For example, in the case of bnd I, there are errors for only 8 for 2993 binary variables. By splitting these 8 erroneous variables into 10 groups, at least one group will inevitably exclude the erroneous variables. Of course, when the number of erroneous variables greater, this not guaranteed, but is important to note that some variables, even if mispredicted, do not affect the ability to find feasible solution due to their limited impact on solution sensitivity. We can easily filter out some variables that are highly sensitive solution quality for each group.
Algorithm 3 Relaxation Mechanism
if solution becomes infeasible then Divide fixed variables into G groups. for each group = 1, .,,....,C G do
Relax fixed variables in group g back their original bounds. Solve the subproblem with these relaxed constraints.
if feasible solution found then Proceed to the next iteration.
end if end for end
E. More details of experiments
E.1. Datasets
We selected the datasets based on two key considerations: first, the varying components within the instances, and second, the number of different variable types (integer, binary, continuous) present in each dataset. We aim for evaluation to cover a wide range of variable types and varying components comprehensively possible.
The varying components of nine datasets are summarized in Table
Table 6. The varying components of datasets.
Datasets
Varying component
LO UP
OBJ
LHS
RHS
MAT
bnd_1
bnd 2
bnd_3
mat
obj_1
obj_2
rhs_1
rhs 2
rhs_3
The details of each dataset is follows:
This dataset is from "bnd s1" in the MIP Computational Competition 2023 (Bolusani et al., 2023). The instance is based on the instance rococoC10-001000 from the MIPLIB 2017 benchmark library (Gleixner et al., 2021). The instances were generated by perturbing the upper bounds of general integer variables selected via discrete uniform distribution up to +100% of the bound value.
bnd 1:
14

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
This dataset is from "bnd_s2" in the MIP Computational Competition 2023 (Bolusani al., 2023). This series is based the instance esched007 from the MIPLIB 2017 benchmark library (Gleixner et al., 2021). The instances were generated via random fixings of 15% to 25% of the binary variables selected via discrete uniform distribution w.r.t. the original instance.
bnd 2:
This dataset is from "bnd s3" in the MIP Computational Competition 2023 (Bolusani et al., 2023). This series is also based on the instance csched007 from the MIPLIB 2017 benchmark library (Gleixner et al., 2021). The instances were generated via random fixings of 5% 20% of the binary variables selected via a discrete uniform distribution w.r.t. the original instance. These instances are relatively harder solve as compared the instances in bnd 2.
bnd 3:
This dataset is from "mat_sl" in the MIP Computational Competition 2023 (Bolusani et al., 2023). This series is based on the optimal vaccine allocation problem (Tanner & Ntaimo, 2010) and generated with varying constraint coefficients in the inequality constraints.
mat_1:
obj_1: This dataset is from "obj_s1" in the MIP Computational Competition 2023 (Bolusani et al., 2023). This series is based on the stochastic multiple binary knapsack problem (Angulo et al., 2016). The problem is modeled as a two-stage stochastic MILP and one-third of the objective vector varying across instances.
obj-2: This dataset is from "obj_s2" in the MIP Computational Competition 2023 (Bolusani et al., 2023). The instances are based on the instance ci-s4 from the MIPLIB 2017 benchmark library (Gleixner et al., 2021) with random perturbations and random rotations of the objective vector.
rhs_1: This dataset is from "rhs_s1" in the MIP Computational Competition 2023 (Bolusani et al., 2023). This series is based on the stochastic server location problem (Ntaimo, 2010). The instances is generated by the given dataset, and only the right-hand side vector of equality constraints varying across instances.
rhs 2:
This dataset is from "rhs s2" in the MIP Computational Competition 2023 (Bolusani et al., 2023). This series is based on a synthetic MILP and the associated dataset (liménez-Cordero et al., 2022). The instances are generated by taking a convex combination of two different RHS vectors.
This dataset is from "ths s4" in the MIP Computational Competition 2023 (Bolusani et al., 2023). This series is also based on the synthetic MILP Ceménez-Corden et al., 2022). The instances are generated by taking a convex combination of two different RHS vdfferssdifferent than the ones used for generating rhs.2).
rhs 3:
E.2. Implementation details of the baselines
All baselines that provided open-source implementations, including PS and Re_Tuning, were tested using their official code. Since ND did not provide open-source source code, we reproduced their method to the best of our ability based on their paper (Nair al., 2020) and fine-tuned the parameters accordingly.
SCIP. We use SCIP 8.0.4 (Bestuzheva et al., 2021), which is the state-of-the art open source solver. We keep all the other SCIP parameters to default and emphasize that all of the SCIP solver's 's advanced features, such as presolve and heuristics, are open.
Re_Tuning. Re_Tuning is a state-of-the-art heuristic reoptimization framework (Patel, 2024), which does not utilize machine learning models. This framework, developed for the MIP 2023 workshop's 's computational competition (Bolusani et al., 2023), earned the first prize. It is primarily based reusing historical branches and fine-tuning SCIP's parameters for more effective reoptimization. Our investigation revealed that Re Tuning adjusts its configurations based on the previous instances it solves. Specifically, it may disable modules such as presolving or generating cutting planes for subsequent instances. While these adjustments have been shown to potentially improve overall solving time on certain datasets, they inevitably make it more challenging to find high-quality feasible solutions quickly in the early stages. To address this, we ensured these modules remained enabled for all instances, striving to achieve the best possible results with their code.
Prediic-and--Seacc((Ps)) PS is an end-to-end machine learning- based approach (Han et al., 2023) which employs large neighborhood search (LNS) combined with GNN predictions. In practice, we do not know how many variables may be predicted incorrectly, and selecting appropriate radius 5 for the neighborhood in LNS can be time-consuming. To better demonstrate the performance of the PS method, we select the radius å based on the average number of binary prediction errors observed during our preliminary tests, as shown in Table 1.
Neural Diving(ND), Another notable method we compared against is Neural Diving (ND) framework with Selective
15

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Net (Nair al., 2020), which is also based variable-fixing strategy. Since ND focuses fixing variables accelerate the solving process, it serves relevant baseline evaluate alongside approach.
E.3. More results with different parameters
In this section, we present comprehensive evaluation of policy performance across various synthetic and real-world datasets, using different time and fix parameters. Each table below illustrates the impact of varying these parameters the performance metrics, namely the absolute and relative gaps. The methods examined include SCIP, Re_Tuning, ND, and PS, alongside our proposed method, VP-OR, under different time constraints and fixed parameter ratios.
Table 7 illustrates the performance of various methods under different boundary conditions (bnd 1, bnd 2, bnd 3). After reoptimizing with adjusted boundary parameters, the VP-OR method consistently shows lower absolute and relative gaps compared SCIP and other comparative methods under different time constraints (T=10 and T=20).
Table 7. Policy evaluation the synthetic and real-world datasets with different time and fix parameters, We report the arithmetic mean of gap_abs sap_abs and gap rel.
Methods
bnd 1
bnd 2
bnd 3
gap_abs
gap rel
gap_abs
gap rel
gap.abs
gap_rel
SCIP (T=10.0)
1974.20
0.16
Re. Re.Tuning (T=10.0)
1425.5
0.12
ND (T=10.0, P=0.5)
PS (T=10.0, P=0.5)
9439.60
0.79
VP-OR(Ours) (T=10.0, P=0.5)
279.20
0.02
40.20
0.11
31.20
0.09
ND (T=10.0, P-0.))
PS (T=10.0, P=0.6)
9439.60
0.79
VP-OR(Ours) (T=10.0, P=0.6)
$28.80
0.04
39.40
37.40
0.11
ND (T=10.0, P=0.7)
(T=10.0, P=0.7)
9665.20
0.81
VP-OR(Ours) (T=10.0, P=0.7)
299.40
0.02
40.20
0.11
28.60
0.06
ND (T=10.0, P=0.8)
PS (T=10.0,
1216.80
0.10
(::O(OOu))(T=100))) P=0.8)
973.80
0.08
38.80
0.11
34.80
0.10
SCIP (T=20.0)
921.00
0.08
Re Tuning (T=20.0)
402.25
0.03
26.0
0.06
ND (T=20.0, P=0.5)
PS (T=20.0, P=0.5)
2483.00
0.20
VP-OR(Ours) (T=20.0, P=0.5)
313.20
0.03
48.60
0.14
33.80
0.10
ND (T=20.0, P=0.6)
PS (T=20.0, P=0.6)
2408.00
0.19
VP-OR(Ours) (T=20.0, P=0.6)
264.60
0.02
40.40
0.12
37.40
0.11
ND (T=20.0, P=0.7)
PS (T=20.0, P=0.7)
2627.40
0.21
VP-OR(Ours) (T=20.0, P=0.7)
299.40
0.02
39.80
0.11
23.40
0.07
ND (T=20.0, P=0.8)
PS (T=20.0, P=0.8)
1007.20
0.08
VP-OR(Ours) (T=20.0, P=0.8)
1409.40
0.12
41.40
0.12
23.40
0.07
16

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Table evaluates performance under different matrix and objective function settings (mat_1, obj_1, obj.2). With these adjustments, the VP-OR method maintains significant suppression of gap abs and gap rel, particularly excelling in objective function cases (obj_1 and obj.2).
Table 8. Policy evaluation on the synthetic and real-world datasets with different time and fix parameters. We report the arithmetic mean gap.abs and gap
Methods
mat_1
obj_1
obj_2
gap_ab
gap_rel
gap_abs
gap_rel
gap_abs
gap_rel
SCIP (T=10.0) Rc. Re.Tuning (T=10.0)
14.10
0.23
11.40
0.00
626.52
0.39
30.06
0.48
10.25
0.00
74.10
0.09
ND (T=10.0, P=0.5)
11.40
0.00
634.70
0.39
(T=10.0, P=0.5)
14.10
0.23
13.40
0.00
387.89
0.51
VP-OR((urs) (T=10.0, P=0.5)
9.09
0.15
7783.94
1.53
ND (T=10.0, P=0.6)
11.40
0.00
634.70
0.39
PS (T=10.0, P=0.6)
14.10
0.23
13.40
0.00
397.53
0.51
VP-OR(Ours) (T=10.0, P=0.6)
11.62
0.19
6854.66
0.75
ND (T=10.0, P=0.7)
11,40
0.00
674.21
0.44
PS (T=10.0, P=0.7)
14.10
0.23
13.40
0.00
397.53
0,51
VP-OR(OurS) (T=10.0, P=0.7)
10.09
0.16
3.28
0.00
329.99
0.06
ND (T=10.0, P=0.8)
11.40
0.00
PS (T=10.0, P=0.8)
14.10
0.23
13.40
0.00
702.68
0.41
VP-OR(Ours) (T=10.0, P=0.8)
11.77
0.19
338.60
0.04
8287.57
3.01
SCIP (T=20.0)
11.66
0.19
10.40
0.00
285.99
0.14
Re: Teningg (T=20.0)
18637.00
0.42
8.25
0.00
1.61
0.01
ND (T=20.0, P=0.5)
10.40
0.00
285.99
0.14
PS (T=20.0, P=0.5)
13.17
0.21
13.40
0.00
243.40
0.30
VP-OR(Ours) (T=20.0, P=0.5)
7.69
0.12
6855.85
0.75
ND (T=20.0, P=0.6)
10.40
0.00
268. 18
0.13
PS (T=20.0, P=0.6)
13.17
0.21
13.40
0.00
243.40
0,30
VP-OR(Ours) (T=20.0, P=0.6)
9.94
0.16
19.40
0.00
6058.61
0.50
ND (T=20.0, P=0.7)
10.40
0.00
285.99
0.14
PS (T=20.0, P=0.7)
13.17
0.21
13.40
0.00
239.79
0.28
VP-OR(Ours) (T=20.0, P=0.7)
10.09
0.16
3.28
0.00
12.85
0.01
ND (T=20.0, P=0.8)
10.40
0.00
PS (T=20.0, P=0.8)
13.17
0.21
13.40
0.00
202.44
0.16
VP-OR(Ours) (T=20.0, P=0.8)
11.61
0.19
142.40
0.02
12.85
0.01
17

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Table 9 shows the response of each method when adjusting the parameters the right-hand side of constraints (rhs_1, rhs_2,
rhs 3). In these scenarios, the VP-OR method achieves gaps close
Table 9. Policy evaluation the synthetic and real-world datasets with different time and fix parameters, We report the arithmetic mean gap abs and gap rel.
Methods
rhs_1
rhs_2
rhs_3
gap_abs
gap_rel
gap_abs
gap_rel
gap_abs
gap_rel
SCIP (T=10.0)
173.08
0.50
12.29
0.00
16.77
0.00
Rc_ Re_Tuning (T=10.0)
6.40
0.02
2.24
0.00
0.40
0.00
ND (T=10.0, P=0.5)
PS (T=10.0, P=0.5)
57558.07
165.41
13.23
0.00
12.46
0.00
VP-OR(Ours) (T=10.0, P=0.5)
0.27
0.00
1.85
0.00
0.26
0.00
ND (T=10.0,
PS (T=10.0, P=0.6)
62046.33
177.93 0.00
13.23
0.00
12.46
0.00
VP-OR(Ours) (T=10.0, P=0.6)
0.50
1.85
0.00
0.26
0.00
ND (T=10.0, P=0.7)
PS (T=10.0, P=0.7)
67090.50
193.04
22.25
0.00
17.98
0.00
VP-OR(Ours) (T=10.0, P=0.7)
0.73
0.00
1.85
0.00
0.26
0.00
ND (T=10.0, P=0.8)
(T=10.0, P=0.8)
66978.45
192.33
15.35
0.00
16.29
0.00
VP-OR(Ours) (T=10.0, P-0.)
0.71
0.00
1.85
0.00
0.26
0.00
SCIP (T=20.0)
173.08
0.50
5.54
0.00
7.22
0.00
Re Tuning (T=20.0)
2.85
0.01
0.00
0.00
0.00
0.00
ND (T=20.0, P=0.5)
PS (T=20.0, P=0.5)
38275.26
109.85 0.00
5.54
0.00
5.97
0.00
VP-OR(Ours) (T=20.0, P=0.5)
0.39
1.85
0.00
0.26
0.00
ND (T=20.0, P=0.6)
PS (T=20.0, P=0.6)
38275.26
109.85 0.00
5.47
0.00
5.97
0.00
VP-OR(Ours) (T=20.0, P=0.6)
0.26
1.85
0.00
0.26
0.00
ND (T=20.0. P=0.7)
PS (T=20.0, P=0.7)
65141,18
187.43 0.00
4.42
0.00
5.97
0.00
VP-OR(Ours) (T=20.0, P=0.7)
0.29
1.85
0.00
0.26
0.00
(T=20.0. P=0.8)
PS (T=20.0, P=0.8)
54004, 10
155.03
3.30
0.00
2.16
0.00
VP-OR(Ours) (T=20.0, P=0.8)
0.40
0.00
1.85
0.00
0.26
0.00
18

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
E.4. More results of the relative gap
In the main text, we presented results for the datasets bnd_1, mat_1, and rhs_ Here, extend our analysis by providing additional results for the remaining datasets. This section focuses performance comparisons in terms of the average relative gap gap_rel.
1.0
1.0
1.0
Re. Toning
Re. Re_Tuning
Re. Me_Tuning
gap gap. rel
VP-OR(OUrs)
Avg. gap rel
VP-OR(Ours)
Avg. gap rel
VP-OR(Ours)
Avg.
0.2
0.2
0.2
0.0
100
0.0
100
0.0
60
80
100
time(s)
time(s)
time(s)
Figure 3. Performance comparisons in bnd.2, bnd_3 and obj-1, where the y-axis is average relative primal gap; cach plot represents one benchmark dataset.
Tuningg SCIP
Re_Tuning
te_Tuning
SCIP
SCIP PS
0.8
P5
0.8
P5
0.8
Avg. gap rel
VP-OR(Ours)
rel
Avg. gap rel
VP-OR(OUrs)
0.6
0.6
0.6
Avg.
0.2
0.2
0.2
time (s)
time(s)
time(s)
Figure 4, Performance comparisons in obj_2, rhs_2 and rhs_3, where the y-axis is average relative primal gap; cach plot represents one benchmark dataset.
E.5. Ablation study of prediction.
The table below demonstrates the predictive performance of both traditional Graph Neural Networks (GNN) and our approach in reoptimization context(Re GNN):
E.6. Computational complexity analysis
The primary computational complexity VP-OR arises from the Thompson Sampling process. In the sampling phase of Thompson Sampling, sample the probability for binary variables and select certain percentage (a%) of variables based on the value of min(p, 1 p) by sorting them. For integer and continuous variables, we sample to determine whether they should be fixed and select the top a% of variables based on this criterion. This step has time complexity of ((nlogn), where n is the number of variables.
In the parameter update phase of Thompson Sampling, we update the parameters for each variable once. This step has a time complexity of (n)) We tested the sampling time and parameter update time for each dataset, as presented in Table 11.
19

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Table 10. Predictive performance of traditional Graph Neural Networks (GNN) and our prediction method in reoptimization con- GNNN)
bnd_1
bnd_2 2
bnd_3
Total binary var.
1457.0
1457.0
1457.0
mispredicted binary var. (GNN)
163.0
45.1
42.2
mispredicted binary var. (Re.GNN)
8.2
6.7
4.5
Total integer
124.0
0.0
0.0
mispredicted integer var. (GNN)
33.4
0.0
0.0
mispredicted integer var. (Re_GNN)
17.4
0.0
0.0
Total continuous var. mispredicted continuous (GNN)
0.0
301.0
301.0
0.0
140.2
121.0
mispredicted continuous var. (Re_GNN)
0.0
0.0
2.0
Table 11. Variable Numbers, Sampling Time(Time-s), and Parameter Update Time(Time.u) for Different Datasets
bnd 1
bnd 2
bnd 3
mat 1
obj 1
obj 2
rhs 1
rhs 2
rhs 3
Var. num
3117
1758
1758
802
360
745
12760
1000
1000
Time (s)
0.008
0.005
0.003
0.013
0.002
0.016
0.102
0.002
0.002
Time_u u (s)
0.002
0.001
0.000
0.009
0.001
0.010
0.070
0.001
0.001
E.7. Results for the impact of initial hints
We provided the initial solution hint for the "completesol" heuristic method during the presolve phase, effectively employing the historical solution as a warm start(WS). We observe that SCIP has improvements in the quality of feasible solutions under these conditions. The results are shown Table 12, where "_" indicates cases where the method could not find a feasible solution within the designated time limit.
Table 12, Performance Comparison Across SCIP, SCIP(WS) and VP-OR.
We report the arithmetic mean of the metric gap.rel.
Method
bnd 1
bnd_2
bnd_3
mat.1
obj_1
obj.2
rhs.
rhs.2 2
rhs_3
SCIP
0.16
0.23
0.00
0.39
0.50
0.00
0.00
SCIP(WS)
0.10
0.22
0.00
0.12
0.50
0.00
0.00
VP-OR(Ours)
0.02
0.11
0.06
0.16
0.00
0.06
0.00
0.00
0.00
E,8. More results for expanded test samples
The publicly available dataset from the MIP Workshop 2023 Computational Competition on Reoptimization (Bolusani et al., 2023) is limited in size, providing only 50 examples per task. To further increase the number of test samples, we attempt to generate similar datasets for testing by using a method consistent with the one published by the competition organizers. This step proves to be very time-consuming because random perturbations in the parameters often result in infeasible problems. During the dataset generation process, we repeatedly generate instances randomly until we find one that is feasible. Using the b dataset as an example, we generate 100 additional instances. The results presented in Table 13 are consistent with our previous tests.
E.9. More results for end-to-end methods
Several end-to-end methods have been developed specifically for large-scale problems, such as GNN&GBDT (Ye et al., 2023) and Light-MILL (Ye et al., 2024). We conduct an experiment on the latest approach, Light-MILPopp We observe that Light-MILPopl uses a variable fixing strategy, initially fixing k% of the variables based on predicted values (using the default setting k=20 as per the authors' code). However, in reoptimization context, fixing these variables often led to
20

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Table 13. Policy evaluation on the bnd_I dataset with 100 samples. We provide the metrics Average Relative Gap (gap.rel) and Average
Absolute Cap (gap_abs).
Method
gap rel
gap abs
SCIP
0.20
2354.2
PS VP-OR(OUrs)
1.13
13213.0
0.01
167.3
infeasibility in most instances. This is mainly because the model inaccurately predicts some variables, when considered high-confidence. Consequently, we test the results with the variable fixing module disabled. The final experimental results present the number of instances that can find feasible solutions within 10-second time limit in Table 14. Although this method is not specifically designed for reoptimization scenarios, which often demand rapid responses to slight changes in parameters with time-critical requirements for solutions, it does show some improvement over SCIP on more challenging datasets like bnd and bnd_3.
Table 14, Number of Instances Finding Feasible Solutions within 10 Seconds.
Method
bnd_1
bnd_2
bnd_3
SCIP
5/5
0/5
0/5
Light-MILPopt
0/5
0/5
0/5
Light-MILPopt (without fix strategy)
5/5
1/5
1/5
VP-OR (Ours)
5/5
5/5
5/5
We provide the average relative gap (gap_rel) for comparison in Table 15, where "_" represents where the method could not find feasible solution within the time limit.
Table 15. Average Relative Gap (elp.rel).
bnd_1
bnd_2
bnd_3
SCIP
0.16
Light-MILPopt
Light-MILPopt (without fix strategy)
0.22
VP-OR (Ours)
0.02
0.11
0.06
E.10. 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 comparison with the ML-guided LNS method of Huang al. (ConPas) (Huang al., 2024). The results reported for both Gurobi and SCIP. We generate large-scale datasets IS and CA using the code from Gasse et al. (Gasse et al., 2019), 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. Fig. 16 and Fig. 17 shows that VP-OR achieves more significant acceleration than PS (Han et al., 2023) and ConPas (Huang et al., 2024) during the early stages of solving on both Gurobi and SCIP.
E. Ablation experiments
We conduct an ablation experiment in Fig. 18 using Re-GNN for initial solution prediction LNS and traditional GNN with the Thompson Sampling (TS) algorithm. We report the average gap rel, where "_" means no feasible solution was found.
21

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Table 16. Average absolute gap (gap.abs), relative gap (gap_rel) and the number of each method that achieves the closest solution to the optimal one within the 30-second time limit (Wins) of the CA dataset.
gap_abs
gap.rel
Wins
SCIP
24068.22
0.19
0/100
Gurobi
3754.16
0.03
0/100
PS+SCIP
20182.91
0.19
0/100
PS+Gurobi
3754.16
0.03
0/100
ConPaS+SCIP
8506.52
0.07
0/100
ConPaS+Gurobi
2526.28
0.02
0/100
VP-OR+SCIP(Ous)
0.00
0.00
12/100
VP-OR+Gurobb(Ourr)
0.00
0.00
88/100
Table 17. Average absolute gap (gap_abs), relative gap (gap_rel) and the number of each method that achieves the closest solution to the optimal one within the second time limit (Wins) of the dataset.
gap_abs
gap_rel
Wins
SCIP
104.92
0.05
0/100
Gurobi
133.07
0.06
0/100
PS+SCIP
104.57
0.05
0/100
PS+Gurobi
117.62
0.06
0/100
ConPaS+SCIP
30.25
0.01
0/100
ConPaS+Gurobi
24.66
0.01
0/100
VP-OR+SCIP(OUrs)
9.57
0.00
33/100
VP-OR+Gurobi(Ours)
0.97
0.00
67/100
22

---

Don't Restart, Just Reuse: Reoptimizing MILPs with Dynamic Parameters
Re-GNN improves performance 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.
Table 18. Average absolute gap (gap abs) within the 10-second time limit of the datasets, where "-" means no feasible solution was found.
bnd_1
bnd 2
bnd.3
mat_1
obj.1
obj.2
rhs_1
rhs
rhs
GNN+LNS(PS)
0.81
0.23
0.00
0.51
193.04
0.00
0.00
Re-GNN+LNS
0.16
0.23
0.00
0.21
1.04
0.00
0.00
GNN+TS Re-GNN+TS(VP-OR)
0.04
0.17
0.12
0.17
0.00
0.00
0.00
0.00
0.00
0.02
0.11
0.06
0.16
0.00
0.00
0.00
0.00
0.00
E.12. Accuracy of predicted bounds for integer and continuous variables
We evaluate the accuracy of predicted bounds for integer and continuous variables as follows: the optimal value of a variable lies within the predicted lower and upper bounds, the predicted bounds are considered accurate; otherwise, they are not. Continuous and integer variables are treated similarly, with the key difference being that continuous variables are rounded during preprocessing.
In Fig. 19, evaluate how tight these bounds become after training and across different optimization stages, use Lo and C.o to denote the average difference between original upper and lower bounds for integer and continuous variables, respectively. Lp 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.
Table Average difference between original and predicted bounds of datasels, where "NA" means there are no integer or continuous variables in the dataset.
bnd_1
bnd_2 2
bnd_3
mat_1
obj_2
rhs_1
rhs
rhs_3
Lo
72146.14
NA
NA
NA
2.0
NA
NA
NA
Lp
32750.57
NA
NA
1.34
NA
NA
NA
NA
C_o
NA
25.91
26.15
1.0
lc+19
le+20
2e+20
2e+20
NA
14.22
14.28
1.0
19968.14
1.0
14.22
13.67
23


Reviews:
[{"review_id": "2qBAKOjhj2", "reviewer": "Reviewer_A56t", "summary": "“Don’t Restart, Just Reuse” addresses the problem of MILP reoptimization – repeatedly solving similar MILP instances that change over time (e.g. objective coefficients, constraints, or bounds)​. The paper proposes a novel two-stage framework called VP-OR (Variable Prediction and Online Refinement) for fast reoptimization of MILPs with dynamic parameters​. In the first stage, a graph neural network (GNN) model predicts a high-confidence partial solution space for the new MILP by estimating marginal probabilities for binary variables and feasible value ranges for integer/continuous variables​. In the second stage, an iterative refinement procedure uses a Thompson Sampling bandit strategy to gradually fix a subset of variables to their predicted values or ranges and solve the reduced MILP, updating which variables to fix in subsequent iterations based on solution improvements​. Extensive experiments on 9 dynamic MILP datasets (derived from MIP 2023 workshop Competition benchmarks) demonstrate that VP-OR finds feasible solutions for every test instance within 10 seconds and achieves lower primal gaps than baseline methods, converging to better solutions more rapidly.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback and suggestions.\n## Response to the Question 1\n**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.\n\n**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.\n\nCA:\n|  | gap_abs| gap_rel | wins|\n|-------|-------|-------|----|\n|SCIP|24068.27|0.19|0/100|\n|Gurobi|3754.16|0.03|0/100|\n|PS+SCIP|20182.91|0.19|0/100|\n|PS+Gurobi|3754.16|0.03|0/100|\n|ConPaS+SCIP|8506.52|0.07|0/100|\n|ConPaS+Gurobi|2526.28|0.02|0/100|\n|VP-OR+SCIP(Ours)|0.00|0.00|12/100|\n|VP-OR+Gurobi(Ours)|**0.00**|**0.00**|**88/100**|\n\n\nIS:\n|  | gap_abs| gap_rel | wins|\n|-------|-------|-------|----|\n|SCIP|104.92|0.05|0/100|\n|Gurobi|133.07|0.06|0/100|\n|PS+SCIP|104.57|0.05|0/100|\n|PS+Gurobi|117.62|0.06|0/100|\n|ConPaS+SCIP|30.25|0.01|0/100|\n|ConPaS+Gurobi|24.66|0.01|0/100|\n|VP-OR+SCIP(Ours)|9.57|0.00|33/100|\n|VP-OR+Gurobi(Ours)|**0.97**|**0.00**|**67/100**|\n\n## Response to the Comment 1\n**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. \n\nThe 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.\n\n## Response to the Comment 2\nYes, 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.\n\n[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.\n\n[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.\n\n[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.", "claims_and_evidence": "The paper’s key claims are well-supported by thorough evidence. For example, (a) VP-OR yields superior solution quality under tight time limits – The authors back this by reporting, for each dataset, the number of instances where a feasible solution is found within 10 seconds (Table 3). VP-OR finds feasible solutions in all test cases within 10s, whereas other methods often fail on harder instances. (b) VP-OR is significantly faster than traditional large neighborhood search (LNS) – This claim is quantified in Table 2: fixing a substantial portion of variables (with VP-OR’s strategy) leads to solving times an order of magnitude shorter than LNS-based methods​. \n\nOverall, the evidence presented is convincing and aligns with the claims. I did not identify any problematic claims – the authors are careful to couch statements in empirical results.", "methods_and_evaluation_criteria": "The proposed VP-OR method is well-motivated and appropriate for the reoptimization problem domain. The combination of a GNN for variable prediction and Thompson Sampling for iterative variable fixing is a sound design: the GNN exploits structural similarities between consecutive MILP instances, and the refinement stage balances exploration/exploitation when fixing variables. This approach directly addresses the limitations of prior reoptimization techniques, which either reused old solutions that might be invalid or only tweaked solver parameters without reducing problem complexity. The evaluation methodology is rigorous and well-aligned with the problem’s goals. The authors focus on time-constrained performance (10-second limit), reflecting real-world needs for quick reoptimization in dynamic settings. The experiments are conducted on nine diverse MILP reoptimization datasets from a well-known competition​, ensuring the evaluation is realistic and broad. The authors split data into training and test sets properly (training on 20 instance pairs and testing on 5 pairs per dataset), which is appropriate to evaluate generalization to new instances. Overall, the methods and evaluation criteria are sound and well-chosen for the problem. I have no major concerns here; the paper’s approach is both novel and evaluated fairly.", "theoretical_claims": "The paper does not heavily focus on new theory – it is primarily an algorithmic and empirical contribution. There are no formal theorems or proofs presented that require verification (I did not encounter any stated lemma or theorem in the main content). The use of Thompson Sampling is supported by standard bandit theory references, but the paper itself treats it as a heuristic for exploration; no formal convergence proofs are provided. The authors’ theoretical claims are mostly implicit in the design – for example, the variable fixing strategy that leads to accelerated solving is reasonable. In summary, while there are no new theoretical guarantees to check, the paper’s technical content is consistent with known theory, and I found no issues in the mathematical formulation or algorithmic claims.", "experimental_designs_or_analyses": "The experimental setup is thorough and well thought out, lending credibility to the results. The authors clearly define three experiments targeting different aspects: (1) feasibility within 10s, (2) solution quality (gap) in 10s, and (3) convergence over 100s​. This separation makes it easy to understand how each method performs in terms of both speed and quality. The use of 9 different datasets (with varied parameter changes: objective, bounds, matrix coefficients, RHS) demonstrates that the approach is not tuned to one specific scenario but is broadly applicable. The experiments are reproducible and sufficiently detailed. The analysis acknowledges limitations too: e.g., VP-OR can get stuck in a suboptimal solution in longer runs (though it finds good solutions faster)​. Overall, the design and analysis of the experiments are valid and convincing.", "relation_to_broader_scientific_literature": "This work is well-situated at the intersection of operations research reoptimization techniques and machine learning for combinatorial optimization. Traditional MILP reoptimization methods (e.g. warm-start approaches) focusing on reusing information like optimal solutions or branch-and-bound trees from previous instances struggle when the new instance differed more substantially, as the old optimal solution might not be feasible and reusing search trees may not reduce problem complexity​. The re-tuning method (Patel 2024) extended this by preserving a series of past solutions and adaptively tuning solver parameters​. In parallel, recent years have seen ML-driven heuristics for MILP: e.g. Neural Diving (Nair et al., 2020) which learns a distribution over binary variables and fixes some to reduce the problem​, and Predict-and-Search (Han et al., 2023) which uses a GNN to predict variables then applies large neighborhood search​. The contribution of this paper is to merge the strengths of both lines of work: it uses instance-specific historical data (like classical reoptimization) and employs learning to predict variable fixings (like ND/PS), achieving a new level of performance.", "essential_references_not_discussed": "The authors have done a good job covering the essential prior work, and I did not identify any critical omissions in the references.", "other_strengths_and_weaknesses": "Strengths: This paper’s primary strength lies in its original combination of ideas that yields practical impact. The VP-OR framework is a novel synthesis of ML prediction and online optimization that, to my knowledge, has not been applied to MILP reoptimization before. The results show substantial improvements in time-constrained scenarios – for instance, being the only method to consistently solve all instances in under 10 seconds is a compelling result for real-time applications.\n\nWeaknesses: One weakness is the lack of theoretical guarantees. As a heuristic/learning method, VP-OR does not guarantee optimality or even improvement in every iteration. It is possible that it could fix a wrong set of variables. While this is acceptable for a heuristic approach, some theoretical analysis (e.g. bounds on solution quality in terms of prediction accuracy) could strengthen the work. Another potential weakness is scalability/generalization: the method was tested on instances solvable within 10 minutes by SCIP (up to 600s baseline solve time); it’s not proven how it scales to truly large-scale MILPs beyond those benchmarks. These weaknesses are relatively minor in comparison to the contributions.", "other_comments_or_suggestions": "The authors might consider a few minor improvements. \n\nIn Table 4, it might help to clarify how “gap abs” and “gap rel” are defined, especially since some methods show a 0.00 relative gap but still have a non-zero absolute gap. \n\nI assume that the 10-second evaluation for VP-OR includes the model inference and refinement iterations. It would be good if the final version states that explicitly.\n\nFuture work: I echo the authors’ note on extending to larger instances.\n\nOverall, my comments are minor; the paper is in good shape.", "questions_for_authors": "Generalization: How well would the trained GNN model generalize to instances with new characteristics outside the training distribution?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G3EnU17XSt", "reviewer": "Reviewer_MNmC", "summary": "This paper introduces a novel ML-guided framework for predicting solutions for reoptimization problems. First, they adapt on current GNN methods by adding information about the leaf node to predict solutions specifically for reoptimization problems. Second, they introduce online-learning methods to refine the solutions they found. The paper has shown superior performance of their approach over default solver and several baselines.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback and suggestions.\n## Response to the Question 1\n**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.\n\nCA:\n|  | gap_abs| gap_rel | wins|\n|-------|-------|-------|----|\n|SCIP|24068.27|0.19|0/100|\n|Gurobi|3754.16|0.03|0/100|\n|PS+SCIP|20182.91|0.19|0/100|\n|PS+Gurobi|3754.16|0.03|0/100|\n|ConPaS+SCIP|8506.52|0.07|0/100|\n|ConPaS+Gurobi|2526.28|0.02|0/100|\n|VP-OR+SCIP(Ours)|0.00|0.00|12/100|\n|VP-OR+Gurobi(Ours)|**0.00**|**0.00**|**88/100**|\n\n\nIS:\n|  | gap_abs| gap_rel | wins|\n|-------|-------|-------|----|\n|SCIP|104.92|0.05|0/100|\n|Gurobi|133.07|0.06|0/100|\n|PS+SCIP|104.57|0.05|0/100|\n|PS+Gurobi|117.62|0.06|0/100|\n|ConPaS+SCIP|30.25|0.01|0/100|\n|ConPaS+Gurobi|24.66|0.01|0/100|\n|VP-OR+SCIP(Ours)|9.57|0.00|33/100|\n|VP-OR+Gurobi(Ours)|**0.97**|**0.00**|**67/100**|\n\n## Response to the Question 2\n\n**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.\n\n|  | bnd_1 |bnd_2|bnd_3|mat_1|obj_1|obj_2|rhs_1|rhs_2|rhs_3|\n|-------|-------|-------|---|----|----|----|----|----|-----|\n| GNN+LNS(PS) |0.81|inf|inf|0.23|0.00|0.51|193.04|0.00|0.00|\n| Re-GNN+LNS |0.16|inf|inf|0.23|0.00|0.21|1.04|0.00|0.00|\n| GNN+TS |0.04|0.17| 0.12|0.17|0.00|0.00 |0.00|0.00|0.00|\n| Re-GNN+TS(VP-OR) |0.02|0.11| 0.06|0.16|0.00|0.06|0.00|0.00|0.00|\n\n## Response to the Question 3\nRe-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.\n\n**Reference:**\n\n[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.\n\n[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.\n\n[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.", "claims_and_evidence": "The claims in the paper are partly supported by experiments. The experiments in the appendix have shown the methods of Re-GNN features are definitely better than original features when applied to reoptimization problems. But I didn’t find any ablation studies for the iterative online refinement methods. All the experiment results show the whole two-step process without knowing how online refinement has contributed to performance improvement.", "methods_and_evaluation_criteria": "The proposed methods are valid and interesting. However, the benchmark datasets they used is not enough to show their approaches work. Generally, when you use ML-guided heuristic methods, you would test the performance on much harder instances (e.g. at least 1 hour to solve) than the instances evaluated in this paper.", "theoretical_claims": "No major proof and theoretical claims in the paper.", "experimental_designs_or_analyses": "The baseline the paper compared is weak, so additional experiments are needed to ensure the performance improvement of the author's claimed methods. First, ND and PaS work the best when solving problem instances that are very hard. Using them on smaller instances and showing gaps at a runtime cutoff of only 10 seconds may not be appropriate. Second, the instances used for training ND and PaS are much smaller than the original paper, 40 instances is not enough to get competitive results for ND and PaS, as their original paper uses 300 instances for training. Thirdly, the author did not compare their methods with state-of-art solver Gurobi. I didn’t see why the methods couldn’t be applied to the Gurobi solver, since one of the baseline PaS is running experiments against both SCIP and Gurobi.", "relation_to_broader_scientific_literature": "Speeding up MILP solving is very useful for solving a lot of real-world problems. The paper has improved upon previous reoptimization approaches for MILPs.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Can you show some experiment results on a larger set of harder instances (e.g., 200 train, 100 test) that would require a runtime of more than 1 hour? And can you show the performance comparison both on SCIP and Gurobi?\n2. Can you provide some insights about how much performance you gain by online refinement? How is the performance w/o online refinement?\n3. The methods of Re-GNN are described very vaguely. Can you explain more carefully how you use the leaf node feature as training data?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J2KoLtcIob", "reviewer": "Reviewer_vV2R", "summary": "This paper studies the opportunities of leveraging an existing solution to efficiently adapt to slight modifications in MILP constraints or objectives, thereby accelerating MILP reoptimization. To this end, it introduces Variable Prediction Online Refinement (VP-OR), a novel two-stage reoptimization framework. First, VP-OR learns to predict confidence bounds for each MILP variable, leveraging historical information and a GNN to induce a high-quality solution space. It then incorporates Thompson Sampling (using a Beta distribution) to dynamically adjust the confidence of selecting variables to be fixed during online refinement (optimization). Results show that VP-OR can yield much better performance when the time limits for reoptimization are small (i.e., restricted in 10s).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback and suggestions.\n## Response to Comment 1\nThere 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.\n## Response to Comment 2\n**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.\n|  | bnd_1  | bnd_2 | bnd_3 | \n|--|---|---|---|\n| Total binary var. |1457.0 | 1457.0|1457.0|\n| binary var. (GNN) |163.0 |45.1| 42.2 |\n| binary var. (Re_GNN)|**8.2**|**6.7**|**4.5**|\n| Total integer var. |  124.0 | 0.0 | 0.0|\n| integer var. (GNN) |  33.4 |0.0 | 0.0|\n| integer var. (Re_GNN)|**17.4**|0.0 | 0.0 |\n| Total continuous var. |0.0 | 301.0 | 301.0 |\n| continuous var. (GNN) |0.0 |140.2|121.0  |\n| continuous var. (Re_GNN)| **0.0** |**0.0**|**2.0**|\n## Response to Comment 3, 4\nWe 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.\n\nWe 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.\n\nThe 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.\n\n## Response to Comment 6, 8\n**Large-scale experiments**: Please refer to our Response to Reviewer MNmC's Question 1 for details.\n\n## Response to Comment 7\n**Ablation experiment**: Please refer to our Response to Reviewer MNmC's Question 2 for details.\n\n## Response to Comment 9, Question 2\n1) 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.\n\n2) Continuous and integer variables are treated similarly, with the key difference being that continuous variables are rounded during preprocessing.\n\nTo 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. \n\n|  | bnd_1  | bnd_2 | bnd_3| mat_1|obj_2|rhs_1|rhs_2|rhs_3|\n|-----|--|---|---|---|---|---|---|----|\n| I_o |72146.14|NA|NA|NA|2.0|NA|NA|NA|NA|\n| I_p |32750.57|NA|NA|NA|1.34|NA|NA|NA|\n| C_o |NA|25.91| 26.15|1.0|1e+19|1e+20 |2e+20|2e+20|\n| C_p |NA|14.22| 14.28|1.0|19968.14|1.0|14.22|13.67|\n\n## Response to Comment 10\nThe '-' 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.\n\n## Response to Question 3\nEach instance uses only one GPU for both training and inference.\n\n## Response to Question 4\nOur 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.", "claims_and_evidence": "Most of the claims are well supported with evidence. However, a few comments are:\n\n1. In the introduction, the authors state that reusing branching strategies and adjusting parameters can save time. However, it also reads that these approaches do not reduce the overall size or complexity of the problem. Does this create a contradiction?\n\n2. The claim, \"However, predicting each binary bit’s actual value can lead to inaccuracies, causing overall prediction errors.\" (around line 131), should be better justified with supporting evidence or examples.\n\nAlso, the paper seems insufficiently polished, with lots of unclear statements and uncovered details regarding the methodology. Please refer to the following points for specific areas requiring clarification.", "methods_and_evaluation_criteria": "3. The paper lacks clarity in presentation, which may hinder understanding of the soundness of the approach. Section 4.1 is difficult to follow, as it intermixes various aspects such as the training stage, inference stage, training data processing, and predicted output processing within the same discussion flow. It is suggested to separate these components into distinct paragraphs to improve readability.\n\n4. The section 4 is also missing key details, including: Definition of network input/output, Network architexture, Training Method and framework, Loss function, Data generation, Inference algorithm. Without these, the methodology remains unclear and difficult to follow.\n\n5. Particularly, the necessity of the binary representation as well as the logarithmic transformation is unclear. Further discussion, along with numerical evidence, would be helpful to justify these choices.\n\n6. The method appears to be trained on a small set of instances. I have concerns on how well it generalizes to other MILP instances. This is important as we need to offset the training cost so that once the model is trained, it can address many online optimization instances. Also, would the current model show signs of overfitting on the small datasets? Will it leads to poor long-term performance or unexpected failures?\n\n7. It remains unclear to what extent Thompson Sampling helps in mitigating infeasibility and early convergence to local optima. Further analysis and empirical validation would help in this regard.", "theoretical_claims": "Not involved.", "experimental_designs_or_analyses": "8. First, the experiments do not appear extensive enough to demonstrate the robustness of the proposed methods. The results show mixed performance. I encourage the authors to evaluate the approach on more datasets and provide a clearer summary of its key benefits.\n\n9. In Table 1, it would be better to also show: 1) To what extent are the confidence bounds accurate? 2) How does the accuracy differ between continuous and integer variables?\n\n10. In Table 4 and appendix, the presentation of results involves many empty rows marked with '-' . This is not effective in terms of comparision with baseline. It would be clearer to report all results using convergence figures, similar to Figure 2, as the main comparisons.", "relation_to_broader_scientific_literature": "It is related to the optimization community.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Overall, the paper has several strengths. It addresses an important real-world problem relevant to industrial applications, and the proposed idea appears novel and conceptually sound. However, more effort is needed to refine the presentation, expand the experiments, and better summarize the key insights and takeaways beyond purely performance comparison.", "other_comments_or_suggestions": "Please refer to the above. Correct me if I was wrong.\n\nThere are also lots of minor issues or typos: For example, Figure 2 is not referenced anywhere in the paper, making it unclear how it contributes to the discussion. In Table 4, there is an inconsistency where, in some cases, the absolute gap is larger while the relative gap is smaller.", "questions_for_authors": "* What is the rationale behind using binary representation and logarithmic transformation? Are there any experimental results supporting their effectiveness?\n* Do lower and upper bounds vary across different types of variables? Are there observable patterns in how tight these bounds become after training and across differnt optimization stages? Do these patterns differ between continuous and integer variables?\n* Are all eight GPUs used for both training and inference?\n* Are there any repair mechanisms for infeasible solutions? Can Thompson Sampling adaptively learn to resolve infeasibility over time?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "72lmwJUf6y", "reviewer": "Reviewer_L6hn", "summary": "The paper presents a new heuristic to find primal solutions of mixed-integer linear problems (MILP). The approach is based on predicting a distribution for the value of binary variables and a multi-armed bandit approach for iterative variable fixing. The paper also considers new features for the graph-embedding of MILPs based on values at leaf nodes of historical optimal solutions. Experiments on instances of the 2023 MIP Competition measure the time to find a feasible solution as well as the relative gap for the method and several baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback and suggestions.\n## Response to Weakness 1\n**Baselines**: We will clarify in the introduction that our method primarily focuses on primal heuristics.\nHowever, 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.\n\n## Response to Weakness 2 and Question 1\n**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. \n\n**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.\n\n**SCIP settings**: The SCIP setup uses all default settings without disabling any features, including the default preprocessing and reoptimization modules.\n\n## Response to Weakness 3\n**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.\n\n|  | bnd_1|bnd_2|bnd_3|mat_1|obj_1|obj_2|rhs_1|rhs_2|rhs_3|\n|---|--|--|---|---|----|---|--|--|--|\n| GNN+LNS(PS) |0.81|inf|inf|0.23|0.00|0.51|193.04|0.00|0.00|\n| Re-GNN+LNS |0.16|inf|inf|0.23|0.00|0.21|1.04|0.00|0.00|\n| GNN+TS |0.04|0.17| 0.12|0.17|0.00|0.00 |0.00|0.00|0.00|\n| Re-GNN+TS(VP-OR) |0.02|0.11| 0.06|0.16|0.00|0.06|0.00|0.00|0.00|\n\n## Response to Weakness 4\nWe expand our experiments to include large-scale MILP experiments and add a comparison with the ML-guided LNS method of **Huang et al.** (ConPas).\n\n**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. \n\nCA:\n|  | gap_abs| gap_rel | wins|\n|---|---|---|---|\n|SCIP|24068.27|0.19|0/100|\n|Gurobi|3754.16|0.03|0/100|\n|PS+SCIP|20182.91|0.19|0/100|\n|PS+Gurobi|3754.16|0.03|0/100|\n|ConPaS+SCIP|8506.52|0.07|0/100|\n|ConPaS+Gurobi|2526.28|0.02|0/100|\n|VP-OR+SCIP(Ours)|0.00|0.00|12/100|\n|VP-OR+Gurobi(Ours)|**0.00**|**0.00**|**88/100**|\n\nIS:\n|  | gap_abs| gap_rel | wins|\n|---|---|--|--|\n|SCIP|104.92|0.05|0/100|\n|Gurobi|133.07|0.06|0/100|\n|PS+SCIP|104.57|0.05|0/100|\n|PS+Gurobi|117.62|0.06|0/100|\n|ConPaS+SCIP|30.25|0.01|0/100|\n|ConPaS+Gurobi|24.66|0.01|0/100|\n|VP-OR+SCIP(Ours)|9.57|0.00|33/100|\n|VP-OR+Gurobi(Ours)|**0.97**|**0.00**|**67/100**|\n\n## Response to Question 2\nThe 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.\n\n## Response to Question 3\n**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.\n\n**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.", "claims_and_evidence": "The paper claims to provide significant improvement in times to find feasible solutions. I have major concerns regarding the experiment setting and overall presentation of the results, which follows from an ambiguous framing of the paper’s goal and results.\n\nFirst, two of the four baselines are general MILP solvers (SCIP and Re_Tuning). These methods are not only aiming to find feasible solutions, but *proving their global optimality*. It is well-known that the latter is a much harder task than the former. The comparison with these two baselines is biased since it is assumed that the optimal value OPT is known in advance, but SCIP and Re_Tuning are spending the majority of their computational budget to find OPT and prove that it is global lower bound. The authors’ should focus primarily on baselines that are also primal heuristics.\n\nSecond, the title of the paper is “Don’t restart, Just reuse”, but they do not include the very simple baseline that “just reuses” past feasible solutions. They consider warm start approaches, but only based on previous *optimal* solutions. They should consider adding the baseline that stores all feasible solutions of past problems, sort them by objective value for the new problem, and verifies whether they are feasible. Note that such an approach is often done by default by commercial solver (e.g., Gurobi calls this the “solution pool”).\n\nThird, the paper lacks an ablation study that clearly shows the value of the different components of the final algorithm. The small experiment in Appendix C.5 focuses only on variable prediction. The ablation study should allow to critically assess the value for finding feasible solutions of (a) the new features considered for the historical problem embeddings, (b) using a GNN for initial variable prediction, and (c) the final Thomson sampling algorithm.\n\nBecause of the above concerns, I find that the experiments do not support the paper’s claims.\n\nEDIT (Post-Rebuttal): Since the above concerns have been addressed in the rebuttal, I have raised my score from 2 to 4.", "methods_and_evaluation_criteria": "See above.", "theoretical_claims": "The paper is mostly experimental, which is fine given the topic. Still, there is a theoretical claim in Appendix B regarding the relaxation mechanism: “theoretically, with enough iterations, we can ensure that the variables causing conflicts with the constraints are filtered out.” This is an interesting property that should be stated and proven formally.", "experimental_designs_or_analyses": "See “Claims and Evidence”.", "relation_to_broader_scientific_literature": "The current scope of the paper is ambiguous and broader than what is actually done. The paper presents itself as contributing to general MILP reoptimization. It counts “solved” instances whereas it is only about finding feasible solutions, and includes general MILP solvers as baselines. Yet, the core focus of the paper is presenting a new primal heuristic for reoptimization. The focus is only on feasibility. The authors should better frame their contribution in the title / introduction, and includes relevant benchmarks: primal heuristics, rather than general solvers.", "essential_references_not_discussed": "The choice of baseline method is insufficient. The experiments should include general primal heuristics such as (among others) the ML-guided LNS of Huang et al. (2024), which is cited in the paper.", "other_strengths_and_weaknesses": "While the above review is rather critical, I find the overall approach interesting and look forward to seeing it presented in a more comprehensive fashion. In particular, I find the relaxation mechanism as well as the update algorithm for Thomson sampling interesting and valuable.", "other_comments_or_suggestions": "Please adapt the terminology used when presenting the results. The general understanding is that an MILP is “solved” when a feasible solution is found *and* it is proven to be globally optimal. The current experiments measure the time to find a feasible solution.\n\nSection 4 is quite dense in terms of detail, but does not provide a high-level overview of the algorithm. It could be useful to add a pseudo-code algorithm to show the key steps of the algorithm. It is also important to specify that the algorithm is only run once, and not integrated in a branch-and-bound process as is typical of a MILP solver. A major difference is that a general MILP solver will run many different primal heuristics at different times in the solving process.", "questions_for_authors": "-\tHow did you setup SCIP? Which variation of the baselines (SCIP vs. SCIP-WS) has access to historical optimal or feasible solutions? Did you enable the reoptimization module?\n-\tWhy do you specify that the ML-based methods are end-to-end? In what ways are they end-to-end and why is it an advantage? Is your method end-to-end? \n-\tWhat is the loss function used to train the GNN? Do you propagate a gradient through the sampling step? Why/ why not?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a rather nice idea of using information during re-optimization, something that is actually rarely done currently. The reviewers agree that the approach is novel and effective. The experimental results show that the technique works on a dataset from a competition about reoptimization. The experiments also have good depth, showing different time frames. The method itself is also not so complicated, which I view as a plus.
Decision: Accept (poster)