Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming
Authors: Haoyang Liu
Jie Wang
Zijie Geng
Xijun Li
Yuxuan Zong
Fangzhou Zhu
Jianye HAO
Feng Wu
Venue: ICLR 2025 Poster (2025)
Keywords: Mixed-integer Linear Programming
Learning to Optimize
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: Leveraging machine learning (ML) to predict an initial solution for mixed-integer linear programming (MILP) has gained considerable popularity in recent years. These methods predict a solution and fix a subset of variables to reduce the problem dimension. Then, they solve the reduced problem to obtain the final solutions. However, directly fixing variable values can lead to low-quality solutions or even infeasible reduced problems if the predicted solution is not accurate enough. To address this challenge, we propose an Alternating prediction-correction neural solving framework (Apollo-MILP) that can identify and select accurate and reliable predicted values to fix. In each iteration, Apollo-MILP conducts a prediction step for the unfixed variables, followed by a correction step to obtain an improved solution (called reference solution) through a trust-region search. By incorporating the predicted and reference solutions, we introduce a novel Uncertainty-based Error upper BOund (UEBO) to evaluate the uncertainty of the predicted values and fix those with high confidence. A notable feature of Apollo-MILP is the superior ability for problem reduction while preserving optimality, leading to high-quality final solutions. Experiments on commonly used benchmarks demonstrate that our proposed Apollo-MILP significantly outperforms other ML-based approaches in terms of solution quality, achieving over a 50% reduction in the solution gap.

Published as a conference paper at ICLR 2025
APOLLO-MILP: AN ALTERNATING PREDICTION- CORRECTION NEURAL SOLVING FRAMEWORK FOR MIXED-INTEGER LINEAR PROGRAMMING
Haoyang Liu'; Jie Wang", Zijie Geng', Xijun Li Yuxuan Zong', Fangzhou Zhu?,
JianYe Hao Feng Wu
"MoE Key Laboratory of Brain-inspiri inspired Intelligent Perception and Cognition,
University of Science and Technology of China
2 Noah's s Ark Lab, Huawei Technologies
3 Tianjin University
4 Shanghai Jiao Tong University
ABSTRACT
Leveraging machine learning (ML) to predict an initial solution for mixed-integer linear programming (MILP) has gained considerable popularity in recent years. These methods predict a solution and fix a subset of variables to reduce the prob- lem dimension. Then, they solve the reduced problem to obtain the final solu- tions. However, directly fixing variable values can lead to low-qualit solutions or even infeasible reduced problems if the predicted solution is not accurate enough. To address this challenge, we propose an Alternating solving framework (Apollo that can identify and select accurate and reli- able predicted values to fix. In each iteration, Apollo-MILP conducts prediction step for the unfixed variables, followed by correction step to obtain an improved solution (called reference solution) through trust-region search. By incorporat- ing the predicted and reference solutions, we introduce a novel Uncertainty lineertaittybbaeed Error upper BOund (UEBO) to evaluate the uncertainty of the predicted values and fix those with high confidence. A notable feature of Apollo-MILP is the superior ability for problem reduction while preserving optimality, leading to high-quality final solutions. Experiments on commonly used benchmarks demonstrate that our proposed Apollo-MILP significantly outperforms other ML-based approaches in terms of solution quality, achieving over 50% reduction in the solution gap.
cetfiction-correctiin neural
INTRODUCTION
Mixed-integer linear programming (MILP) is one of the most fundamental models for combinatorial optimization with broad applications in operations research (Bixby et al., (004)), engineering (Mal et al. 2219), and daily scheduling or planning (Li et al. 2024b). However, solving large-size MILPs remains time-consuming and computationally expensive, as many are NP-hard and have exponential expansion of search spaces as instance sizes grow. To mitigate this challenge, researchers have explored wide suite of machine learning (ML) methods (Gasse et al., [002)). In practice, MILP instances from the same scenario often share similar patterns and structures, which ML models can capture to achieve improved performance (Bengio et al. 202T).
Recently, extensive research has focused on using MI. models to predict solutions for MILPs. No- table approaches include Neural Diving (ND) Nair et al. 2020 Yoon 2021 Paulus & Krause 2023) and Srredit--andSeaatt (PS) (Han et al. 2023 Huang et al. 2024). illustrated in Figure I Given MILP instance, ND and PS begin by employing an ML model to predict an initial solution. ND with SelectiveNet (Nair al. 2020) assigns fixed values to subset of variables based the prediction, thereby constructing reduced MILP problem with a reduced dimensionality of decision variables. Then, ND solves the reduced problem obtain the final solutions. However, the fixing strategy
"This work was done when Haoyang Liu was an intern at Huawei. 1 Corresponding author. Email: jiewangx edu...

---

Published as a conference paper at ICLR 2025
Neural Diving
Predict-and-Search
MILP Problem
Predict
Fix and Optimize
Predict
Search
min d'z As i Isa 17 R
Predicted
Partial
Predicted
Best
Solution
Solution
Sotution 2
Solution 2
Solution
Solution
Sabelie Prodianee
Setaske Prehicor
P
||a
a|PII
34
Predicted variables in partial solutions
B
Variables with changed values search
Variables with fixed values
Variables with values found by the solver
0 Unfixed variables
Illustration of Neural Diving (ND) and Predict-and-Seardh (PS). For given MILP prob- lem, both methods begin by using GNN predictor to generate initial solution & and construct a partial solution @[P]. . ND then fixes the variable values in this partial solution and optimizes the reduced problem. While PS searches within neighborhood around the partial solution.
Figure I:
faces several limitations. The solving efficiency and the quality of the final solutions heavily depend on the accuracy of the MI--based predictor for initial solutions (Huang et al.] 20224) but achieving an accurate ML-based predictor is often challenging due to the complex combinatorial nature of MILPs, insufficient training data, and limited model capacity. Consequently, enforcing variables to fixed values that may not accurate can misguide the search toward areas that do not contain the optimal solution, leading to low low-quality final solutions or even infeasible reduced problems. Instead of fixing variables, PS offers a more effective search strategy for a pre-defined neighborhood of the predicted partial solution, leading to better feasibility and higher-quality final solutions. The trust- region search strategy in PS allows better feasibility but is less effective than the fixing strategy in terms of problem dimension reduction, it requires larger search space.
To address the aforementioned challenges, a natural idea is to refine the predicted solutions before fixing them. We observe that the search process in PS provides valuable feedback to enhance solu- tion quality for prediction, an aspect that has been overlooked in existing research. Specifically, the solver guides the searching direction toward the optimal solution while correcting variable values that are inappropriately fixed. Theoretically, incorporating this correction yields higher precision for predicted solutions (please see Theorem
In light of this, we propose a novel MILP optimization approach, called the Alternating Prediction- Correction Neural Solving Framework (Apollo-MILP), that can effectively identify the correct and reliable predicted variable values to fix. In each iteration, Apollo-MILP conducts prediction step for the unfixed variables, followed by correction step to obtain an improved solution (called refer- ence solution) through a trust-region search. The reference solution serves as guidance provided by the solver to correct the predicted solution. By incorporating both predicted and reference solutions, we introduce a novel sincertainty-based Error upper BOund (UEBO) to evaluate the uncertainty of the predicted values and fix those with high confidence. Furthermore, we also propose straightfor- ward variable fixing strategy based on UEBO. Theoretical results show that this strategy guarantees improved solution quality and feasibility for the reduced problem. Experiments demonstrate that Apollo-MILP reduces the solution gap by over 50% across various popular benchmarks, while also achieving higher-qualin solutions in one-third of the runtime compared to traditional solvers.
We highlight main contributions as follows. (1) A Novel Framework. Apollo-MILL is the first framework to incorporate a correction mechanism to enhance the precision of solution predictions, enabling effective problem reduction while preserving opti- mality. (2) Investigating Effective Problem Reduction Techniques. We rethink the existing problem- reduction techniques for MILPs and establish a comprehensive criterion for selecting an appropriate subset of variable values to fix, combining the advantages of existing search and fixing strategies. (3) High Performance across Various Benchmarks. We conduct extensive experiments demonstrating Apollo-MILP' strong performance, generalization ability, and real-world applicability.
MILP Solving
2 RELATED WORKS
ML-Enhanced Branch-and-Bound Solver In practice, typical MILP solvers, such SCIP AAcheererg 2009) and Gurobi (Gurobi Spptmization|20222 1 are primarily based on the Branch-and- Bound (B&B) algorithm. ML has been successfully integrated enhance the solving efficiency of
2

---

Published as a conference paper at ICLR 2025
these B&B solvers (Bengio et al. 2021 Li et al. 2024a Gasse et al., 2022 Scavuzzo et al. 2024
Specifically, many researchers have leveraged advanced techniques from imitation and reinforce- ment learning to improve key heuristic modules. A significant portion of this work aims to learn
heuristic policies for selecting variables to branch on (Khalil et al. 2016; Gasse et al.
2019;
Cupta
et al.
2020 Zarpellon et al. [202]] Cupta al. 2022 Scavuzzo al. 2022] Lin al.
2024
Zhang
et al.
2024; Kuang et al. 2024). selecting cutting planes (Tang et 2020 Wang ct al.
2023b
2024b
Huang et al., 2022 Balcan al., 2022 Paulus et 2022 Ling al. 2024 Puigdemont
et al.
2024). and determining which nodes to explore next (He et al.
et al. [202]] Liu
al.
2024c). These ML-enhanced methods have demonstrated substantial improvements in solving
efficiency. Additionally, extensive research has been dedicated to boosting other critical modules in
B&B algorithm, such as separation (Li et al. 2023), scheduling of primal heuristics (Khalil al.)
2017
Chmiela et al. (021), presolving (Liu et al.) 2024a), data generation (Geng et al. [2023] Liu
ct al. 2023a 2024b) and large ncighborhood search (Song et al. 2020; Wu et al. 2021 Sonnerat
al. 2021] Huang ct al. 2023). Beyond practical applications, theoretical advancements have also
emerged to analyze the expressiveness of GNNs for MILPs and LPs (Chen et al.)
2023a b). as well
to develop landscape surrogates for ML-based solvers (Zharmagambetov et al.
2023)
ML for Solution Prediction
Another line of research leverages ML models to directly predict
solutions (Ding et al., 2020 Yoon, 2021; Khalil et al. 2022 Paulus & Krause [0033] Zeng et al.
2024 Cai et al. 2024 Li al. 2025] Geng et al. 2025). Neural Diving (ND) et al. (2020) is pioneering approach in this field. Specifically, ND predicts partial solution based on coverage rates and utilizes SelectiveNet to determine which predicted variables to fix. To enhance the quality of the final solution, subseguent methods incorporate search mechanisms, such as trust-region search (PS) Han et al. 2023); Huang et al. (2024) and large neighhorhood search [Sonnerat et al. (202T); Ye et al. (2023 2024) with sophisticated neighborhood optimization techniques. In this paper, focus on ND and PS, both of which have gained significant popularity in recent years.
PRELIMINARIES
3.1 MIXED INTEGER LINEAR PROGRAMMING
mixed-integer linear programming (MILP) defined as follows,
min #ER"
c. TT.,. xx
Ax A b, u R
(1)
where denotes the n-dimensionaa decision variables, consisting of p integer components and - continuous variables. The vector с E I" denotes the coefficients the objective function, e Rmx* is the constraint coefficient matrix, and b R.m represents the right-hand side terms of the constraints. The vectors E (IR U (- and u E (R U (+00})) specify the lower and upper bounds for the variables, respectively. programming with æ E {0, 1)2 x -R for simplification, as it can be easily generalized to general MILPs using the well-established modification techniques proposed in Nair al. (0020)
is reasonable that PS primarily focuses on mixed-binary
3.2 BIPARTITE GRAPH REPRESENTATION FOR MILPS
A MILP instance can be represented as weighted bipartite graph g = (W U.VE) Gasse et al. 2219), as illustrated in Figure 2 this bipartite graph, the two sets of nodes, W and V. represent the constraints and variables in the MILPP instance, respectively. An edge is constructed between constraint node and a variable node if the variable has a nonzero coefficient in the constraint. For further details on the graph features utilized in this paper, please refer to Appendix B
3.3 PREDICT-AND-SEARGE
Predict-and-Seane (PS) Han et al. (003) is a two-stage MILP optimization framework that uti- lizes machine learning models learn the Bernoulli distribution for the solution values of binary variables. It then performs a trust-region search within a neighborhood the predicted solution à to enhance solution quality. Given a MILP instance I, PS considers approximating the solution
3

---

Published as a conference paper at ICLR 2025
distribution q(x [I) by weighing the solutions with their objective value,
exp(-E(xx I))
(C x, if x is feasible, +00, otherwise,
q( I) Ex'es exp(-Et E(),
where the energy function E(x,I)
and S is collected set of optimal or near-optimal solutions. PS learns the solution distribution using a GNN model pg and computes the marginal probability ps(æ | Σ) to predict a solution. To simplify the formulation. PS assumes that the variables are independent, as described in Nair et al. (2020), i.e., po(a: T) P Po(a; I). PS then selects hn binary variables with the highest predicted marginal values po I) and fixes them 1. Similarly, PS fixes ko binary variables with the lowest marginal values to O. The hyperparameters ko and Kj are called partial solution size parameters, and we denote the fixed partial solution as a a[P], where P is the index set for the fixed variables with kg + k1 elements. Instead of directly fixing the variables a &[P). PS employs a traditional solver. such as SCIP or Gurobi, to explore the neighborhood Bp (P). A) of the predicted partial solution E[P] in search of the best feasible solution. Here A represents the trust-region radius (neighhorhood parameter), and ( A) = (a: E IR. | a: P|]l1 I A} is the trust region. The neighborhood search process is formulated as the following MILP problem, referred to as the trust-region search problem.
min EER"
C cTx,,
s.t.
Ax < b, S x u.
(2)
x <| E Br ( [P), A). RM-P.
Notice that PS reduces to ND (without SelectiveNet) when the neighborhood parameter = O.
4 THE PROPOSED ALTERNATING PREDICTION- FRAMEWORK
"How to identify and fix a high-quality partial solution" is a longstanding challenge for ML-bbaed solution prediction approaches. Unlike existing works that primarily focus enhancing the pre- diction accuracy of ML models, we offer a new perspective by identifying and selecting the correct and reliable predicted values to fix, thereby improving the quality of final solutions and overall solving efficiency. The proposed Apollo-MILP framework alternates between prediction (Sec- tion [4.I) and correction (Section 4.2) steps, progressively identifying high-confidence variables and expanding the subset of fixed variables. As the algorithm proceeds, we obtain sequence of MILPs ( + [11 + ... + I(K) with fewer decision variables, where the superscripts {(k) k = 0, ... ,K} is the iteration number. The overview of our architecture in Figure
As shown in Figure 2 during the t iteration, Apollo-MILP processes a MILP [(k), which may be either the original problem or a reduced version. In this section, we assume that the prediction and correction steps are performed within the 4tth iteration. Therefore, we simplify the notation by omitting the superseript
(k) without leading to misunderstanding For example, we denote the predicted solution by z instead of (4).
4.1 PREDICTION STEP
In each prediction step, our goal is to predict the solution for the current MILP problem I, which is represented as bipartite graph, as discussed in Section 3.2
We employ GNN- solution predictor pe to predict the marginal probabilities of values pe (æ I) for binary variables in the optimal solution, similar to the method employed in PS (Han et al., 2023 Assuming independence among the variables, the predictor outputs the probability that the variable equals i.e., Po (a:; = I) for I,....,
As mentioned above, the predictor takes either the original or reduced MILP problems input. However, the distribution of the reduced problems may differ from that of the original problems. To address this issue, we employ data augmentation to align the distributional shifts. Specifically, for a given MILP instance I in the training dataset, we collect a set Sy of m optimal or near-optimal solutions approximate the solution distribution q(z Z) mentioned in Section 3.3 We then randomly sample a solution x" from this solution pool Sz, along with a subset of variables from I. We fix the selected variables to the corresponding values in x² generate reduced instance T'.
4

---

Published as a conference paper at ICLR 2025
Original 179
(8)
I(
Solve
Reducing
sao cle 15 S
assa desss iss agmin ah x
sáde dfe 15 S. ap a =
Fixing
Solver
Prediction Step
Correction Step
Reftnaaee sakslas
Variables fixed valurs
Sodation 8
Setatie
Predicted vuriables the sulutions
GNN Tredkter
Variatle Finleg
Variables with changed values
Bipartite Graph (Reduced)) Problem
Nig + 4p.sl
Trust Region Srarch
Vartuble Fixing Strategy
Problem Reduction
L1
Unfived variables
Solution Prediction
The overview of Apollo-MILP. Apollo-MILP operates through an iterative process that alternates between prediction and correction steps to reduce the original MILP problem progres- sively. In the prediction step, Apollo-MILP (1) employs a GNN to generate a partial solution. In the correction step, (2) trust region-based search is conducted to refine this solution obtain the reference solution. (3) The proposed variable fixing criterion, UEBO, is then calculated to identify which variables should be fixed. (4) Finally, we reduce the problem dimension by enforcing the selected variable values to fix values.
Figure 2:
For each reduced instance I' we also collect m optimal or near-optimal solutions to estimate the solution distribution q(x I'). All instances and solutions are combined, resulting in an enriched training dataset denoted as DD
To calculate the prediction target for training, we construct the estimated probability target vector (p(x) = p(æ2 = I), p(xn = Z)) Here, we let
- exp(-cTxx)
p: = p(x; I) = Ex'ss, exp(-ee cc x')
be the probability of variable æ; being assigned the value 1, given the instance I from the enriched dataset and the solution set Sz. Finally, the predictor pe is trained by minimizing the cross-entropy loss (Han et al. 2023)
(()) = D
1
Σ
pp log =1 (1 -p:) log(1 po( = Z))).
(4)
(I,SZ)ED
4.2 CORRECTION STEP
The correction step aims to improve the partial solutions by identifying and discarding the inaccurate
predicted variable values that were inappropriately fixed. Specifically, we (1) leverage a trust-region search the partial solution for refined solution reference for subsequent operations, (2)
introduce novel uncertainty-based metric to determine which subset of variables to fix, and (3) enforce the selected variables fixed values for dimension reduction.
To begin with, we establish the following notations. Given MILP instance I, let g( ( represent the distribution of the optimal solution, and q<x (ē, Z) denote the distribution of the reference lution given instance I and predicted solution æ. The notation x: [P] implies that the partial solution [P] has the same variable values as the index set P.
Trust- Regiin Search We leverage the solver as corrector to improve the predicted solutions via trust-region search. Formally, given the predicted marginal probabilities Pe I), we solve the MILP problem 2 with predefined hyperparameters (ko, AI, A), which is similar to the search process in PS. this process, the partial solution to be fixed during the search is &(P). The best primal solution à q(x= áz, I) found by the solver has values ă [P] for the variable index set P.
5

---

Published as a conference paper at ICLR 2025
Correction Criterion The solution z' obtained through the trust-region search serves refer- ence to improve the solution quality, called the reference solution. Then, we need to determine which variables to fix and the values they should be assigned. To evaluate the reliability of the predictions for each variable, a natural approach is to compute the distributional discrepancy be- tween the optimal and predicted solutions, specifically DKL. (2o [)]]g Z)), where we have assumed the independence between different variables. Here the (conditional) Kullback-Leibler (KL) divergence is defined to be DKL (g) = Ex P(Vx) plys) for distributions p, 4 and vari- able y taking values in {yr: 92. ... y/k. ... }. However, during testing, the optimal solution is not available, rendering the computation of the KL divergence intractable. Fortunately, we propose an upper bound to estimate the KL divergence that utilizes the available reference solutions.
Proposition 1 (Uncertainty-Bee Based Error Upper Bound). We derive the following upper bound for the KL divergence between the predicted marginal probability pe (2; I] and optimal solution distribution q(z; I), utilizing po (x; [) and the reference solution distribution g I;,I),
DEL (po(x) [x)g I)) S ((po((; I))
+d(pe [.; [], 9(2; 2 I))
(5)
Target Distance
Prediction Uncertainty
Prediction Correction Discrepancy
(og(p((=)) for variable y taking values in {11. 32. : Ykk ... "....... J. and d((..)) represents the (conditional) cross-entropy loss of distributions with d(p, 4) = - Ex ((k)) ) log(p(u))).
where HH(-) denotes the entropy with H(p) E Mlyg))
We define the upper bound in Equation (5) as the Uncertainty- -bsed Error upper BOund (UEBO), represented as UEBO(p, q) == H(p)+d(pp. +d(p.g) for distributions p and q. The first term H(po (a; I)) on the right-hand side of Equation (5), referred to as prediction uncertainty, reflects the confidence of the predictor in its predictions. lower negative entropy value indicates lower uncertainty and greater confidence in the predictor pe. The second term d(pe(x; I), g(x; Z), called the prediction-correction discrepancy, quantifies the divergence between the predicted and reference solutions. A larger discrepancy suggests that further scrutiny of the predicted results is necessary. We will now discuss why UEBO has the potential to be an effective metric for selecting which variables to fix.
1. Providing an upper bound of the intractable KL divergence DEL (po(a; []]((<>; [)).
During testing, the distribution of the optimal solution ((2; Σ) is generally unknown, making the computation of this KL divergence intractable. Instead, UEBO offers a practical estimation by utilizing the available distributions po (ar, (), d;
2. Estimating the discrepancy between the solutions. UEBO aims to penalize variables that exhibit substantial prediction uncertainty or significant disagreement, indicating the reliability of the predicted values.
Problem Reduction. We begin by selecting variables with low UEBO according to the correc- tion rule, low UEBO indicates higher reliability and greater potential for high-quality solutions. Consequently, we can be more confident in fixing these variables to construct a partial solution Corr ['] F(x PI. [P)). referred to the corrected partial solution. Specifically, the correc- tion operator F takes in the predicted and reference partial solutions é PP) and & P] and identifies a new index set P' c P of variables to fix, along with their corresponding fixed values. Finally, arrive at the following reduced problem for the next iteration.
min æER
c_ cTx,,
s.t.
Ax S b x u
(6)
x P x Corr C
I E x R-
Furthermore, to accelerate the convergence, we can introduce a cut e J < e a into the reduced problem to ensure monotonic improvement.
4.3 ANALYSIS OF THE FIXING STRATEGY
This part is organized as follows. (1) We begin by introducing the concept of prediction-correttii consistency for variable and illustrating its close relationship with UEBO. (2) We propose straightforward strategy F for approximating UEBO and fixing variables. (3) We analyze the ad- vancement properties of Apollo-MILP incorporated with the proposed fixing strategy.

---

Published as a conference paper at ICLR 2025
(1) UEBO and Prediction-Corrrectio Consistency To provide deeper insight into UEBO, first introduce the concept of prediction-corrcction consistency as follows.
Definition 1. We call a variable æ; prediction-correction consistent if the predicted and reference partial solutions yield the same variable value, i.e., át ã;. Furthermore, we define the prediction- correction consistency of a variable as the negative of the prediction-correciin discrepancy, given by -d(po(2t (a; I), ((p: d;; I)).
We investigate the relation between UEBO and prediction-correctionn consistency. Our findings in- dicate that prediction-correction consistency serves as a useful estimator of UEBO, as demonstrated in Theorem 2 with the proof available in Appendix C.2
Theorem 2 (UEBO and Consistency). Given variable H; UEBO is monotonically increasing discrepancy. Therefore, UEBO decreases as the prediction-
with respect to the correction consistency increases.
Theorem 2 illustrates that to compare the UEBOs of two variables, it suffices compare their cndlitiion-oorectionn consistencies.
(2) Variable Fixing Strategy We define the following consistency-basee variable fixing strategy given the predicted and reference partial solutions, [t]] and æ [P] Specifically, we let
p' {i E P 2 = x<"r
=[P'] =[P'].
The fixing strategy outlined in Equation ( fixes the variables that are prediction-correctio con- sistent. We will demonstrate the significant advantages of this proposed variable fixing strategy compared those based solely on predicted or reference solutions, emphasizing its ability fur- ther enhance precision. We present the pseudo-code of Apollo-MILP in Algorithm
(3) Advancement of the Fixing Strategy Let q(x; T, C;,, I) be the marginal distribution of the optimal solution for variable Tt, given the predicted value Φ; and reference values H;. We outline the following consistency conditions. The condition is motivated by a classical probabilistic problem: two students provide the same answer to a multiple-choice question respectively, then the answer is more likely to be correct (see Appendix [rpendix[B.]]pp [B. for more details). Analogous to the problem, the condition is intuitive and straightforward: we have greater confidence in the precision of the prediction y(a; = 1 Ø = 1. 1, I) for the optimal variable value nf when the predicted and reference values, 2; and I,, yield the same result.
Assumption (Consistency Conditions). Consistency between the predicted and reference values for variable æ; enhances the likelihood of precisely predicting the optimal solution, iee.
((2; = i; = 1, = 1, I) 2 ( = 1 ã; = 0, x; = I, and 1, = 1,
(8)
q(x:
a.; 1, a = O,
Based on the above conditions, we analyze the effects of fixing the prediction ceddiction-core correction consistent variables. The proposed strategy ensures greater precision in identifying the optimal variable value. Theorem (Precision Improvement Guarantee). Suppose the consistency conditions (8) hold. Then, the prediction precision for variables with consistent results g(æ; = 1 i; 1, 2 = I,I) is higher than that of variables based solely on the predicted or reference solutions, i.e..
((2: = 1 3. = 1, = 1,I) 2 q(x; = =1| = 1, and
(9)
q(>; = x. = 1, 1.I) 2 g = =
Please refer to Appendix C.3 for the proof. Finally, we examine the feasibility guarantee of Apollo- MILP. As the feasibility of PS is closely related to Problem D better feasibility than Problem 2 and hence the PS method.
we show that our method allows for
Corollary 4. Suppose select variables to fix based the strategy in Equation 77. If the trust- region searching problem 2 (the PS method) is feasible, then the corresponding reduced problem provided by Apollo- MILP will also be feasible.
EXPERIMENTS
In this part, we conduct extensive studies to demonstrate the effectiveness of our framework. Our method achieves significant improvements in solving performance (Section 5.2).. generalization abil- ity (Appendix H.S5). , and real-world applicability (Appendix H.T. Please refer to Appendix D for a detailed implementation of the methods.
7

---

Published as a conference paper at ICLR 2025
Algorithm 1: Alternating Prediction-Correde Neural Solving Framework
Input: MILP Instance I solve, the predictor pe, iteration number K, hyperparameters {(Kb)) ( [
Initialize: the reduced problem I +- I. for k in {0.-.. _K do
# Prediction Step
Obtain predicted solution & pa I(4) from the predictor pe
Determine the partial solution @ E è to fix according to (Kg (1))) # Correction Step
Construct the trust-region searching Problem over (1k) using (1) 1x(1) A (4))
k= then
Leveraging solver solve the Problem for the best solution x²
10
end
11
else
Leveraging solver to solve the Problem 2 for reference solution & q(x: $, T(K)
12
Obtain x Corr [P]] using Criterion 7
13
Fix a Corr [P*] in ((k to obtain the new reduced problem (k++1)
14
15
end
end
17
return the best solution ~*
5.1 EXPERIMENT SETTINGS
Benchmarks We conduct experiments on four popular MILP benchmarks utilized in the MI
field: combinatorial auctions (CA) (Leyton- Leytonn-rown Brown al. 2000), set covering (SC) (Balas & Ho
1980 item placement (IP) (Gasse et al.) 2022) and workload appointment (WA) (Gasse et al.
2022 The first two benchmarks are standard benchmarks proposed in (Gasse et al. 2019) and are
commonly used evaluate the performance of ML solvers (Gasse al.] 2019 Han et al. 2023
Huang et al.] 2024). The last two benchmarks, IP and WA, come from two challenging world
problem families used in NeurlPS ML4CO 2021 competition (Gasse al. 2022). We use 240
training, 60 validation, and 100 testing instances, following the settings in Han et al. 2023 Please refer Appendix F for more details the benchmarks.
Baselines We consider the following baselines in our experiments. We compare the proposed method with Neural Diving (ND) (Nair al. 2020) and Predict-and-Searte (PS) (Han al. 2023). which we have introduced in the previous sections. Contrastive al.] 2024) is strong baseline, leveraging contrastive learning to enhance the performance of PS. For ConPS, we set the ratio of positive to negative samples at ten, using low-quality solutions as negative samples. These baselines operate independently of the backbone solvers and can be inte-
(ConPS) Huang
grated with traditional solvers such as SCIP (Achterberg) (2099) and Gurobi (Gurobi Optimization] 2021). Therefore, we also include SCIP and Gurobi as baselines for a comprehensive comparison. Following Han et al. (023), Gurobi and SCIP are set to focus finding better primal solutions.
Metries We evaluate the methods on each test instance and record the best objective value OBJ within 1,000 seconds. Following the setting in Han et al. (2023), we also run single-thread Gurobi for 3,600 seconds and denote the best objective value as the best-known solution (BKS) to approxi- mate the optimal value. However, we find that our method, when built on Gurobi, solutions within 1,000 seconds than Gurobi achieves in 3,600 seconds for the IP and WA bench- marks. As result, benchmarks. We define the absolute primal gap as the difference between the best objective found by the solvers and the BKS, expressed as gapats == |OJJ BKS). Within the same solving time, lower absolute primal gap indicates stronger performance.
identify better
the best objectives obtained by approach the BKS for these two
Implementations In our experiments, we conduct four rounds of iterations. The time allocated for each iteration is 100, 100, 200, and 600 seconds, respectively. We denote the size of the partial
solution in the thh iteration by k(() k
(8) (.(6) with 2(0) variables fixed 0 and x(3) to 1, and allow
8

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of solving performance between our approach and baseline methods, under 1, 000s time limit. We build the ML approaches on Gurobi and SCIP, respectively. As we choose the challenging benchmarks with large-size instances, the solvers reach the time limit in all the experiments. We thus report the average best objective values and the absolute primal gap. "f" indicates that higher is better, and "J" indicates that lower better. We mark best values in bold. We also report the improvement of our method over the traditional solvers in terms of gapabe We find our method with a 1,000s runtime can outperform Gurobi with 3,600s runtime in IP and WA.
CA (BKS 97616.59)
SC (BKS (22.95)
IP (BKS 8.90)
WA (BKS 704.8)
Obj f
gapabs
Obj
gapabs
Obj |
gapaba
Obj
gapabs
Gurobi
97297.52
319.07
123.40
0.45
9.38
0.48
705.49
0.61
ND+Gurobi
96002.99
1613.59
123.25
0.29
9.33
0.43
705.70
0.82
PS+Gurobi
97358.23
258.36
123.30
0.35
9.17
0.27
705.45
0.57
ConPS+Gurobi
97464.10
152.49
123.20
0.25
9.09
0.19
705.37
0.49
Ours+Gurobi
97487.18
129.41
123.05
0.10
8.90
0.00
704.88
0.00
Improvement
52.2%
77.8%
100.0%
100.0%
SCIP 96544.10
1072.48
124.80
1.85
14.50
5.60
709.62
4.74
ND+SCIP
95909.50
1707.09
123.90
0.95
13.61
4.71
709.55
4.67
PS+SCIP
96783.62
832.97
124.35
1.40
14.25
5.35
709.39
4.51
ConPS+SCIP
96824.26
792.33
123.90
0.95
13.74
4.84
709.33
4.45
Ocrs+SCIP
96839.34
777.25
123.50
0.55
12.86
3.96
709.29
4.41
Improvement
27.5%
70.2%
29.2%
6.9%
CA
IP
WA
10-1
10-4
Average Primal
10-2
10
10-1
10-1
10-1
1000
Time (s)
Time (5)
Time (s)
Time (s)
Gurabi
Gurabl
PSrGuobbi
ConPs Gurbbbl
Gurbbl
Figure 3: The primal gap of the approaches the solving process proceeds. Our methods implemented using Gurobi, with a time limit set to 1,000s, and we average the results across 100 testing instances. A lower primal gap for our method indicates stronger convergence performance.
( of the fixed variables to be flipped during the trust-region search. The total size of the partial solutions is given by kix Σi A00), which sums the partial solution sizes across all iterations. More details on hyperparameters are in Appendix G
5.2 MAIN EVALUATION
Solving Performance To evaluate the effectiveness of the proposed method, we compare the solv- ing performance between our framework and the baselines, under a time limit of 1,000 seconds. Ta- ble presents the average best objectives found by the solvers alongside the average absolute primal gap. The instances in the IP and WA datasets possess more complex structures and larger sizes, making them more challenging for the solvers. While ND demonstrates strong performance in the CA and SC datasets, it falls short in the real-world datasets, IP and WA. ConPS serves as a robust baseline across all benchmarks, indicating that contrastive learning effectively enhances the predic- tor, leading to higher-qualite predicted solutions. The results reveal that our proposed Apollo-Mal consistently outperforms the baselines, achieving the best objectives and the lowest gaps across the benchmarks. Specifically, Apollo-MILP reduces the absolute primal gap by over 80% compared to Gurobi and by 30% compared to SCIP, Furthermore, the IP and WA benchmarks, our approach identifies better solutions within 1,000s than those obtained by running Gurobi for 3,600s.
Primal Gap as a Function of Runtime Figure iillustrates the curves of the average primal gap, defined gap (BJ- BKSJ/BBSS throughout the solving process. Similar the absolute

---

Published as a conference paper at ICLR 2025
primal gap, the primal gap reflects the convergence properties of the solvers; rapid decrease in the curves indicates superior solving performance. As shown in Figure the primal gap of Apollo- MILP exhibits gradual decrease in the early stages it focuses correction steps to improve the quality of partial solutions. Subsequently, the primal gap demonstrates a rapid decline, ultimately achieving the lowest gap, which highlights Appolo-MII.P's strong convergence performance.
5.3 ABLATION STUDY
Table 2: Comparison of solving performance between our approach and different fixing strategies, under a 1, 000s time limit. We report the average best objective values and absolute primal gap. " indicates that lower is better. We
Fixing Strategies To better under- stand Apollo-MILP, we conduct ab- lation studies on the variable fixing strategies. Specifically, we imple- ment two baselines for variable fixing strategies: Direct Fixing (four rounds of direct fixing) and Multi-stage PS (four rounds of PS). We utilize the same set of hyperparameters as our method. The Multi-stage PS strategy directly fixes the variables in the pre- dicted partial solutions & P]. The Di- rect Fixing strategy directly fixes the variables in the reference partial solu- tions æ P]. The results the IP and WA benchmarks are presented in Table The results in
mark the best values in bold.
IP (BKS 8.90)
WA (BKS 704.88)
Obj
gapabs
Obj
gapabs abs
Gurobi
9.38
0.48
705.49
0.61
PS+Gurobi
9.17
0..77
705.45
0.57
Direct Fixing
9.22
0.32
705,40
0.52
Multi-stage PS
9.18
0.28
705.33
0.45
Ours+Gurobi
8.90
0.00
704.88
0.00
Table 2 show that our proposed consistency based fixing strategy outperforms the other baselines, highlighting our method's 's effectiveness. Please see Appendix HH.3 for more experiment results.
Comparison with Warm-Starting Gurobi Warm-starting is an alterna- tive to the trust-region search in P$ and our method, in which we provide an initial feasible solution to Gurobi to guide the solving process. Gurobi can search around these start solutions or partial solutions. Warm-starting is crucial baseline to help us under- stand the trust-region search. Specif- ically, we implement two methods, warm-starting PS (WS-PS) and warm- starting our method (WS-Ours). WS- PS passes the initial GNN prediction to Gurobi as a start solution, with hy- perparameters such as kn and k same as those we conduct in our main ex- periments. We also implement WS-Ours, which employs the same prediction model but replaces the trust-region search with warm-starting at each step. The results are presented in Table 19 in which set the solving time limit as 1,000s. The results show that WS Gurobi performs com- parably to PS, while WS Ours combined with Gurobi outperforms WS Gurobi, demonstrating the effectiveness of our proposed variable fixing strategy. Finally, our proposed method performs the best. The trust-region search is more effective search method that aligns well with our framework. Please see Appendix H.3 for more experiment results.
Table 3: Comparison of solving performance between our method and the warm-starting methods, under a 1, 000s time limit. We report the average best objective values and absolute primal gap. " indicates that lower is better. We mark the best values bold.
IP (BKS
WA (BKS 704.88)
Obj 4 gapabs
Obj
gaPabs
Gurobi PS+Gurobi
9.38
0.48
705.49
0.61
9.17
0.27
705.45
0.57
WS-PS+Gurobi
9.20
0.30
705.45
0.57
WS-Ours+Gurobi
9.13
0.23
705.40
0.52
Ours+Gurobi 8.90
0.00
704.88
0.00
CONCLUSION AND FUTURE WORKS
In this paper, we propose a novel ML-based solving framework (Apollo-MILP) to identify high- quality solutions for MILP problems. Apollo-MILP leverages the strengths of both Neural Diving and Predict-and-SSt -neaarc, alternating between prediction and correction steps to iteratively refine the predicted solutions and reduce the complexity of MILP problems. Experiments show that Apollo- MILP significantly outperforms other ML-based approaches in terms of solution quality, demon- strating strong generalization ability and promising real-world applicability.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors would like to thank all the anonymous reviewers for their valuable suggestions. This work was supported by the National Key R&D Program of China under contract 20222D011990 and the National Nature Science Foundations of China grants U23A20388 and 62021001.
ETHIC STATEMENT
This paper aims to explore the potential of an efficient MILP solving framework and obey the ICLR code of ethics. We do not foresee any direct, immediate, or negative societal impacts stemming from the outcomes of our research.
REPRODUCIBILITY STATEMENT
We provide the following information for the reproducibility of our proposed Apollo-MILP.
1. Method. We provide the pseudo-code of our method in Section 4.3 make our source code publicly available once the paper is accepted for publication.
Moreover, will
2. Theoretical Proof. We provide the proof of our theoretical results in Appendix C
3. Implementations. We discuss the hyperparameters in Table T0 of Appendix The infor-
mation on the implementation details can be found Appendix D
7 ACKNOWLEDGEMENT
The authors would like to thank all the anonymous reviewers for their insightful comments and valuable suggestions. This work was supported by the National Key R&D Program of China under contract 2022/DD01 19801 and the National Nature Science Foundations of China grants U23A20388 and 62021001.
REFERENCES
Tobias Achterberg. Seip: solving constraint integer programs. Mathematical Programming Compu- tation, 1:1 1:1-41, 2009.
Yinqi Bai, Jie Wang, Lei Chen, Zhihai Wang. Yufei Kuang, Mingxuan Yuan, Jianye HAO, and Feng Wu. A graph enhanced symbolic discovery framework for efficient circuit synthesis. In The Thirteenth International Conference on Learning Representations, 2025. URL https:
Egon Balas and Andrew Ho. Set covering algorithums using cutting planes, heuristics, and subgra- dient optimization: a computational study. Springer, 1980.
Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Structural analysis of branch-and-cut and the learnability gomory mixed integer cuts. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neu- ral Information Processing Systems, volume 35, pp. 33890-33903. Curran Associates, Inc., www.:/eeedd..nn.......e......eee nwwrips....... ce wwtppcppppeeeeeeeeeeeeeeee httppppeefleeepppe////0//0 -aapsspperrf--epeerrrr Conference.pdf
2022. URL
file/
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Robert E Bixby, Mary Fenelon, Zonghao Gu, Ed Rothberg, and Roland Wunderling. Mixed-intege programming: A progress report. In The sharpest cut: the impact of Manfred Padberg and his work, pp. 309-325. SIAM, 2004.
11

---

Published as a conference paper at ICLR 2025
Junyang Cai, Taoan Huang, and Bistra Dilkina. Learning backdoors for mixed integer programs with contrastive learning. In The 27th European Conference on Artificial Intelligence, 2024.
Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations. 2023a.
Ziang Chen, Jialin Liu, Xinshang Wang. and Wotao Yin. On representing mixed-integer linear programs by graph neural networks. In The Eleventh International Conference on Learning Rep- resentations, 2023b.
Antonia Chmiela, Elias Khalil, Ambros Gleixner, Andrea Lodi, and Sebastian Pokutta. Learning to schedule heuristics in branch and bound. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, volume 34, pp. 24235 24246. Curran Associates, Inc., 2021. URL https::/proceedd mew. cttpssccpppppppe/e. fi /eslepppree/222111 Fi 11t///77600031111110000000000000
Jian- Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang, Yinghui Xu, and Le Song. Ac- celerating primal solution findings for mixed integer programs based on solution prediction. In The Thirth-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirly-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020. The Tenth AAAI Sympo- sium on Educational Advances in Artificial Intelligence. EAAI 2020, New York, NY, USA, Febru- ary 7-12, 2020, pp. 1452 1459. AAAI Press, 2020. doi: 10.1609/AAALVV3400.5555 https: /tw.///oi.../. 100 6099 aaai v34 02.4102.10 12.52.5503
URL.
Huanshuo Dong, Hong Wang, Haoyang Liu, Jian Luo, Jie Wang, et al. Accelerating pde data gener- ation via differential operator action in solution space. In Forty-first International Conference on Machhne Learning, 2025.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M. Kazachkov, Elias Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris J. Maddison, Morris Christopher, Dimitri J. Papagcorgiou, Augustin Parjadis, Scbastian Pokutta, Antoine Prouvost, Lara Scavuzzo, Giulia Zarpellon, Linxin Yang, Sha Lai, Akang Wang, Xiaodong Luo, Xiang Zhou, Haohan Huang, Shengcheng Shao, Yuanming Zhu, Dong Zhang, Tao Quan, Zixuan Cao, Yang Xu, Zhewei Huang, Shuchang Zhou, Chen Binbin, He Minggui, Hao Hao, Zhang Zhiyu, An Zhiwu, and Mao Kun. The machine learning for combinatorial optimization competition (ml4co): Re- sults and insights. In Douwe Kiela, Marco Ciccone, and Barbara Caputo (eds.). Proceed- ings of the NeurIPS 2021 Competitions and Demonstrations Track, volume 176 of Proceed-
ings of Machine Learning Research, pp. 220-231. PMLR, 06-14 Dec 2022. URL https: //proceedings... mlr.. www.m.lr..rrrss.mmmmmmmmmmmmmmee
Zijie Geng, Xijun Li, Jie Wang, Xiao Li, Yongdong Zhang, and Feng Wu, A deep instance generative framework for milp solvers under limited data availability. In Advances in Neural Information Processing Systems, 2023.
Zijie Geng, Jie Wang, Xijun Li, Fangzhou Zhu, Jianye HAO, Bin Li, and Feng Wu. Differentiable integer linear programming, In The Thirteenth International Conference on Learning Represen- tations, 2025. U //ppnrreee///eeeeeeeeeee net/ wtt.:oormmmmdddPPe-
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data- driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):443-490 2021.
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33: 18087-18097, 2020.
12

---

Published as a conference paper at ICLR 2025
Prateek Gupta, Elias B Khalil, Didier Chetélat, Maxime Gasse, Yoshua Bengio, Andrea Lodi, and M Pawan Kumar. Lookback for learning to branch. arXiv preprint arXiv:2206. 2211:2206.11987, 2022.
LLC Gurobi Optimization. Gurobi optimizer. URL http://www. gurobi. com, 2021.
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xi- aodong Luo. A gon-guided predict-and-search framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2023.
He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
Taoan Huang, Aaron Ferber, Yuandong Tian, Bistra N. Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In International Conference on Machine Learning. 2023. URL. https:://p/pp semant oscho ar. org/ CorpusTD:
256598329
Taoan Huang, Aaron M Ferber, Arman Zharmagambetov, Yuandong Tian, and Bistra Dilkina. Con- trastive predict-and-search for mixed integer linear programs. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.). Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 19757-19771. PMLR, 21-27 Jul 2024. URL https:://proces
ngs. ml www.sress//eeee v235 https//////2///aag22222/3 http///aaag2....m html
Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning select cuts for efficient mixed-integer programming.
Pattern Recognition, 123:108353, 2022. ISSN 0031-3203. doi:
2021.108353. URL https: www. sci www.sciencedii encedi rect cct.//scieence/araiclee/iiiiiiii
S0031 #2032100533
Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Dale Schuurmans and Michael Wellman (eds.), Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pp. 724-731, United States of America, 2016. Association for the Advancement of Artificial Intelligence (AAAI). URL /ttp:://://// www. aaai org/ Conferencee CowferenceeeeaAt// aaaii 6. php, AAAI Conference on Artificial Intelligence 2016, AAAI 2016; Conference date: 2216 Through 17-02-2016.
Elias B. Khalil, Bistra Dilkina, George L. Nemhauser, Shabbir Ahmed, and Yufen Shao. Learning to run heuristies in tree search. Proceedings of the Twent--ixxh International Joint Conference on Artificial Intelligence, LJCAI-17, pp. 659 666, 2017. doi: 10.24963/jjcai.20111 2017//2.
URL http:::::
7/doi. oro/1oorg/10. 100 200.e/244333jj... /tt.:////caaa..111/991
Elias B. Khalil, Christopher Morris, and Andrea Lodi. MIP-GNN: A data-driven framework for guiding combinatorial solvers. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual
Event, February 22- -Mrrh 1, 2022, pp. 10219-10227 AAAI Press, 2022. doi: 10.1609/AAAI.
V3619.21262. URL httpt:tt////m /oo.doo.ooo http:///oooooggo/ooooooo 609 /waai.aaaa... http:/aaaaiiaii......... www.9..6..... 21262
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URI. https:
//openreview. net/forum http:r/rwww...eee....aaa/a/aa//s
Yufei Kuang, Jie Wang, Haoyang Liu, Fangzhou Zhu, Xijun Li, Jia Zeng. HAO Jianye, Bin Li. and Feng Wu. Rethinking branching on exact combinatorial optimization solver: The first deep symbolic discovery framework. In The Twelfth International Conference on Learning Represen- tations, 2024.
Abdel Ghani Labassi, Didier Chetelat, and Andrea Lodi. Learning to compare nodes in branch and bound with graph neural networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Infor- mation Processing Systems, volume 35, pp. 32000-32010 Curran Associates. Inc., 2022. URL hrg.aaaeeeeSSaaaaaaaaaaaaaaaaaar
f htte:ccfStb118377esefffaeeeeeeee
13

---

Published as a conference paper at ICLR 2025
Kevin Leyton- Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combina- torial auction algorithms. In Proceedings of the 2nd ACM Conference on Electronic Commerce, pp. 66-76, 2000.
Sirui Li, Wenbin Ouyang, Max B Paulus, and Cathy Wu. Learning to configure separators in branch- and-cut. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Xijun Li, Fangzhou Zhu, Hui-Ling Zhen, Weilin Luo, Meng Lu, Yimin Huang, Zhenan Fan, Zirui Zhou, Yufei Kuang, Zhihai Wang. Zijie Geng. Yang Li, Haoyang Liu, Zhiwu An, Muming Yang, Jianshu Li, Jie Wang, Junchi Yan, Defeng Sun, Tao Zhong, Yong Zhang, Jia Zeng, Mingxuan Yuan, Jianye Hao. Jun Yao, and Kun Mao. Machine learning insides optverse ai solver: Design principles and applications, 2024a.
Yixuan Li, Wanyuan Wang. Weiyi Xu, Yanchen Deng, and Weiwei Wu. Factor graph neural network meets max-sum: A real-time route planning algorithm for massive-scale trips. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 1165- 1173, 2024b.
Yixuan Li, Can Chen, Jiajun Li, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, and Wanyuan Wang. Fast and interpretable mixed-integer linear program solving by learning model reduction. Proceedings of the AAAI Conference Artificial Intelligence, 2025.
Jiacheng Lin, Meng XU, Zhihua Xiong, and Huangang Wang. CAMBranch: Contrastive learning
with augmented MILPs for branching. In The Twelfth International Conference on Learning Representations, 2024. URL https: : //oppprreviieee net/ / wtt.mmmmc--kkktt00.-2
Haotian Ling, Zhihai Wang, and Jie Wang. Learning to stop cut generation for efficient mixed- integer linear programming. Proceedings of the AAAI Conference on Artificial Intelligence, 38 (18):20759-20767. Mar. 2024. doi: 10. 16.1669/aaii..... 333108330 URL htttts:////// aaai....s....................... org/index.phr
Chang Liu, Zhichen Dong, Haobo Ma, Weilin Luo, Xijun Li, Bowen Pang. Jia Zeng, and Junchi Yan. L.p-MIIP: Learning to presolve for mixed integer programming. In The Twelfth Interna- tional Conference on Learning Representations, 2024a. URL htttps://epenreiieeee
Forum?id 2errum?id-McfbbKnTT3
Haoyang Liu, Yufei Kuang, Jie Wang, Xijun Li, Yongdong Zhang, and Feng Wu. Promoting generalization for exact solvers via adversarial instance augmentation, 2023a. URL https:
/abp///b///// //arxiv.orq/ abs /abbs//e 221123111.111... 14161
Haoyang Liu, Jie Wang. Wanbo Zhang, Zijie Geng, Yufei Kuang, Xijun Li. Bin Li, Yongdong Zhang, and Feng Wu. MILP-studio: MILP instance generation via block structure decomposition. In The Thirty- Annual Conference Neural Information Processing Systems, 2024b. URL. net forum -iw.:mmdd-dw333w3
Hongyu Liu, Haoyang Liu, Yufei Kuang, Jie Wang, and Bin Li. Deep symbolic optimization for combinatorial optimization: Accelerating node selection by discovering potential heuristics. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 2067- 2075, 2024c.
Qiyuan Liu, Qi Zhou, Rui Yang, and Jie Wang. Robust representation learning by clustering with bisimulation metrics for visual reinforcement learning with distractions. Thirty-Seventh AAAI Conference on Artificial Intelligence, pp. 8843-8851 AAAI Press, 2023b.
Kefan Ma, Liquan Xiao, Jianmin Zhang, and Tiejun Li. Accelerating an based sat solver by software and hardware co-design. Chinese Journal of Electronics, 28(5)95539611, 2019.
Wenyu Mao, Jiancan Wu, Haoyang Liu, Yongduo Sui, and Xiang Wang. Invariant graph learn- ing meets information bottleneck for out-of-distribution generalization, 2024. URL https: / www.aii.rg.aas///ee..aa.aaaaaa
01697
Wenyu Mao, Shuchang Liu, Haoyang Liu, Haozhe Liu, Xiang Li, and Lantao Hu. Distinguished quantized guidance for diffusion-based sequence recommendation. THE WEB CONFERENCE 2025, 2025a. URL wtRl/tttss.// httpa:::////eeevviieeeee wtt.eeeeeeeeoooommd.....omo
14

---

Published as a conference paper at ICLR 2025
Wenyu Mao, Jiancan Wu. Weijian Chen, Chongming Gao, Xiang Wang, and Xiangnan He. Re- inforced prompt personalization for recommendation with large language models, 2025b. URL htttss//aaxiv wwtp/a////0....a11
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan D'Donoguue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint wrXi:22012.13349 2020.
Max Paulus and Andreas Krause. Learning to dive in branch and bound. In A. Oh, T. Naumann, A. Globerson, Saenko, M. Hardt, and S. Levine (eds.). Advances Neu- ral Information Processing Systems, volume 36, pp. 34260-34277. Curran Associates, Inc.,
2023. URL https::/pproeed www. wttppppr.pppppppppppppppp.ppp.ep http://ppppe..ilee/////////2/22/ file elee/e http:///www.ccoc0000/00000000000
pdff
Max B. Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris J. Maddison Learning to cut by looking ahead: Cutting plane selection via imitation learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML. 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 17584-17600. PMLR, 2022. html
URL
mlr http://pooo.ccooo..o.eeeeeeeaeaa
Pol Puigdemont, Stratis Skoulakis, Grigorios Chrysos, and Volkan Cevher. Learning to remove cuts in integer linear programming. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.). Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 41235 41255. PMIR, 21-27 Jul 2024. URI. 2ress/v2333 http:///wiidmmooooo.ee.eemmm.mee
ngs. aog..m..
html
Lara Scavuzzo, Feng Chen, Didier Chetelat, Maxime Gasse, Andrea Lodi, Neil Yorke- Smith, and Karen Aardal. Learning to branch with tree mdps. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural In- formation Processing Systems, volume 35, pp. 18514-18526. Curran Associates, Inc., 2022. URL httpps://procceeddg.....ee. neurips cct wttp:pppppcpppppppp.pppppeppeeee
fi file/556lkc662228666442222222222 http:///e..eeeeeeee/////ee/////a httppperrriilleeapee///22..
Lara Scavuzzo, Karen Aardal, Andrea Lodi, and Neil Yorke-Smith. Machine learning augmented branch and bound for mixed integer linear programming. Mathematical Programming, Aug 2024. ISSN 1436-4646. doi: 10. 1011000001100-0244 02140-2213-----
URL. htttt:://////// http:///.......111.000001000
s
Zhihao Shi, Xize Liang, and Jie Wang. LMC: Fast training of GNNs via subgraph sampling with provable convergence. In The Eleventh International Conference on Learning Representations, 2023.
Zhihao Shi, Jie Wang, Fanghua Lu, Hanzhu Chen, Defu Lian, Zheng Wang, Jieping Ye, and Feng Wu. Label deconvolution for node representation learning on large-scale attributed graphs against learning bias. IEEE Transactions on Patlern Analysis and Machine Intelligence, 46( (6(12):11277 11286, 2024. doi: (119///AA....2224445555...0
Zhihao Shi, Jie Wang. Zhiwei Zhuang, Xize Liang, Bin Li, and Feng Wu. Accurate and scal- able graph neural networks via message invariance. In The Thirteenth International Confer- ence on Learning Representations, 2025. URL http::t /ttp:///pppeeiiieeee / net. fott//orrmmidd UgrFPhcmFp
Jialin Song, ravi lanka, Yisong Yue, and Bistra Dilkina. A general large neigh- borhood search framework for solving integer linear programs, In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.). Advances in Neural In- formation Processing Systems. volume 33, pp. 20012 20023. Curran Associates, Inc., 2020. URL wtt.tttesss/pppcecc.....eerrr.o. http://eerrr....ooooooooeeeeeeee ffles/papee/2020//
Fi F1143338ccc532222200044444444333
15

---

Published as a conference paper at ICLR 2025
Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning large neighborhood search algorithm for mixed integer programs. ArXiv, abs/2107.10201, 2021. URL
httpss//appi semanticschooaaa..
wttp/oorpssaao. 236154745
Yongduo Sui, Wenyu Mao, Shuyao Wang, Xiang Wang, Jiancan Wu, Xiangnan He, and Tat-Seng Chua. Enhancing out-of-distribution generalization on graphs via causal attention learning. ACM Trans. Knowl. Discov. Data, 18(5), March 2024. ISSN 1556-4681. doi: 10. 1411136444492.. URL
https://ee wwo..oogg/00 1144/3644392
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning to cut. In Hal Daumé IIII and Aarti Singh (eds.). Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 9367-9376. PMLR, 13-18 Jul 2020. URL tang20a. html
ngs mlr prwss/eessvvv. 19
Haoyu Peter Wang, Jialin Liu, Xiaohan Chen, Xinshang Wang, Pan Li, and Wotao Yin. DIG- MILP: a deep instance generator for mixed-integer linear programming with feasibility guaran- tee. Transactions on Machine Learning Research, 2024a. ISSN 2835-8856. URL https:
MywlrEaF
Jie Wang, Rui Yang. Zijie Geng, Zhihao Shi, Mingxuan Yc, Qi Zhou, Shuiwang Ji, Bin Li, Yongdong Zhang, and Feng Wu. Generalization in visual reinforcement learning with the reward sequence distribution. CoRR, abs/2302.09601, 2023a.
Jie Wang, Zhihai Wang. Xijun Li, Yufei Kuang, Zhihao Shi, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning to cut via hierarchical sequence/set model for efficient mixed-integer programming. IEEE Transactions on Pattern Analysis and Machine Intel- ligence, pp. 1-17, 2024b. doi: 10.100//AMM.2202.4427766
Zhihai Wang, Jie Wang, Qi Zhou, Bin Li, and Houqiang Li. Samplc-efficient reinforcement learning via conservative model-based actor-critic. Proceedings of the AAAI Conference on Artificial Intelligence, 36(8):8612-8622) Jun. 2022. doi: 10. 10.1609 v3w.://............... 23688.20839. URL
https://ojs aaai. org/ index.. pwwp:p/.//a//ppppppppptpppwwwaat AAAI/ wAt./aaticeeeeeee////aaa
Zhihai Wang, Xijun Li, Jie Wang. Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. In The Eleventh International Conference on Learming Representations, 2023b.
Zhihai Wang. Taoxing Pan, Qi Zhou, and Jie Wang. Efficient exploration in resource-restrieted reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8): 10279-10287, Jun. 2023c. doi: 10. 10.1609/amai.v3776 http:/a.a...7....22222. 262224. htlptttts:://oo aaai. org/ Bhedex.ppp/Aaaee
Zhihai Wang, Lei Chen, Jie Wang, Yinqi Bai, Xing Li, Xijun Li, Mingxuan Yuan, Jianye Hao, Yongdong Zhang, and Feng Wu. A circuit domain generalization framework for efficient logic synthesis in chip design. In Forty-first International Conference Machine Learning, PMLR, 2024c.
Zhihai Wang, Jie Wang, Qingyue Yang, Yinqi Bai, Xing Li, Lei Chen, Jianye HAO, Mingxuan Yuan, Bin Li, Yongdong Zhang, and Feng Wu. Towards next-generation logic synthesis: A scalable neural circuit generation framework. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024d. URL https: /ttes:://penreviees net. www.foormmi...
ZYNYhh3ocW
Zhihai Wang, Jie Wang, Dongsheng Zuo, Yunjie Ji, Xinli Xia, Yuzhe Ma, Jianye Hao, Mingxuan Yuan, Yongdong Zhang, and Feng Wu. A hierarchical adaptive multi-task reinforcement learn- ing framework for multiplier circuit design. In Forty-first International Conference on Machine Learning. PMLR, 2024c.
Zhihai Wang, Jie Wang, Xilin Xia. Dongsheng Zuo, Lei Chen, Yuzhe Ma, Jianye Hao, Mingxuan Yuan, and Feng Wu. Computing circuits optimization via model-based circuit genetic evolution. In The Thirteenth International Conference on Learning Representations, 2025.
16

---

Published as a conference paper at ICLR 2025
Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighbor- In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, volume 34, pp. 30075-30087. Curran Associates, Inc., files//apper/201/ File/ File//ccbs.s5Setreccoeeeeeeeeeee Papeee---pprpppp.
hood search policy for integer programming.
2021. URL httpps:/pprccee// ngs. neuriss cc.pspe.ccpppppeeeep httppppscppppps..cpppp......
Rui Yang. Jie Wang, Zijie Geng, Mingxuan Ye, Shuiwang Ji, Bin Li, and Feng Wu. Learning task-relevant representations for generalization via characteristic functions of reward sequence distributions. In The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,
pp. 2242-2252. ACM, 2022.
Rui Yang, Jie Wang. Guoping Wu, and Bin Li. Uncertainty-buse offline variational bayesian rein- forcement learning for robustness under diverse data corruptions. In Advances in Neural Infor- mation Processing Systems 38, 2024.
Huigen Ye, Hua Xu, Hongyan Wang. Chengming Wang, and Yu Jiang. GNN&GBDT fast optimizing framework for large-scale integer programming. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Pro- ceedings of Machine Learning Research, pp. 39864 39878. PMLR, 23-29 Jul 2023. URL
htaps://proceedingg mlr /ztp:////ass.aappppeeee///////e/
Huigen Ye, Hua Xu, and Hongyan Wang. Light-MII Solving large-scale mixed integer linear programs with lightweight optimizer and small-scale training dataset. In The Twelfth International Conference on Learning Representations, 2024.
net /forrmortm
id 2oWRumm677
Tachyun Yoon. Confidence threshold neural diving. In Advances in Neural Information Processing Systems, Competition Workshop on Machine Learning for Combinatorial Optimization, 2021.
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and-boumd search trees to learn branching policies. In Thirty- Fifth AAAI Conference on Artificial Intelligence,
AAAI 2021, Thirty-Third Conference Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. -9339 AAAI Press, 2021. doi: 10.1609/AAAI. V3515.16512. URL (tthstts:: /wo.doo.oooo org 10. 609 awwaiaaaaa.....aaaa.aaaaaaaaaaaa v3515. 11111..1111.....
Hao Zeng, Jiaqi Wang, Avirup Das, Junying He, Kunpeng Han, Haoyuan Hu, and Mingfei Sun. Effective generation of feasible solutions for integer programming via guided diffusion. In Pro- ceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '24, pp. 4107-4118 New York, NY, USA, 2024, Association for Computing Machinery. ISBN 9798400704901. doi: (0.1145/6637528.3677783.
URL http::///cl...r/110...
3637528. 3671778336773
Changwen Zhang, Wenli Ouyang, Hao Yuan, Liming Gong, Yong Sun, Ziao Guo, Zhichen Dong, and Junchi Yan. Towards imitation learning to branch for MIP: A hybrid reinforcement leamn ing based sample augmentation approach. In The Twelfth International Conference on Learning net Cicrum?ic-NNdoque
Representations, 2024. URL CRRLhttps:://// https::/openrevieee
Arman Zharmagambetov, Brandon Amos, Aaron Ferber, Taoan Huang, Bistra Dilkina, and Yuandong Tian. Landscape surrogate: Learning decision losses for mathemat- ical optimization under partial information. In A. Oh, Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.). Advances in Neural Information Pro- cessing Systems, volume 36. pp. -7330. Curran Associates, Inc., 2023. URL
wttptiipppcccpppppeeeeeee wwpprpppppppppe.ppppppeeeeepee.e http://ppppppeeeeepppaaaaeeeeaaa 372 pilees/papsr/22///111
17

---

Published as a conference paper at ICLR 2025
A
NOTATIONS
For a better understanding, we summarize and provide some key notations used in this paper in Table 4
Table 4: Notations used in paper.
Notations
Descriptions
I
A MILP instance.
æ
The decision variables in the MILP.
The 7th component of solution decision variable.
The predicted solution for the MILP.
á
The reference solution for the MILP.
x|P]
The partial solution the same variable values as in the index set P.
a Corr [P]
The corrected partial solution given the index set P.
( I)
The distribution of the optimal solution given MILP instance I.
(a I)
The predicted marginal probabilities for the solution, given instance I.
a(x I)
distribution of the reference solution given instance I and predicted solution á.
DKL(-1-)
The KL divergence two distributions.
H()(()
The entropy of a distribution.
d(..)
The cross-entropy of two distributions.
B
THE SKETCH OF DERIVATION OF THE VARIABLE FIXING STRATEGY
B. THE MOTIVATION OF ASSUMPTION I FROM CLASSICAL PROBLEM
In this part, We will provide some evidence to support Assumption from both an intuitive perspec- tive for better understanding.
Example 1. Consider two students, A and B. participating in math competition with multiple- choice question offering two options. Let the probability that student A answers correctly be and the probability for student be q. Since both have prepared for the exam, assume p, q >> 0.5. they provide the same answer, what is the probability that their answer is correct? Conversely, they provide different answers, what is the probability that student is correct?
Answer. by:
When both students provide the same answer, the probability that both are correct is given
P(A are correct A,B provide the same answers)
P(A,B are correct and provide the same answers)
Pq
(10)
PPA.B provide the same answers)
pq + (1 P1 9)
Given that their answers different, the probability that A is correct is
P(A is correct A,B provide different answers)
p(1 -9) P(A is correct, and A,B provide different answers)
(11)
P.A. provide different answers)
p(1 111-0 9) (111pp
simple calculation reveals that
PAA.B are correct A,B provide the same answers) PPA is correct A,B provide different answers), (12)
suggesting that both students provide the same answer, is more likely to correct.
Returning Assumption D draw analogy: the predicted solution and the reference lution correspond to the answers given by the two students, while the optimal solution represents the correct answer. For simplicity, treat these independent. As shown in the example, ifs
18

---

Published as a conference paper at ICLR 2025
P.q 0.5, then consistent answer yields higher precision than differing answers. Given that the predictor is well-trained, we believe that the precision will exceed 0.5. Similarly, the precision of the traditional solver is also expected to be greater than 0.5.
( = 2; = = = 1,
((2; = | i 0, = =, and
(13)
((:; 3;
q(:;
| 5; = 1,5; =0,)).
B.2 THE SKETCH OF DERIVATION
In this paper, we propose the UEBO metric to determine the variables to fix. In practice, we do not calculate UEBO directly. Instead, we propose to approximate UEBO in Section
First, we introduce a concept called prediction-coorrctionn consistency (Definition I in
Section 4.3)
d((p( I), II) q(2; 0 &; Log(1 po(a; = I]) I)) +g(x; = 1 i; log = 1 I)),
(14)
which is the negative of cross entropy loss using reference solutions 'labels'.
Second, also show that UEBO decreases the prediction-correctinn consistency increases (Theorem 2 in Section 4.3). Using this property, to compare the UEBO of two variables, we just need to compare their prediction-correciion consistency, with higher prediction-correction consistency indicating a lower UEBO. Here we provide a simple nu- merical example explain this process.
We suppose kn = 0. 1 an instance with five binary variables æ; (i .I...,,)) 5) is (0.9, 0.7, 0.6, 0.5). First, we add the following constraints to the instance.
Example 2.
3 and A = for simplicity. GNN prediction for
Φ S 01, 1 01 S a1:
32 S 022 - 32 02:
(15)
Σ3 S 0z, - E3 S 0g:
01 02 + 03 < 1.
Suppose that the reference solution is [i), 02 33, U4, ks} 1,, 1]. Thus, we have the prediction-correction consistency
d(pp((11 [Z) [1
i1, 1 log( + log(0.1) log(0.9),
d(po(<>2 ZZ. q 22
i2, I)) = 0 x log (0.8) + 1 x log(0.2) = log (0.2), (16)
d(po(ws, Z), q (;,, I)) 1 (0.7) + 0 x log(0.3) log(0.7).
Thus, the variables æ; and 2: have higher prediction-correction consistencies and thus confidence to fix æ; and 333
lower UEBO. We have
Third, we step further to simplify the fixing rule. Intuitively, a well-trained model should satisfy the property that if the predicted partial solution á;; 1, then po (æ; II) should be larger than 0.5: if the predicted partial solution é; = O, then pa I] should be smaller than 0.5. Using this observation, we find the inequality
-d(pe(æ; I). g(x, a. I)) 2 -d(po(x, IZ). [T,
(17)
always hold given 3., b * C. with x; .;.. To see this, assume that o; = 6. = 1,
we have po (x; [) > 0.5 and pe (
II) Z 0.5. Then, we have
- -d(po (a:; I), ((x
i; 1)) = log(po (z; [T) > log(0.5) 2 looglolpop (x [)) d(po 12), T).
(18)
Thus, we propose the fixing strategy in Equation (7). The proposed fixing strategy fixes variables satisfying a; á;, which are indeed the variables with high prediction- correction consistency and thus low UEBO.
Example 3. In Example 2 - क = 1, t2 # 82. db = a.3 = 1. Thus, we fix æ; and 23 value 1. This result coincides with that given Example
19

---

Published as a conference paper at ICLR 2025
C PROOF OF PROPOSITIONS AND THEOREMS.
C.I PROOF OF PROPOSITION
We show the results by direct calculations,
DRL. pa (x: Z)]la(<x [T) [.le
[po(z; []]
pa(ar; (o)
dæ,dI
g(<n; T)
= =f po(a; log(o))) I))
/ po(an; [Tp(I) log(1(ar; I))
-M(po(x: [I) [ po(x:; I)p(Z) log (/ q(xx; R; T)o(( I)dt; dx
S (2v [I)) | mi 20
pe( (p IJ) log(((2; 2e da
H(pe( (zv, []) + d(pe(xx; [I), &t,I)).
(19)
C.2 PROOF OF THEOREM 2
We analyze the monotony property of UEBO as follows. First, we suppose that the variable 2; takes value 1 in the reference solution, i.e., क; Thus, UEBO in the form of
UEBO(po I), ((t;;
I), g( IT) Pe Po ( I)) log pe ( [T] (1 ( IT) log(1 pe (á: Σ)) log po( I]
Z))
(á Z)) + d(po (.:
0:=1
(20)
(1 + pe ( I)) log Po ( I) - (1 - - [)) log (1 Pe ( Z)).
Differentiating UEBO with respect the predicted logit pa Σ), we have
dUEBO(Po ( I])
0.=1 log
II) 1)
S 0,
(21)
dp (#; I))
Pa ④
Pa (
I))
where po (á;; I) takes values between [0. 1]. Therefore, UEBO decreases as (o
I) becomes
larger in [0. 1]. As pa( Σ) grows, the cross-entropy term d(po 9 2, 2))
-log Po (;; Σ) decreases and the prediction-correction consistency becomes higher.
Similarly, the proof of case that the variable ã; takes value 0 in the reference solution follows the same step, and we thus show that UEBO has a negative correlation with the predection-coorrcctoon consistency.
C.3 PROOF OF THEOREM 3
We first expand the hight-hand side of the inequalities.
q = 1 à; = 1,Z) (xx =
= 1 é; = 1,T)
+ u( = -.
= =0 ã; = 1,2)
(22)
<x(2; = -,,
-- =
+ g(=; -,, - = = |
1,2),
where the inequality holds by the consistency conditions
Thus we have
<x=;- = =1 || ã;; 1,
<q(x; 11 i 1, = 1,I) (g(a: 1 a. 1,2) ( -0 3. 1,
(23)
= [xx" = 1
=00=11,77 1,Z).
20

---

Published as a conference paper at ICLR 2025
C.4 PROOF OF FEASIBILITY GUARANTEE
Since the trust-region searching problem 2is feasible, we can obtain a feasible solution as a reference solution, denoted by T. Thus, satisfies the constraint in Problem 2 i.e.,
Ač b, S ã S u, T[P] E Bp(a
dE R"
According to the consistency- baaseedeyy-beedd variable fixing strategy, we fix the variable x[P' in the instance I values ž (P"), where p' is a subset of P satisfying ā [ T[P'). Therefore, we have
AE - b, s u.
a|P'l = x [P'). I EE x XP
This implies that à is also feasible solution of Problem
6
D IMPLEMENTATION OF OUR METHODS AND THE BASELINES
Machine learning has made great progress in a broad range of areas Mao al., 2025a Dong et al., 2025 Bai et al., 2025: Wang et al.] 2025: 2024d cle 2023c| 2022 Yang et al. 2022 Liu
al. 2023b; Wang et al.J [0233a] Yang et al. 2024) and graph neural networks have shown great performance in solving MiLPs. The PS models used in this paper align with those outlined in the original papers] Han et al. (2023). We use the code in https: / github. com/ sr sribden//
P Predict-and Search MILP method to implement PS. For the PS predictor,
leverage
graph neural network (Kipf & Welling 2017 Shi et al. 2023 Sui et al. 2024; Mao et al.] [024]
Shi et al. 2025| 2024) comprising four half-convolution layers. The codes of the original work of ND (Nair et al. 2020) and ConPS (Huang et al., 2024) are not publicly available. We try our
best to reproduce these baselines and tune the hyperparameters for testing. We conducted all the experiments on single machine with NVidia GeForce GTX 3090 GPUs and Intel(R) Xeon(R) ES-2667 V4CPUs 3.20GHz.
In the training process of the predictors, we set the initial learning rate to be 0.001 and the training epoch be 10,000 with early stopping. To collect the training data, we run a single thread Gurobi on each training and validation instance to for 3,600 seconds and record the best 50 solutions.
The partial solution size parameter (ko, k1) and neighborhood parameter A are two important pa- rameters in PS. The partial solution size parameter (Kg. K1, A) represents the numbers of variables fixed with values 0 and 1 in partial solution. The neighborhood parameter A defines the radius of the searching neighborhood. We list these two parameters used in our experiments in Table 5
Table 5: The partial solution size parameter (ko, k1) and neighborhood parameter A.
Benchmark
CA
SC
IP
WA
PS+Gurobi
(600,0,1)
(2000,0,100)
(400.5,10)
(0.500,10)
ConPS+Gurobi
(900,0,50)
(1000,0,200)
(400,5.3)
(0,500,10)
PS+SCIP
(400,0,10) (2000.0,100)
(400,5.1)
(0,600,5)
ConPS+SCIP
(900,0,50)
(1000,0,200)
(400,5,3)
(0,400,50)
For our Apollo-MILP, the training process follows a similar approach, but we incorporate data aug- mentation to align with the testing distributions, For each original training instance with n variables, we select the best solution x² from the solution pool S. Then, we randomly sample fixing ratio E [0.3, 0.7] and an index set P., of variables, where the index set contains an elements. Finally, we enforce the variables in the set V. to the corresponding values in x", resulting in æ [P.] = x [Pa). By varying the ratio we generate five reduced augmented instances from each training instance.
E DETAILS ON BIPARTITE GRAPH REPRESENTATIONS
The bipartite instance graph representation utilized in this paper closely aligns with that presented in the PS paper Han et al. (2023). We list the graph features in Table
21

---

Published as a conference paper at ICLR 2025
Table 6: The variable features, constraint features, and edge features used for the predictor.
Index
Variable Feature Name
Description
Objective Variable coefficient Variable degree
Normalized objective coefficient
1
Average variable coefficient in all constraints
Degree of the variable node in the bipartite graph representation
3
Maximum variable coefficient
Maximum variable coefficient in all constraints Minimum variable coefficient in all constraints Whether the variable is an integer variable or not) Binary encoding of the order of appearance for each variable among all variables.
4
Minimum variable coefficient
5
Variable type
6-17
Position embedding
Index
Constraint Feature Name
Description
0
Constraint coefficient
Average of all coefficients in the constraint
Constraint degree
Degree of constraint nodes
2
Bias Sense
Normalized right-hand-side of the constraint
The sense the constraint
Index
Constraint Feature Name
Description
Coefficient
Constraint coefficient
F DETAILS ON THE BENCHMARKS
F.1 BENCHMARKS IN MAIN EVALUATION
The CA and SC benchmark instances are generated following the process described in Gasse et al. 2019). Specifically, the CA instances were generated using the algorithm from Leyton-Bree BrooonBrowwnn
2000 and the SC instances were generated using the algorithm presented in Balas & Ho 1980).
The IP and WA instances are obtained from the NeurIPS ML4CO 2021 competition (Gasse al. The statistical information for all the instances is provided in Table
2022
Table 7: Statistical information of the benchmarks used in this paper.
CA
SC
IP
WA
Constraint Number
2593
3000
195
64306
Variable Number
1500
5000
1083
61000
Number of Binary Variables
1500
5000
1050
1000
Number of Continuous Variables
0
33
60000
Number of Integer Variables
0
0
0
F.2 BENCHMARKS IN USED FOR GENERALIZATION
We generate larger CA and SC instances to evaluate the generalization ability of the approaches. We use the code in Gasse al. (2019) for data generation. Specifically, the generated CA instances have an average of 2,596 constraints and 4,000 variables, and the SC instances have 6,000 constraints and 10,000 variables. These instances considerably larger than the training instances.
F.3 SUBSET MIPLIB
We construct subset of MIPLIB (Gleixner et al. 2021 to evaluate the solvers' ability to handle challenging real-world instances. Specifically, we select instances based on their similarity, which is measured by 100 human human-designed features (Gleixner et al. 2021). Instances with presolving times exceeding 300 seconds or those that exceed GPU memory limits during the inference process are discarded. Inspired by the IIS dataset used in Wang al. (2024a), develop refined IIS dataset
22

---

Published as a conference paper at ICLR 2025
containing eleven instances. We divide this dataset into training and testing sets, comprising eight training instances and three testing instances (ramos3, sepj4scip, and scpl4). Detailed information on the IIS dataset can be found in Table g
Table Statistical information of the instances the constructed IIS dataset.
Instance Name
Constraint Number
Variable Number
Nonzero Coefficient Number
ex ex1010-pi
1468
25200
102114
fast0507
507
63009
409349
glass-sc
6119
214
63918
iis-glass-cov
5375
214
56133
iis-hc-cov
9727
297
142971
ramos3
2187
2187
32805
scpj4scip
1000
99947
999893
scpk4
2000
100000
1000000
scpl4
2000
200000
2000000
seymour
4944
1372
33549
v150dd0--hopeds
7822
150
103991
F.4
MORE BENCHMARKS
To demonstrate the effectiveness of our method, we include three more benchmarks. The statistical information is in Table g
SCUC dataset This dataset comes from the Energy Electronics Industry Innovation Competition. The benchmark contains large-scale instances from real-world power systems.
Smaller-size CA dataset This dataset is the CA dataset with the same sizes as the 'Hard CA' in Gasse et al. (2019). This dataset has a lower instance size and computational hardness than the CA dataset used in our paper. All the methods can solve the problems within the time limit, and we thus report the solving time.
APS dataset This dataset is from anonymous commercial enterprise containing real-world pro- duction scheduling problems in the factory. The instances in APS are general integer programming problems, containing binary, continuous, and general integer variables.
Table 9: Statistical information of the benchmarks.
SCUC
Small-size CA
APS
Constraint Number
27835
576
31296
Variable Number
19807
1500
31344
Number of Binary Variables
9295
1500
1500
Number of Continuous Variables
10512
0
15984
Number of Integer Variables
0
9600
G HYPERPARAMETERS
We report the hyperparameters (Ag (0) ()) of Apollo-MILP used Table
23

---

Published as a conference paper at ICLR 2025
Table 10: Hyperparameters (R.g) A (6) for Apollo-MILP.
CA
SC
IP
WA
Iteration I
(400,0,60)
(1000,0,200)
(100,20,50)
(20,200,100)
Iteration 2
(200,0,30)
(500,0.100)
(40,15.20)
(10,100,50)
Iteration 3
(100,0,15)
(250,0,50)
(20,15.10)
(10,5,5)
Iteration 4
(50,0,10)
(10,0,5)
(5,50,30)
(1,10,5)
H ADDITIONAL EXPERIMENT RESULTS
H.1 REAL-WORLD DATASET
To further demonstrate the applicability of Apollo-MILP, we conduct experiments on instances from MIPLIB (Gleixner et al. 2021). challenging real-world dataset. Due to the heterogeneous nature of the instances in MIPLIB, applying ML-based solvers directly to the entire dataset can be difficult. However, we can focus on subset of MIPLIB that contains similar instances (Wang et al. 2023b 2024a). For more information on the selected MILP subset, referred as IIS, please see Appendix F33 This subset consists of eleven challenging real-world instances. Notice that we need to care- fully tune the hyperparameters (kg, k1, A) for the ML baselines, as improper hyperparameters can easily lead to infeasibility. While Appolo-MILP exhibits strong adaptation across different hy- perparameters. We report the solving performance of the solvers in Table [1| where Apollo-MIIl significantly outperforms other baselines, showcasing its promising potential for real-world applica- tions. We also report the detailed results of the real-world challenging MIPLIB dataset mentioned. We set the time limit 3,600 seconds and two iterations with 1,000 and 2,600 seconds. Given the variation in instance sizes within the dataset, we set A 1000 and the proportion of fixed vari- ables (ao. a1) (0.8, 0), which means that fix 0.8 of the binary variables to 0 in the first round.
Table 11: The results in the IIS dataset, which is used in Wang al. (2024a) and is a subset of MIPLIB. We build the ML approaches on Gurobi and set the solving time limit to 3,600s.
Obj
gapabs
Gurobi
214.00
23.00
ND
213.00
22,00
PS
211.00
20.00
ConPS
211.00
20.00
Ours
209.33
18.33
Table 12: The best objectives found by the approaches on each test instance in IIS. BKS represents the best objectives from the website of MIPLIB https: //tpppib.p.i/pm//m//m../... z ib. de wtt///ndexx../ html
BKS
Gurobi
ND
PS
ConPS
Ours
ramos3
186.00
233.00
233.00
225.00
225.00
224.00
sepj4scip
128.00
132.00
131.00
133.00
133.00
131,00
scpl4
259.00
277.00
275.00
275.00
275.00
273.00
H.2 HYPERPARAMETE ANALYSIS
We investigate the impact of hyperparameters in our proposed framework. In this part, we conduct extensive experiments to analyze the impact of hyperparameters, including the partial solution size, neighborhood parameter, iteration time, iteration round number, and the use data augmentation. For all experiments, we implement the method using Gurobi and set time limit of 1,000 seconds.
We examine the effects of the partial solution size parameter kns in the CA benchmark. As noted in Huang et al. 2024). fixing x
Partial Solution Size Parameters
always yields better
24

---

Published as a conference paper at ICLR 2025
solutions. Therefore, we focus on the effects of ko while keeping k 0 and A (60, 30, 15, 0) for four rounds of iterations. Our findings, presented in Table 13 indicate that a fixing coverage of 50% of variables yields the best performance. This optimal coverage balances the risk of the solution prediction methods becoming trapped in low-quality neighborhoods common with high coverage of fixed variables while avoiding ineffective problem reduction associated with low coverage.
Table 13: The solving performance with different partial solution size parameters kax the CA benchmark, under the time limit 1,000 seconds. The coverage rate implies the approximate proportion of fixing variables.
Obj f
gapabs +
Coverage 85%
96950.55
666.04
Coverage 70%
96929.98
686.61
Coverage 50%
97487.18
129.41
Coverage 30%
97359.09
257.50
Neighborhood Parameter We examine how the choice of neighborhood parameters affects solv- that when A is small, increasing its value enhance performance since searching within a larger area may yield higher-quality solutions. However, when A is too large, performance decreases, the expanded trust region results in larger search space, leading to inefficiencies in the search process.
ing performance. From [4]
Table 14: The effects of neighborhood parameters on the solving performance.
Obj f
gapabs
60% of Fixing Numbers
97297.52
319.07
50% Fixing Numbers
97343.47
273.12
20% of Fixing Numbers
97487.18
129.41
10% of Fixing Numbers
97019.17
597.12
Iteration Time We investigate the relationship between iteration time and performance in Table setting time limit of 1,000 seconds. The early iterations focus identifying high-quality feasible solution to reduce the search space, while the final iteration aims to exploit the optimal solution within this reduced space. Through four iterations, we find that the last iteration, allocated 600 seconds, yields the best performance. As the exploitation time increases, the algorithm is more likely to search the reduced space thoroughly. However, extending the exploitation time reduces the available time to enhance the predicted solution during the early stages, which can lead to decline the quality of the predicted solutions.
15
Table 15: The effects of iteration time on the solving performance.
Ohj f
gaPab
(25.25,50,900)
96741. 004
875.55
(50,50, 100,800)
96889.70 770
726.89
(100,100. 100,00000000)
97487.18
129.41
(5.0,1503300,400)
97353.35
263.24
The Rounds of Iterations We conduct experiments on the rounds of iterations. We fix the solving time limit to 1.000s and compare different rounds of iterations the CA dataset. Given an iteration round, we set the same search time across the iterations. The results are presented in Table T6] which indicates the four rounds of iterations have the best performance.
Data Augmentation The distribution of the reduced problems in each iteration may differ from that the original problems. As pointed out Section 4.1 we employ data augmentation to align the distributional shifts. We conduct experiments to evaluate the effect of data augmentation in
25

---

Published as a conference paper at ICLR 2025
Table 16: The effects of rounds of the iterations on solving performance.
Obj f
gapabs
(500,500)
97132.39
484.20
(333.3,333.3.333
97349.74
266.85
(250,250,25,,255)))
97388.21
228.38
96889.70
726.89
We the CA dataset and the solving time limit 1,000s. The results show that data augmentation can improve the performance.
Table 17
Table 17: The effects of data augmentation on solving performance.
Obj f
gapabs +
w/o data augmentation
97393.65
222.9c 24
Ours
97487.18
129.41
H.3 COMPARISON WITH MORE BASELINES
Comparison with Different Fixing Strategies We provide more results when comparing differ- ent fixing strategies more benchmarks. We set the search time in each iteration to be consistent across these methods. Direct Fixing relies totally on the GNN predictor for variable fixing, and Multi-stage PS relies the reference solution provided by the traditional solver. Different from these two baselines, our proposed method introduces the correction mechanism and combines the predicted and reference solutions, determining the most confident variables to fix. The results correction method
presented in Table I8 The results in Table 18 show that our proposed outperforms the other baselines.
Table 18: Comparison of solving performance between approach and different fixing strategies, under a 1, 000s time limit. We report the average best objective values and absolute primal gap.
CA (BKS 97616.99
SC (BKS 122.95)
IP (BKS 8.90)
(BKS 704.8)
Obj
gap
Obj 4.
gap
Obj 4
gap
Obj 4
gaPats
Gurobi PS+Gurobi
97297.52
319.07
123.40
0.45
9.38
0.48
705.49
0.61
97358.23
258.36
123.30
0.34
9.17
0.27
705.45
0.57
Direct Gurooi
96939.19
677.4
123.30
0.35
9.22
0.32
705.40
0.52
Multi-stage PS+Gurobi
97016.47
600.12
123.20
0.25
9.18
0.28
705.33
0.45
Ours+Gurobi
97487.18
129.41
123.05
0.10
8.90
0.00
704.88
0.00
Comparison with a Warm-starting Gurobi starting methods benchmarks. The results are presented in Table 19 in which we set the solving time limit as 1,000s.
We provide more results when comparing the warm-
H.4 EVALUATION ON MORE BENCHMARKS
We evaluate our method in more benchmarks, including the small-scale CA dataset, the large-scale and real-world dataset SCUC, and real-world general integer programming problems APS. We re- port the experiment results in Table 20 The experiment results demonstrate the strong performance of our proposed method across various benchmarks. Notice that our method still outperforms the baselines in the general integer programming problems (APS) in Table 20
26

---

Published as a conference paper at ICLR 2025
Table 19: Comparison of solving performance between our approach and the warm-starting meth- ods, under 1, 000s time limit. We report the average best objective values and absolute primal gap-
CA (BKS 97616.59)
SC (BKS 122.95)
IP (BKS 8.90)
WA (BKS 704.88)
Obj f
gapabs +
Obj +
gapabs
Obj 4
gapahe
Obj
gapats
Gurobi
97297.52 .52
319.07
123,40
0.45
9.38
0.48
705.49
0.61
PS+Gurobi
97358.23
258.36
123.30
0.35
9.17
0.27
705.45
0.57
WS-PS+Gurohi
97016.34
600.25
123.30
0.35
9.20
0.30
705.45
0.57
WS- WS-Ours+Gurobi
97359.19
257.40
123.20
0.25
9.13
0.23
705.40
0.52
Ours+Guurbi
97487.18
129.41
123.05
0.10
8.90
0.00
704.88
0.00
Table 20: Comparison solving performance on more benchmarks, under a 1, 0,0s time limit. We report the average best objective values and absolute primal gap.
SCUC (BKS 1254399.66)
Smaller- Size CA
APS (BKS 558917.52)
Obj
gapabs +
Time
gapabs
Obj +
gapabs
Gurobi
1269353.86
14954.20
105.61
0.00
666583.20
107665.c6 688
ND+Gurobi
1266355.77
11956.11
102.34
0.00
646908.07
87990.55
PS+Gurobi
1265332.21
10932.55
104.68
0.00
635087.43
76169.91
ConPS+Gurobi
1264173.98
9774.32
98.63
0.00
626713.56
67796.04
Ours+Gurobi
1261684.89
7285.23
94.04
0.00
603443.23
44525.71
H.5 GENERALIZATION
We evaluate the generalization performance of our method. Specifically, we generate larger in- stances of the CA and SC problems (please refer to Appendix F.2 for more details). We utilize the model trained on the instances described in Section 5.1 [.1 and evaluate the models these larger in- stances. The experiment results in Table 21 demonstrate the strong generalization ability of Apollo- MILP, as it outperforms other baselines these larger instances.
Table 21:
We evaluate the generalization performance 100 larger instances. The ML approaches are implemented using Gurobi, with a time limit set to 1,000s. 'xa indicates that higher is better, and ' indicates that lower is better. We mark the best values in bold.
CA (BKS (15746.88)
SC (AKS 101
Obj f
gapabs
Obj
gapabs
Gurobi
114960.25
786.63
102.29
0.84
ND+Gurobi
115035.44
711.44
102.51
1.06
PS+Gurobi
115228.20
518.68
102.27
0.82
ConPS+Gurobi
115343.23
403.65
102.18
0.73
Ours+Gurobi
115413.86
333.02
102.16
0.71
27

---

Published as a conference paper at ICLR 2025
I REPRODUCTION OF THE BASELINES
Since ND and ConPS are not open-source, we must reproduce the results from the original papers to validate models. In this section, we reproduce the experiments conducted in the original studies (Nair et al. 2020) and (Huang et al. 2024) to ensure the performance of our reproduced models.
Following the validation approach and settings outlined in Nair al. (2020) and Han et (2023) we conduct experiments on the Neural Network Verification (NNV) dataset. We implemented the Neural Diving method within SCIP and compared its performance against the default SCIP. As noted by Han et al. (2023), tuning the presolve option in SCIP can lead to false assertions of feasibility in the NNV dataset; therefore, we disabled this option for both SCIP and our reproduced ND+SCIP. The results are presented in Figure 4 where ND significantly outperforms SCIP, confirming the performance of our reproduced model.
To reproduce ConPS, we utilized the IP dataset built SCIP and replicated the experiments de- scribed the original paper (Huang al.) 2024). The results are summarized Figure where performance of ConPS aligns with the results in the original study (Huang et al. 2024
NNV
SCIP
Average Primal Gap
ND+SCIP
0.10
0.01
10a
10a
10a
Time
Figure 4: The reproduced results of SCIP and ND+SCIP the NNV dataset.
IP
10"
SCIP
Average Primal Gap
PS+SCIP
ConPS+SCIP
10-1
500
1000
Time (s)
Figure 5: The reproduced results of SCIP and ConPS+SCIP on the IP dataset.
28


Reviews:
[{"review_id": "ngRNUNNch6", "reviewer": "Reviewer_Gah2", "summary": "In the context of deep learning for solving mixed-integer linear programs (MILPs), this paper proposes enhancements to an existing predict-and-search framework. \n\nTraining differs from existing work in that the supervised learning dataset includes not only near-optimal solutions to training MILP instances, but also to sub-instances (restrictions) in which some variables are fixed and only other variables are optimized. A GNN is trained to maximize an energy potential function that assigns higher probabilities to variable value-assignments that have a better objective function value. \n\nMost proposed changes are at inference time. First, the approach is iterative. In every iteration, a subset of variables have been fixed based on preceding iterations. Then, the GNN makes a prediction on the remaining variables. A trust-region search is performed around said solution using a MILP solver for a limited amount of time. The GNN prediction and the trust-region solution are compared using an upper bound on GNN prediction uncertainty. Based on this bound, some of the GNN’s variable assignments are ignored if too uncertain. The newly fixed variables are appended to those from the previous iteration and the next iteration of this prediction-correction loop is performed until a set number of iterations is met.\n\nExperiments on four MILP benchmarks from the literature show that the proposed framework produces better solutions on average than Gurobi and three comparable ML methods from the literature. Ablations and hyperparameter searches are performed to justify certain elements of the proposed method and tune its performance to a validation set.", "questions": "Kindly refer to the weaknesses. I can be convinced to increase the rating if convincing answers are provided.\n\nMinor comments:\n- line 256: the notation for equality of two variable assignments along index set P can be confusing. It is better to say x_P[P] = x[P]. Set membership with $\\in$ has a very specific meaning that is not met by your definition.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The incorporation of uncertainty quantification is new and interesting in this setting. Although I have clarification questions on this (see Weaknesses), the overall approach seems sensible and effective in practice. Some theoretical results justifying the proposed uncertainty bound, UEBO, are also presented.\n\nS2. The experiments span multiple competing methods, four very reasonable MILP benchmarks, a subset of the MIPLIB2017 collection, ablations, and hyperparameter analysis. Although I have questions on other aspects of the results in the paper, I appreciate the care taken in designing the experiments.", "weaknesses": "W1. Table 8 says that the CA instances have 1500 variables and ~2500 constraints. The “Hard” instances of CA from Gasse et al. Have 1500 bids, which I believe corresponds to 1500 decision variables. However, their Table 2 “Hard” column for CA shows that SCIP with RPB branching (the default in SCIP) has an average running time of 136.17 seconds, meaning all or most instances are solved to global optimality in 2.5 minutes on average. In contrast, your Table 1 for CA shows that Gurobi typically terminates with a suboptimal solution in 1000 seconds. This is extremely puzzling to me as Gurobi is faster than SCIP and you are likely using better CPUs than used in Gasse et al. Could you clarify whether your CA instances in Table 1 correspond indeed to the “Hard CA” instances of Gasse et al.? Could you explain the performance discrepancy? These instances seem to be super easy to solve to optimality; why does this not apply in your experiments?\n\nW2. Please clarify how you calculate the UEBO, particularly the second term. I have struggled to interpret the conditional version of the q(.) distribution that seems so crucial to this bound. Perhaps a small numerical example is in order for this rebuttal and updated versions of this paper.\n\nW3. Solvers such as Gurobi can be used to emphasize finding good solutions quickly. In particular, MIPFocus=1 (https://www.gurobi.com/documentation/current/refman/mipfocus.html). Do you use this for the “Gurobi” row of your results Table 1? If not, then you should as it is unfair to compare to default Gurobi on primal gap when it is running to balance between proving optimality and finding solutions. It should focus on the latter.\n\nW4. Warm-starting Gurobi as baseline: What if you passed the initial GNN prediction (fixing the k0 and k1 variables to 0 and 1 and letter other variables free) to Gurobi as a MIPStart (https://support.gurobi.com/hc/en-us/articles/360043834831-How-do-I-use-MIP-starts)? Gurobi can search around this warm-start and various ways and it has parameters that let you control this process. I believe this baseline is crucial to understanding the benefits of your and other similar methods. The methods you compare to may have missed this, but that does not justify you not performing this experiment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "nd6czC0bhT", "reviewer": "Reviewer_NfYM", "summary": "This paper proposes a framework, Apollo-MILP, to obtain solutions for MILPs. The framework combines a prediction phase with a correction phase in an iterative manner. In each iteration, the predictor estimates values for unfixed variables, followed by a correction step that refines the partial solution. The correction step is analysed with a newly introduced uncertainty-based error upper bound to evaluate the reliability of predictors, which helps determine which variables to confidently fix. This alternating framework allows the system to reduce problem size iteratively while preserving solution quality and feasibility.Benchmarking results show that Apollo-MILP outperforms both ML-based and traditional solvers, achieving better objective values and closer gaps to the best-known solutions.", "questions": "1. The proposed alternating problem-solving and variable-fixing strategy resembles large neighborhood search (LNS). In each iteration, the ML model predicts a \"confidence\" level for fixing a variable to either 0 or 1, and the top k0+k1 variables are fixed to construct the reduced problem in Equation (2). A MILP solver then solves this reduced problem to obtain a “reference solution.” Before the next iteration, variables with shared values between the “predicted solution” and “reference solution” are fixed. The ML model effectively selects the neighborhood for LNS. Could you please clarify the distinctions between the proposed framework and ML-based LNS methods in the literature?\n\n2. Could you please comment on the rationale for some design choices of the implementation? For instance, \nwhy is the algorithm divided into four iterations with 100, 100, 200, and 600 seconds respectively? What are the other alternatives that have been experimented? \n\n3. In Appendix F, hyperparameters are given for the framework. What is the search space for hyperparameters?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper introduces a new Uncertainty-based Error upper Bound (UEBO) metric and provides a detailed theoretical analysis of the proposed framework. \n\n2. The paper demonstrates Apollo-MILP's effectiveness across various benchmark datasets, showing improvements in solution quality and convergence speed compared to both traditional and ML-based solvers.", "weaknesses": "1. The presentation of the paper can be improved with better introduction of the background and basic concepts. For instance, Proposition 1 uses the concepts of entropy and KL divergence, which should be defined in the context of solution prediction for MILPs. \n\n2. The general framework would be clearer if Algorithm 1 from Appendix B were incorporated into the main text alongside the description in Section 4. Moving the algorithm into the main content could improve readability and help readers follow the approach more easily.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Vzk8XZk3fC", "reviewer": "Reviewer_PGi6", "summary": "This paper introduces Apollo-MILP, a novel iterative framework for MILP that combines prediction and correction. The core idea involves alternating between prediction and correction steps to reduce search space and improve the solution: A bipartite GNN predicts a solution, and a better solution is further searched in the trust region. Another contribution is UEBO, a theoretical sound upper bound, which evaluates the reliability of the current solution and guides variable fixing to reduce problem size after correction. The framework demonstrates superior performance over traditional solvers (Gurobi & SCIP) and other learning methods on various benchmark datasets, achieving comparable or better solutions within a shorter time frame.", "questions": "1. Could the authors provide further details on the characteristics of the problem instances used in the experiments? Specifically, information on decision variables, such as the number of continuous variables, integer variables, and binary variables, would be valuable. \n2. The authors claim that Apollo-MILP suits general integer programming (IP) problems. I wonder now if there are any experimental results on general IP problems, not just 0-1 variables.\n3. The current approach appears to fix one variable with the lowest UEBO in each iteration. Has the team considered fixing multiple variables with low UEBO values simultaneously? Testing this multi-variable fixing strategy could potentially enhance the convergence rate by accelerating problem reduction.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. **Novelty:** Apollo-MILP introduces a novel approach to MILP by combining gin-based prediction with an iterative correction process. This reduces problem dimensionality and maintains solution quality through each iteration. The Uncertainty-based Error Upper Bound (UEBO) is also a good contribution, measuring prediction reliability to guide variable fixing.\n2. **Effectiveness:** The experimental setup and result quality are good, with well-chosen benchmarks and comparisons to MILP solvers and other SOTA baselines. The experiments clearly demonstrate its advantages in speed and accuracy.\n3. **Clarity:** The paper is well-written and well-structured, and its explanations are generally clear, with enough detail provided for the algorithm, theoretical foundations, and experimental setup.", "weaknesses": "1. **Time-Consuming Data Collection:** For my understanding, a key limitation is the time-consuming nature of data collection. Since the model requires optimal or near-optimal solutions as labels during training, it depends on solving many problem instances, which can be computationally expensive for large problems. \n2. **Limited Benchmark Problems:** The number of benchmarks is 4, which, while indicative, may limit the generalizability of the results. Although it is understandable that solving large-scale MILPs can be time-consuming, expanding the experimental scope to include more problems, even some smaller-scale instances, would provide a more comprehensive view.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Nt0GsP57VN", "reviewer": "Reviewer_CDjs", "summary": "The authors propose a Prediction-Correction Mixed-Integer Linear Programming (MILP) solving framework, referred to as Apollo-MILP, aimed at addressing MILP problems. In each iteration, Apollo-MILP first predicts a partial solution that will be fixed and subsequently improves this solution using a trust region method. Under a set of strong assumptions, theoretical results indicate that Apollo-MILP ensures improved solution quality and feasibility. Furthermore, experimental evaluations **seem to** demonstrate that the proposed framework outperforms the state-of-the-art methods across several datasets. **Generally speaking, I think this paper is a trivial extension of the work [3], and I personally do not see significant contributions**.", "questions": "See the weakness part.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "I think the proposed Apollo-MILP framework is new, and the iterative predict-based fixing strategy is well designed for MILPs. Moreover, the perspective of de-coulping  the fixing strategy into two steps--prediction and correction--is interesting.", "weaknesses": "I have a few concerns below.\n\n- Generally, this paper presents some theorems under several very strong assumptions. I do not think this paper has theoretical contribution, it is more about presenting an empirical algorithm. For example, in Theorem 4, \"If the trust-region searching problem 2 is feasible....\", the theorem is clearly valid if this assumption is true. I do not think this is worth a theorem. \n\n- Assumption 1 is kind of too strong and counter-intuitive, can you provide some experiments for validation? \n\n- To compare the proposed method against ND [1] and ConsPS [2], I believe it is essential to reproduce some of the experiments presented in their original papers to ensure that ND and ConsPS  are indeed comparable. \n\n- In Table 6, we notice that the parameters $k_0$, $k_1$, and $\\Delta $ differ significantly from those used in PS's paper [3]. Why did you choose not to use the original parameters? Parameters can directly influence the performance of both the PS and the fixing strategy. For a fair comparison, we recommend the authors employ the optimal parameters for your baseline methods.\n\n- To clearly demonstrate the performance of Apollo-MILP, I suggest including at least two experiments in your ablation study. \n  * Case i: Apollo-MILP v.s. 4 rounds of Direct Fixing;\n  * Case ii: Apollo-MILP v.s. 4 rounds of PS; \n  \n   All these methods utilize the same parameters $k_0^{(i)}, k_1^{(i)}$ and $\\Delta^{(i)}$, except in the case of Direct Fixing, where $\\Delta$ is not present. In each iteration, the solving times are consistent across these methods. By conducting these two experiments, you can effectively demonstrate that the performance improvements result from Apollo-MILP's multi-stage correction rather than from direct multi-stage solving (e.g., 4 rounds of PS and 4 rounds of Direct Fixing). Additionally, this approach will highlight the effectiveness of combining prediction and correction within your framework.\n\nMinor Issues:\n\n- typo: page 6, paragraph 2. “Instead, UEBO offers a practical estimation by utilizing the available distributions $p_θ(x_i | I)$, $q(x | \\hat x_i, I)$”,  $q(x | \\hat x_i, I)$ is missing an $i$.\n\n- The WA's figure is missing in Fig.3\n\n[1] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. *arXiv preprint arXiv:2012.13349*, 2020.\n\n[2] Taoan Huang, Aaron M Ferber, Arman Zharmagambetov, Yuandong Tian, and Bistra Dilkina. Con- trastive predict-and-search for mixed integer linear programs. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), *Proceedings of the 41st International Conference on Machine Learning*, volume 235 of *Proceedings of Machine Learning Research*, pp. 19757–19771. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr.press/v235/huang24f.html.\n\n[3] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xi- aodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear programming. In *The Eleventh International Conference on Learning Representations*, 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)