A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming
Authors: Qingyu Han
Linxin Yang
Qian Chen
Xiang Zhou
Dong Zhang
Akang Wang
Ruoyu Sun
Xiaodong Luo
Venue: ICLR 2023 poster (2023)

Abstract: Mixed-integer linear programming (MILP) is widely employed for modeling combinatorial optimization problems. In practice, similar MILP instances with only coefficient variations are routinely solved, and machine learning (ML) algorithms are capable of capturing common patterns across these MILP instances. In this work, we combine ML with optimization and propose a novel predict-and-search framework for efficiently identifying high-quality feasible solutions. Specifically, we first utilize graph neural networks to predict the marginal probability of each variable, and then search for the best feasible solution within a properly defined ball around the predicted solution. We conduct extensive experiments on public datasets, and computational results demonstrate that our proposed framework achieves 51.1% and 9.9% performance improvements to MILP solvers SCIP and Gurobi on primal gaps, respectively.

Published as a conference paper at ICLR 2023
A GNN-GUIDED PREDICT-AND-SEARGE FRAME- WORK FOR MIXED-INTEGER LINEAR PROGRAMMING
Qingyu Han 1:21, Linxin Yang 1.3 Qian Chen 14, Xiang Zhou', Dong Zhang", Akang Wang",
Ruoyu Sun".3", 9.34 Xiaodong Luo
1.3
Shenzhen Research Institute of Big Data, China
Shandong University, China
3 School of Data Science, The Chinese University of Hong Kong, Shenzhen, China
4 School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen, China
5 Huawei, China
6 Shenzhen International Center For Industrial and Applied Mathematics, Shenzhen Research Institute of Big Data, China
ABSTRACT
Mixed-integer linear programming (MILP) widely employed for modeling com- binatorial optimization problems. In practice, similar MILP instances with only coefficient variations are routinely solved, and machine learning (ML) algorithms are capable of capturing common patterns across these MILP instances. In this work, we combine MI. with optimization and propose a novel predict-and-search framework for efficiently identifying high-quality feasible solutions. Specifically, we first utilize graph neural networks to predict the marginal probability of each variable, and then search for the best feasible solution within properly defined ball around the predicted solution. We conduct extensive experiments on pub- lic datasets, and computational results demonstrate that our proposed framework achieves 51.1% and 9.9% performance improvements to MILP solvers SCIP and Gurobi on primal gaps, respectively.
INTRODUCTION
Mixed-intege linear programminn is one of the most widely used techniques for modeling com- binatorial optimization problems, such as production planning (Pochet & Wolsey| 2006) Chen 2010), resource allocation (Liu & Fan 2018 Watson & Woodruff] (011), and transportation man- agement ( Luathep et al. 2011 1 ScCööell 2001). In real-world settings, MILP models from the same application share similar patterns and characteristics. and such models are repeatedly solved without making uses of those similarities. ML algorithms are well-known for its capability of recognizing patterns (Khalil et al., 2022). and hence they are helpful for building optimization algorithms. Re- cent works have shown the great potential of utilizing learning techniques to address MILP prob- lems. The work of (Bengio et al. (02T)) categorized ML efforts for optimization as (i) end-to-end learning (Vinyals et al. 2015 5 Bello* et al. 2017: Khalil et al.) 2022). (ii) learning to configuring algorithms (Bischl et al. 2016 Kruber et al., 2017 Gasse et al. 2022) and (iii) learning alongside optimization (Gasse et al. 2019 Khalil et al. [206:; Gupta et al. 2020). In this work, for the sake
of interest, we focus on the end-to-end approach. While such an approach learns to quickly identify high-quality solutions, it generally faces the following challenges:
(I) high sample collection cost. The supervised learning task for predicting solutions is to map from the instance-wise information to a high-dimensional vector. Such learning task becomes computationally expensive since it necessitates collecting a considerable amount of optimal solutions (see, e.g., Kabir et al. (2009)).
(II) feasibility. Most of the end-to-end approaches directly predict solutions MILP problems, ignoring feasibility requirements enforced by model constraints (c.g. Yoon 2022 Nair
*Equal first authorship *Corresponding authors

---

Published as a conference paper at ICLR 2023
et al. ).20 As result, the solutions provided by ML methods could potentially violate
constrains.
We propose a novel predict-and-seuree framework to address the aforementioned challenges. In principle, end-to-end approaches for MILP problems require the collection of abundant optimal so- lutions. However, collecting so many training samples is computationally prohibitive since obtain- ing optimal solutions is excessively time-consuming. We consider approximate the distribution by properly weighing high-quality solutions with their objective values. This reduces the cost of sample collections by avoiding gathering optimal solutions mentioned in challenge (I). Regard- ing challenge (II), we implement a trust region inspired algorithm that searches for near-optimal solutions within the intersection of the original feasible region and properly defined ball centered at prediction point. The overall framework is outlined in Figure The commonly used end-to-
Predict
Search
MILP problem
Marginal probabilties
Trust Region
Near optinal
min
ELP
Input
GNN
MLP
0.5
Colect
Round
c 22 gime
Cutpuz
Cuiput
Input
Figure 1: Our approach first predicts marginal probability of each variable utilizing graph neural network (GNN) with graph convolution and multi-layer perceptron modules, and then searches for near optimal solutions to the original MILP problem within well defined trust region.
end approaches usually fix variables directly based on information from the prediction step, such as in Nair et al. (2020) and Yoon (2022). However, such approaches could lead sub-optimal solu- tions or even infeasible sub-problems. Rather than forcing variables to be fixed, search module looks for high-quality solutions within a subset of the original feasible region, which allows better feasibility while maintaining optimality.
The distinct contributions of our work can be summarized as follows.
We propose a novel predict-and-seett search framework that first trains GNN to predict marginal probability of each variable and then constructs trust region to search for high- quality feasible solutions.
We demonstrate the ability of our proposed framework to provide equivalently good or better solutions than fixing-based end-to-end approaches.
We conduct comprehensive computational studies several public benchmark datasets and the computational results show that our proposed framework achieves 51.1% and 9.9% smaller primal gaps than state-of-the-att general-purpott optimization solvers SCIP and Gurobi, respectively.
We make our code publicly available at uthttps://gitti Search MILP method
and
PRELIMINARIES
Given a vector Rdth and an index / {1, 2, ..., ...,n. let vy | denote subvector that corresponds to the index set I.
2. MIXED-INTEGER LINEAR PROGRAMMING
MILP techniques are used to model combinatorial optimization problems, and an MILP instance be formulated min c where D {i 24 --= Ax < b, 15 x S u) denotes the sE
2

---

Published as a conference paper at ICLR 2023
feasible region. There n variables, with I, R" being their objective coefficients, lower and upper bounds, respectively. Without loss of generality, the first q variables are discrete. A E [Rmx denotes the coefficient matrix while b R" represents the fight-hand-side vector. For convenience, let = (A, b, c, 1, u, 4) denote an MILP instance. For the sake of interest, we consider each Furthermore, incorporating continuous variables into consideration will not invalidate our proposed methodology, hence in what follows we consider a pure binary integer programming problem.
discrete variable be binary, i.e. 2; {0. 1} for 1 I
2.2 NODE BIPARTITE GRAPH
Gasse al. (209 proposed bipartite graph representation for MILP problems. Specifically, let
G = (V, E) denote bipartite graph, where V = {rr. ... Uny Un+1, ... Un+m J denotes the set
of variable nodes and constraint nodes, and & represents the of edges that only connect
between nodes of different types. Variable nodes and constraint nodes are individually associated with the instance information e.g. degrees and coefficients. The adjacency matrix A is |V] [V] matrix that represents the connectivity of G, defined below:
0 C
T
A
where Ci. A1.
0
2.3 GRAPH NEURAL NETWORKS
Let N (w:) {uz E EV: Ars & 0} denote the set of neighbors of node We construct k-layer
GNN follows:
( 12 ((N6-D2 J(t) (oe))))
where function {( aggregates the feature information over the set of neighboring nodes and fune- tion (()) combines the nodes' hidden features from iteration (A: 1) with the aggregated neighbor- hood features, and ( denotes the hidden state of node U; in the (k- 1)th layer. Initially, A! the output of an embedding function g (-). Note that the bipartite graph associated with an MILP instance does include edges between variable nodes as well as constraint nodes.
2.4 TRUST REGION METHOD
The trust region method is designed for solving non-linear optimization problems follows:
min (z),
(1)
where H! C Rn denotes a set of feasible solutions. The main idea is to convert the originally dif- ficult optimization problem into series of simple local search problems. Specifically, it iteratively searches for trial steps within the neighborhood of the current iterate point Yuuan 2015). The trial step dy is obtained by solving the following trust region problem:
min
J& (d),
dEH.
s.t.
|ddlw, A
where Ju (d) is an approximation of the objective function I (arx + d). H& denotes shifted H J. of the set H. Ill,,,, is a norm of IR", and A denotes the radius of the trust region. After solving the w, problem in the tth iteration, I++1 is updated to 2& dg or 24 accordingly. Then, new ||-ll and A are selected along with a new approximation Fr+t (d).
PROPOSED FRAMEWORK
The supervised learning task in end-to-end approaches trains a model to map the instance- wise in- formation to high-dimensional vector. Ding al. (2000) first utilizes GNN to learn the values of
3

---

Published as a conference paper at ICLR 2023
"stable" variables that stay unchanged across collected solutions, and then searches for optimal lutions based on learned information. However, such a group of variables does not necessarily exist for many combinatorial optimization problems. Another approach is to learn solution distributions rather than directly learning solution mapping: Li et al. (2018) predicts a set of probability maps for variables, and then utilizes such maps conduct tree search for generating large number of candidate solutions. Their work designed ML-enhanced problem-specific tree search algorithm and achieved encouraging results, however, is not applicable to general problems. [air al. (2020) proposed a more general approach that first learns the conditional distribution in the solution space via a GNN and then attempts fix part of discrete variables, producing smaller MILP problem that is computationally cheap to solve. However, fixing many discrete variables might lead to an infeasible MILP model.
To alleviate these issues, we adopt the trust region method and design novel approach that searches for near-optimal solutions within properly defined region. Specifically, we propose a predict-and- search framework that: (i) utilizes trained GNN model to predict marginal probabilities of all binary variables in a given MILP instance; (ii) searches for near-optimal solutions within the trust region based on the prediction.
3.1 PREDICT
In this section, our goal is to train graph neural network using supervised learning to predict the conditional distribution for MILP instances. To this end, introduce the conditional distribution learning. On this basis, we present the training label the form of a vector, i.e. marginal probabili-- ties.
3.1.1 DISTRIBUTION LEARNING
A probability distribution learning model outputs the conditional distribution on the entire solution space of an MILP instance M. A higher conditional probability expected when the corresponding solution is more likely to be optimal. |air et al. (2020) proposed a method to construct the condi- tional distribution with objective values via energy functions, and for solution z, the conditional probability p(a; M) can be calculated by:
exp( - E(x;; M)) Σnt exp(-E(xx;
fc x if x is feasible, where E(x; M) = +oo otherwise.
M)
(3)
This implies that an infeasible solution is associated with a probability O, while the optimal solution has the highest probability value. It's worth noting that each instance corresponds one distribution.
denotes the set of N, feasible solutions to instance M The probability of each solution in the dataset can be calculated by Equation 3 In general, the distance between two distributions can be measured by Kullback-Leibler divergence. Thus, the loss function for the supervised learning task is defined as:
For the collected dataset {Mr,
(-of It.
N
No
exp
(0) =
w Loggo M²), where t
(4)
.o C== exp
( shii
Po (I+ M¹) denotes the prediction from the GNN denoted as Fa with learnable parameters 6. The conditional distribution of an MILP problem can be approximated by a part the entire solution space. Consequently, the number of samples to be collected for training is significantly reduced.
3.1.2 WEIGHT-BASED SAMPLING
To better investigate the learning target and align labels with outputs, we propose to represent the label in vector form. With the learning task specified in Equation (4), new challenge arises: acquiring solutions through high nigh-dimensional sampling is computationally prohibitive. A common technique is to decompose the high-dimensional distribution into lower-dimensional ones. Given an
4

---

Published as a conference paper at ICLR 2023
instance M, let za denote the d element of solution vector z. In Nair et al. (2020), it is assumed that the variables are independent of each other, i.e.,
Pa M)
pe (zz; M). d=1
II
(5)
With this assumption, the high-dimensional sampling problem is decomposed into 1- dimensional sampling problems for each Za according to their probabilities po (x.: M). Since Po (a.a 1; M) = 1 Po (I 0; MM, we only need Pa (za = 1; MM) for d (1. to represent the conditional probability Po (x; M). Then the conditional distribution mapping out- puts n-dninen dimension vector (po (301 M) -y po (5nn 1; M:)).. Hence, the prediction of the
GNN model can be represented as (M = (PI, P2, .., Pa), where ps = pa (ad = 1; M) for d E
Let S S (1, ) denote the set of indices in L' with their dth component being 1.
p1
w
(6)
JEST
where p is normalized by [,]. Given an MILP instance M, we can calculate a corresponding learning target in the form of vector, i., P = (p1, P2: ... Pq), where each component is obtained by applying Equation 66). This equation calculates the marginal probability, where the weight w if the variable holds a value of in the corresponding solution and 0 otherwise. We define such learning target in the form of vector marginal probabilities. Solutions of higher quality will be associated with larger weighting coefficients w and hence contribute more to the loss function.
For the loss function shown in Equation (4), based the assumption in Equation (5) and the calcu- lation of probabilities in Equation we have:
(
logge (af":))
w logoe (I44,, (z);; + Σ w loogo (a (ox):r))
jESt
1882
(p'log (p') (1 p')) log (1 pd)
This indicates that the multi-diimnnsionl distribution learning loss L (0) becomes a summation of each component's probability learning loss. Thus, with Equation (5). the distribution learning is converted to a marginal probabilities learning.
3.2 SEARCH
With marginal probabilities as inputs, we adopted a trust region like method to carry out search algorithm. In this section, we first introduce our observation that the distance between the solution obtained from a rounded learning target and the optimal solution can be very small. Hence, we adopt trust region like method to address aforementioned challenge (II) and present proposition to manifest the superiority of our framework. The complete framework is shown in Algorithm
3.2.1 OBSERVATION
variable's marginal probability closer to if this variable takes a value of in the optimal solution, and 0 otherwise. Given an MILP instance M and its learning target P. we set the partial solution size parameter (kg, kj) to represent the numbers of O's and 1's in partial solution. Let To denote the set of indices of the ko smallest components of P, and 1 denote the set of indices of the kj largest components P. If d I 1 U lo. we get a partial solution hy by:
0 if d E lo. if d E 1T-
Id
1
5

---

Published as a conference paper at ICLR 2023
Let x" denote optimal solution of M, empirically, found Σy is close to 27 as discussed in Appendix D Explicitly, we measure the distance by l norm, and there still exists a small A > 0, such that I - x A while (An k1) is large number. We speculate that, since the optimal solution has the largest weight as shown in equation (6). it closer to the learning target than all other solutions. As result, hypothesize that similar phenomena larger A and the same (ko. k1) when obtaining the set of indices / based on prediction Fg (M).
be observed with slightly
With this observation, is reasonable accelerate the solving process for MILP problems by fixing variables in the partial solution. Specifically, the sub-problem of an instance M using the fixing strategy with the partial solution ž can be formulated as:
min c x; ZE DeS((()))
where S (Tt) = E = However, once σΙ * zj. the fixing strategy may lead to suboptimal solutions even infeasible sub-problems, which can also be observed in Appendix
3.2.2 SEARCH WITHIN A NEIGHRORHOOD
Based on the observations and analysis above, we design a more practicable method. Inspired by trust region method, we use the partial solution as a starting point to establish trust region and search for a trial step. The trial step is then applied to the starting point to generate new solution.
Specifically, given instance M, we acquire the set 7 via the prediction Fo (M) from trained GNN, and get a partial solution f by equation 7 to construct the trust region problem for a trial step d" similar to problem [ (2). At last, output the point updated by trial step. Such a trust region
problem is equivalent to following:
min C² Ir, =EDD((E),
where B (2, = f 1 S. A} denotes neighborhood constraint. In order to reduce computational costs, we solve this problem only once to find a near-optimal solution. We show that our proposed method always outperforms fixing-based methods in Proposition
Proposition 1. let z Fiizing and Search denote optimal values to problems g and (9) respectively. Search S Fiizing, if they have same partial solution žT.
Proof. Note that S (ăz) = B (ā1,0) C (ă,, A), it obvious
C min T x,
min =E)
#EDnS((e)
i.e. Search < < Fiaing
This proposition demonstrates the advantage of our proposed search strategy over fixing strategy: that is, when fixing strategies may lead to suboptimal solutions or even infcasible sub-problems as a consequence of inappropriate fixing, applying such a trust region search approach can always add flexibility to the sub-problem. Computational studies also provide empirical evidence in support of this proposition. Algorithm [ the prediction Fo (M) as input, and acquires partial solution æa and neighborhood constraints. complete solution is then attained by solving the modified instance M' with neighborhood constraints appended. The solving process is denoted by SOLVE (M'), i.c. utilizing an MILP solver to address instance M'.
presents the details of our proposed search algorithm. takes
COMPUTATIONAL STUDIES
We conducted extensive experiments on four public datasets with fixed testing environments to ensure fair comparisons.
Benchmark Problems Four MILP benchmark datasets are considered our computational studies.
Two of them come from the NeurlPS ML4CO 2021 competition Gasse et al. (2022), including the Balanced Item Placement (denoted by IP) dataset and the Workload Appointment (denoted by WA)
dataset Gasse al. 2022) We generated the remaining datasets: Independent Set (IS) and

---

Published as a conference paper at ICLR 2023
Algorithm Predict-and-search Algorithm
Parameter:
Size {kg }. radius of the neighborhood: A
Input: Instance M, Probability prediction P& (M)
Output: Solution x E R"
1: Sort the components in Fg (M) from smallest to largest to obtain sets To and /
2: for d 1: n do
3: if' d E to U1, then
4:
create binary variable 5g if d E To then
5:
6:
create constraint Ia S 6a
7:
else
8:
create constraint
1- 2d S dg
9:
end if
10: end if
end for
12: create constraint
Σ dEloUT,
5p S A
13: Let M' denote the instance M with new constraints and variables
14: Let x: = =SOLVE (M')
15: return
Combinatorial Auction (CA) using Ecole library (Prouvost et al. 2020) Gasse al. (2019) did. Note that the other two datasets from Gasse et al. (2019), Set Covering and Capacitated Facility Location, chosen since they can be easily solved by state-of-the-ard MILP solvers, such as Gurobi and SCIP. Details of our selected datasets can be found in the Appendix FF
Graph neural networks single layer perceptron embeds feature vectors so they have the same dimension of 64, and the layer normalization Ba et al. (2016) is applied for a better performance of the network. Then adopted half-convolution layers from Gasse et al. (2019) conduct
information aggregation between nodes.
Finally, marginal probabilities are obtained by feeding the aggregated variable nodes into 2-layer perceptron followed by a sigmoid activation function.
Training protocol Each dataset contains 400 instances, including 240 instances in the training set, 60 instances in the validation set, and 100 instances in the test set. All numerical results are reported for the test set. Our model is constructed with the PyTorch framework, and the training process runs on GPUs. The loss function is specified in Equation 4 and (5) with batch size of 8. The ADAM optimizer Kingma & Ba (2014) is used for optimizing the loss function with a start learning rate of 0.003.
Evaluation metrics For each instance, we run an algorithm of interest and report its incumbent solution's objective value OBJ. Then note as BKS the objective to the incumbent solution returned. BKS updated if it is worse than OBJ. We define the absolute and relative primal gaps as: gapahs = [BJ - BKS) and gap =\t JBBJ- BKS (BKSS] + 10-1"), respectively and utilize them performance metrics. Clearly, a smaller primal gap indicates stronger performance.
single-thread Gurobi for 3, 600 seconds and de-
Evaluation Configurations All evaluations performed under the same configuration. The evalu- ation machine has two Intel(R) Xeon(R) Gold 51 CPUs 2.00GHz, 256GB ram and two Nvidia V100 GPUs SCIP 8.0.1 Bestuzheva et al. (202T). Gurobi 9.5.2 Gurobi Optimization, LLC (2022) and PyTorc 1.10.2 Paszke et al. (2019) are utilized in our experiments. The emphasis for Gurobi and SCIP is set focus finding better primal solutions. The time limit for running each experi- ment is set to 1, 000 seconds since a tail-off of solution qualities was often observed after that.
Data collection Details will be provided in the Appendix
B

---

Published as a conference paper at ICLR 2023
5 RESULTS AND DISCUSSION
To investigate the benefits of applying our proposed predict-and-search framework, we conducted comprehensive computational studies that: (i) compare framework with SCIP and Gurobi; (ii) compare our framework with Neural Diving framework (Nair et al. 2020). Other numerical experiments including comparing against modified version of confidence threshold neural div-
ing Yoon 2022) along with implementation details can be found in the Appendix D
5.1 COMPARING AGAINST STATE-OF-THE-AKE SOLVERS
In what follows, we utilize SCIP (Gurobi) as MILP solver in proposed framework and denote our approach as PS+SCIP (PS+ Gurobi).. Figure
exhibits Exhibbts the progress of average gäPret as solving process proceeds. In Figure 2a notice significant performance improvement of our framework (blue) upon default SCIP green), and such an improvement is also observed for WA, CA and IS datasets shown in 2b 2c and 2d Compared with default Gurobi (black), approach(red) still performs better, specially in the I dataset. We remark that, in Figure PS+Gurobi obtained optimal solutions to IS problems within 10 seconds. The performance comparison in Figure Saareealss also indicates that our proposed framework can bring noticable performance improvement upon MILP solvers, regardless of the solver choice.
awerage prénal gn0
0.83
0//
100g
0.gg
time (sec)
time (sec)
time (sec)
time (sec)
(a)
(b) WA
(c) CA
(d) IS
SCP
PS SCIP
Gurobi
PS+Gurobi
Figure 2: Performance comparisons between PS, Gurobi and SCIP, where the y-axis is relative primal gap averaged across 100 instances; each plot represents one benchmark dataset.
In Table we present objective values averaged across 100 instances the time limit of 1, 0.0 seconds. Column "gapabs" provides the absolute primal gap at 1, 0000 seconds, and column "gain" presents the improvement of our method compared over an MILP solver. For instance, Table shows that BKS for IP dataset is 12.02, and the absolute primal gaps of SCIP and PS+SCIP are 7.41 and 3.44 respectively. Then gain is computed as (7.41 3.44) /7411 x 100% = 53.6%. claim that our proposed framework outperforms SCIP and Gurobi with
According to Table average improvements 51. 51%1% and 9.9%, respectively. We notice that the improvement for Gurobi not as significant as for SCIP since Gurobi significantly more capable in terms of identifying high-quality solutions than SCIP.
Table 1: Average objective values given by different approaches at 1,000 seconds.
SCIP
PS+SCIP
Gurobi
PS+Gurobi
datasct
gaiti
guin
gaPa
OBJ
gaPase
OBI
gAPabe
OBJ
gaPate
TP
12.02
19.43
7.41
15.46
3,44
53.6%
12.65
0.63
12.71
0.69
-9.5%
700.94
704.23
3.29
702.35
1.41
57.1%
701.24
0.30
701.22
0.28
6.7%
685.04
684.94
685.03
0.01
90.0%
685.04
0.00
685.04
0.00
0.00
CA
23,680.01
23.671.66
23,671.95
8.06
3.5%
23.635.07
44.94
23.654.47
25.54
43.2%
$1.1
9.9%
8

---

Published as a conference paper at ICLR 2023
5.2 COMPARING AGAINST NEURAL DIVING
Another interesting comparison should be conducted against the state-of-the art ML method for optimization: the Neural Diving framework with Selective Net. However, since detailed settings and codes of the original work Nair al. (2020) not publicly available, reproducing the exact same results is impractical. To our best effort, a training protocol with fine parameter tuning and an evaluation process are established following algorithms provided in |air al. (2020). Three six tested benchmark datasets used in Nair et al. (2020) are publicly available: Corlar, Neural Nenwork Verification, and MipLib. Most Corlat instances can be solved by SCIP within a few seconds; MipLib contains instances with integer variables rather than binary variables, which is out of the scope of this work. Hence, Neural Network Verification (denoted as NNV) is chosen as the benchmark dataset for the comparison study. It is noteworthy that, empirically, turning on the presolve option in SCIP (Bestuzheva et al., 202I) causes false assertion of feasibility on many NNV instances. Hence, in our experiments on the NNV dataset, the presolve option is turned off, which potentially hurts the performances of both SCIP itself and frameworks implemented with SCIP.
Clearly, the Under such cireumstances, the best performance obtained is exhibited in Figure 3a
Neural Diving framework achieves significant improvement over default SCIP. With such an imple-
0.8
0..8
Brimal
average primal
0.6
0.02
0.4
0.4
0.01
0.2
0.2
0.0
10:
10a
10a
10a
10'
10
101
10'
10
time (soc)
time (sec)
time (sec)
(a) NNV
(b) IP
(c) IS
SCIP
Neural SCVI
PS+SCIP
Figure 3: The experiment shown in Figure 3a validates the performance of our Neural Diving imple- mentation by comparing with default SCIP on NNV dataset. (nneee33aanBBeeexiiiii performance comparisons between PS and Neural Diving framework on IP and IS datasets. All methods related are implemented with SCIP. The result shows that our proposed method outperforms the Neural Diving framework significantly.
mentation, we can start to compare our proposed framework against the Neural Diving approach. Due to the limitation of computational power, we are not able find suitable settings of parameters to train Neural Diving framework on WA and CA datasets. Hence we conducted experiments only on IP and IS datasets. As shown in Figure 3bb abjand our predict-and mreiictandd-seacch framework produced at least three times smaller average relative primal gaps. An interesting observation is that Neural Diving framework failed to surpass SCIP on IS dataset where the optimality is hard to achieve, while our framework outperformed both SCIP and the implemented Neural Diving method.
CONCLUSIONS
We propose a predict-and-seett framework for tackling difficult MILP problems that are routinely solved. A GNN model was trained under supervised learning setting to map from bipartite graph representations of MILP problems to marginal probabilities. We then design trust region based algorithm to search for high-quality feasible solutions with the guidance of such a mapping. Both theoretical and empirical supports are provided to illustrate the superiority of this framework over fixing-base based strategies. With extensive computational studies on publicly available MILP datasets, demonstrate the effectiveness of our proposed framework in quickly identifying high tigh-quality feasible solutions. Overall, our proposed framework achieved 51. 1% and 9.9% better primal gaps comparing to SCIP and Gurobi, respectively.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work is supported by the National Key R&D Program of China under grant 2022YFA Huawei: Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project WIZZQSS--KCCYB20OO
University Development Fund UDF01001491 from The Chi- nese University of Hong Kong, Shenzhen; Guangdong Key Lab on the Mathematical Foundation of Artificial Intelligence, Department of Science and Technology of Guangdong Province.
REFERENCES
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. 1xXvv1607.004500 2016.
arXiv preprint
Irwan Bello*, Hieu Pham Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning, 2017. URL httpsts/oppereeiieee net/E
orum?id rJY3399e
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour d'horizon. European Journal of Operational Research, 290(2):
405-421, 2021.
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doormalen,, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Well- ner, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 8.0. ZIB-Report 21-41, Zuse Institute Berlin, December 2021. URL
dew.r.. nbn
de: 02900297-22 zib 85309
Bernd Bischl, Pascal Kerschke, Lars Kotthoff, Marius Lindauer, Yuri Malitsky, Alexandre Fréchette, Holger Hoos, Frank Hutter, Kevin Leyton- Brown, Kevin Tiemny, et al. Aslib: A benchmark library for algorithm selection. Artificial Intelligence, 237:41-58, 2016.
Zhi-Long Chen. Integrated production and outbound distribution scheduling: review and extensions. Operations research, 58(1):130-144 130-148, 2010.
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 Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1452-1459, 2020.
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 Chmicla, Justin Dumouchelle, Ambros Gleixner, Aleksandr M. Kazachkov, Elias Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris J. Maddison, Morris Christopher, Dimitri Papageorgiou, Augustin Parjadis, Sebastian 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 NeurlPS 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.. . mwr. www.mmrrrsss..............mmmmse
press / / wwllvv//66//......aa gasse22a.a.......mmgg. html
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.
10

---

Published as a conference paper at ICLR 2023
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https: www. robi com
Humayun Kabir, Ying Wang, Ming Yu, and Qi-Jun Zhang. High-dimensional neural-network tech- nique and applications to microwave filter modeling. IEEE Transactions Microwave Theory and Techniques, 58(1):145-155)) 2009.
Elias Khalil, Pierre Le Bodic, Le Song. George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guid- ing combinatorial solvers. Update, 2:x3, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Markus Kruber, Marco Lübbecke, and Axel Parmentier. Learning when to use a decomposition. In International conference on Al and OR techniques in constraint programming for combinatorial optimization problems, pp. 202-210. Springer, 2017.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, 31, 2018.
Li Liu and Qi Fan. Resource allocation optimization based mixed integer linear programming in the multi-cloudlet environment. IEEE Access, 6:24533-24542 2018.
Paramet Luathep, Agachai Sumalee, William HK Lam, Zhi-Chun Li, and Hong K Lo. Global optimization method for mixed transportation network design problem: mixed- linear programming approach. Transportation Research Part B: Methodological, 45(5):808-827, 2011. 1.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Bren- dan O' O'Donoguue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yu- jia Li, Oriol Vinyals, and Yori Zwols. Solving mixed integer programs using neural networks, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, peg--performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bue, E. Fox, and R. Garnett (eds.), Advances Neural Information Processing Systems 32, pp. 8024-808 Curran Associates, Inc., 2019.
Yves Pochet and Laurence A Wolsey, Production planning by mixed integer programming, volume 149. Springer, 2006.
Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. URL httthttt//ppeneeeet
Anita Schöbel. A model for the delay management problem based mixee-inlegrr-poraanning Electronic notes in theoretical computer science, 50(1):1-10, 2001.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 28, Curran Associates, Inc., 2015. URL /tRL://tt//////pcciiinoo aper /01///21//5555 e 9921001 F2 wtw.oo0000000000aeeeeeeeee heteabbbbbeeeee4222eeeeee33
www.ipe.e....... cc/p
Jean-Paul Watson and David L Woodruff. Progressive hedging innovations for class of stochastic mixed-integer resource allocation problems. Computational Management Science, 8(4):355-370 2011.
11

---

Published as a conference paper at ICLR 2023
Taehyun Yoon. Confidence threshold neural diving, 2022.
Ya-xiang Yuan. Recent advances in trust region algorithms. Mathematical Programming, 151(1): 249-281, 2015.
12

---

Published as a conference paper at ICLR 2023
A HALF CONVOLUTION
We use two interleaved calf-convolutions Gasse et al. (2019) to replace the graph convolution. After that, the GNN we used can formulated as:
MLP
(k-1)
(k-1))
ie {n,n + 1,... n + m n m)
(EN(v.)
1 (LP
Σ
((--1)
iE (1.,......1
(EN(
where MLP())
MLP(() and g (-) are 2-layer perceptrons with ReLU activation functions. That &
is, half-convolution is performed to promote each constraint node aggregating information from its relevant variable nodes; after that, another one is performed on each variable node to aggregate information from its relevant constraint nodes and variable nodes.
B DATA COLLECTION
The training process requires bipartite graph representations of MILP problems as the input and marginal probabilities of variables the label. We first extract the bipartite graph by embedding variables and constraints as respective feature vectors (see Appendix [). Then, we run a single- thread Gurobi with time limit of 3,600 seconds on training sets collect feasible solutions along
with their objective values. These solutions are thereafter weighted via energy functions as in Equa- tion to obtain marginal probabilities.
C COMPARING OBJECTIVE VALUES IN DIFFERENT PARTIAL SOLUTIONS
We also scrutinize why fixing strategy could fail. Variables in the optimal solution are randomly perturbed to simulate real-world setting that prediction is very likely to be inaccurate. Figure exhibited a trend that, as we perturb more variables, the absolute primal gap (green) increases, and the percentage of infeasible sub-problems (red) increases. The absolute gaps shown Figure 4a indicate large performance drawbacks given that the optimal objective value is 685. Convincingly, we conclude that fixing approaches presumably produce sub-optimal solutions. Besides, as shown in Figure 4b) randomly perturbing variable result in 20% of infeasible sub-problems. That is, fixing strategy could lead to infeasible sub-problems even relatively accurate predictions are provided.
max mn average
Teas bally
0.2
63
vartones
(a) MA
(b)
Figure 4: This plot shows how qualities of solutions to sub-problems vary as variables randomly perturbed in one WA instance. Maximum, minimum and average values are presented in the plot. The x-axis is the number of variables perturbed in the partial solution while y-axis of Figure 4a is the absolute primal gap between average objective values (only include feasible sub- problems) and the optimal objective value; y-axis of Figure 4b on the right is the percentage of infeasible sub- problems.
13

---

Published as a conference paper at ICLR 2023
D COMPARING AGAINST A MODIFIED VERSION OF CONFIDENCE THRESHOLD NEURAL DIVING
In this part, we demonstrate our advantage over fixing strategy by conducting numerical exper- iments. In Yoon| (2022)'s 's work, thresholds are chosen to determine how many variables fix. We modify this method so that the number of variables becomes tunable hyper-parameter, which makes the procedure more controllable and flexible. We directly use the learning target to define confidence scores, and we obtain partial solutions by setting different size parameters (Kp, k1) as stated Section 3.2.1 & norm is utilized for measuring such distances.
selected (700, 0), (750, 0), (800, 0), (850, 0), and (900, 0) as size parameters and obtained their corresponding & dis- tances as 0.00, 0.04, 1.20, 35.26, and 85.01. We observed that such distances can small if only small portion of variables are taken into consideration. However, involved variables, the distance increases dramatically. Hence, the predict-and-seard approach can involve larger set of variables than fixing strategy does while still retaining the optimality.
enlarge the number of
To support this argument, we compare the performance of our approach with that of a fixing strat- egy. For simplicity, we denote the modified version of confidence threshold neural diving as Fixing in Figures. Figure 5 shows the average relative primal gap achieved by different approaches, where both approaches use fixed number of selected variables. One can spot the dominance of our ap- proach over the modified version of confidence threshold neural diving from Figure Bai this implies that such fixing strategy only leads to mediocre solutions, while the search method (red) achieves solutions with better qualities. In Figure 5d] both approaches are capable of finding optimal so- lutions instantly, but the ones obtained by fixing method is far from optimal solutions to original problems. We notice that in Figure 5b and |c] our framework struggles to find good solution in the early solving phases, but produces equivalent or better solutions within 1, 000 seconds comparing to the fixing method. A possible reason is that our solution results in larger feasible regions comparing to the fixing strategy. Conclusively, our framework always outperforms the fixing strategy.
wesnge prinal KN0
wenge Feal
$2:0
42
Hacked
50.30
awnnge
(sec)
(sec)
(swc)
(a) IP
(b) WA
(c) CA
(d) IS
Finng: Gurchi
PS Curchi
Figure 5: This figure shows average gaprel achieved by the search method and the fixing method under the same partial solution. The results are averaged across 100 instances, and each plot rep- resents one dataset. The proposed framework shows constantly dominant performance over the fixing-based method.
E FEATURE DESCRIPTIONS FOR VARIABLE NODES, CONSTRAINT NODES AND EDGES
To encode MILP problems, we propose set of features extracted from constraints, variables, and edges. This set of features relatively hightweeihhted and generalized; each feature is obtained either directly from the original MILP model by conducting simple calculations. Moreover, such extractions do not require pre-solving the MILP instance, which would save a significant amount of time for large and difficult MILP problems.
14

---

Published as a conference paper at ICLR 2023
Table 2: Features in embedded bipartite representations
features.
description
obj v_coeff Nv_coeff
normalized coefficient of variables the objective function average coefficient of the variable in all constraints
degree of variable node in the bipartite representation maximum value among all coefficients of the variable minimum value among all coefficients the variable binary representation to show if the variable is
max_coeke
Variable
min_coeff
int
integer variable
binary encoding of the order of appearance for each variable among all variables.
12
pos emb
coeff
average of all coefficients in the constraint degree of constraint nodes in the bipartite representation
Nc coeff
Constraint
rhs
value of the constraint
sense
the sense the constraint
Edge
coeff
coefficient variables in constraints
F SIZES OF BENCHMARK PROBLEMS
Table 3 exhibits dimensions of the largest instance of each tested benchmark dataset. The numbers of constraints, variables, and binaries are presented.
Table 3: Maximum problem sizes of each dataset
dataset
constr.
var.
# binary var.
IP
195
1,083
1,050
WA
64.480
61,000
1,000
IS
600
1,500
1,500
CA
6,396
1,500
1,500
PARAMETRIC SETTINGS FOR EXPERIMENTS
For experiments where our predict-and-seart framework is compared with SCIP, Gurobi, and lxing-based strategy, the settings for listed in Table Based on the performance of the underlying solver, various settings of (ko, k1) are used to carry out experiments for each benchmark dataset shown in Table 4 The radius of the search area A is chosen respectively for different implementations (PS+SCIP, PS+Gurobi, and Fix PiXIng+SCIP) of our framework as shown in Table
(ko, k2) and the neighborhood parameter A
Table 4: kn ki, and A settings for different dataset
dataset
PS+SCIP
PS+Gurobi
Fixing+SCIP
ko, ki
A
ko, ki
ko
A
IP
400, 5
400, 5
10
400,
0
WA
500
5
0, 500
10
0, 500
0
I5
300, 300
300, 300
20
300, 300
0
CA
400, 0
10
600, 0
600, 0
0
15


Reviews:
[{"review_id": "mnghukuNSjo", "reviewer": "Reviewer_BsbB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper presents a heuristic for constructing good feasible solutions for families of related mixed-integer linear programming (MILP) problems. The heuristic proceeds by taking an instance from a given MILP family and 1) using a machine learning model to output weights (roughly: approximate solution values) for each decision variable, then 2) solve a sub-MILP in the (small) neighborhood around the point proposed by the predictive model. Computational results suggest that this heuristic can outperform the suite of heuristics in SCIP and Gurobi.", "summary_of_the_review": "The paper is very well-written, and provides a natural but worthwhile extension of a recent stream of algorithms for producing heuristic solutions to families of related MILP instances. My concerns are mostly based around the baseline for comparison used in the computational section.", "strength_and_weaknesses": "The proposed method is a natural and reasonable upon ML-based heuristics that are based on variable fixing. While this extension is not particularly deep and uses \"off-the-shelf\" concepts, the computational results seem to indicate its utility. The paper is extremely well-written and does a great job introducing each of the concepts used to develop the algorithm.\n\nWhy did the authors not compare against the ML-based fixing algorithms that they reference in the introduction? That seems to be the fairest baseline for comparison, as these algorithms are the most similar in setting and approach to the one presented by the authors.\n\nI would appreciate more detail (in the appendix, but also some in the text) about the implementation details of the algorithm. For example, I am curious how the algorithm is implemented with SCIP and Gurobi -- presumably it is used via a heuristic callback with both solvers? If so, can the authors break out how much time is spent in the callback (and how many calls), and what fraction of the total allotted wall time this eats up?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kAwvL028BnP", "reviewer": "Reviewer_E5hv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "Authors propose a primal heuristic for solving MIP, following much of Neural Diving strategy from Nair et al (2021). Instead of fixing predicted variables from ML model, authors propose to solve a modified MIP problem which constrains the solution space to be the L1 ball around the predicted solution. Authors demonstrate across two datasets from ML4CO competition and two synthetic datasets from Ecole package that the proposed method works better than the baseline of fixing variables from predicted solution.", "summary_of_the_review": "While the paper heavily builds upon Neural Diving of Nair et al (2021), authors deviate from Neural Diving in their decision to not use SelectiveNet for uncertainty quantification. Hence, it is unclear whether the claimed improvement over the fixing strategy is the consequence of using a naive uncertainty quantification method, or the benefit of the proposed Predict-and-Search strategy.", "strength_and_weaknesses": "The main strengths are the simplicity of the approach and the practical appeal. It is conceivable predicted variables from ML model is often not feasible, hence making only a \"soft\" commitment and searching in an L1 ball seems like a practically useful solution. The method is also conceptually simple and intuitive.\n\nThe main weakness of this paper is that the paper builds upon Neural Diving of Nair et al (2021) but authors don't compare against Neural Diving. While Neural Diving uses SelectiveNet to identify variables to fix, authors simply rely on confidence scores. Hence it is unclear whether the proposed predict-and-search (PS) method is superior to fixing strategy, or this is just the consequence of using a naive method for uncertainty quantification. I understand an open-source implementation of Neural Diving is not available (as far as I know), but given high similarity of the proposed method and Neural Diving, I still think authors should've implemented SelectiveNet (the only component that seems to be missing in the current implementation) and compare against full Neural Diving algorithm from Nair et al.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TsgJ7f1njb", "reviewer": "Reviewer_DX2F", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a predict-and-search framework for solving mixed-integer linear programming (MILP) problems. Specifically, they first predict the solution distributions, and then search for near-optimal solutions within a trust region constructed from the prediction. Experiments demonstrate that the proposed framework improves the performances of two state-of-the-art optimization solvers SCIP and Gurobi on several datasets.", "summary_of_the_review": "Overall, I believe that this paper is marginally below the acceptance threshold. Though the authors propose a novel predict-and-search framework for solving mixed-integer linear programming problem, they miss some important baselines to demonstrate the effectiveness of their proposed framework. Moreover, they may want to improve the writing.", "strength_and_weaknesses": "Strengths:\n1. The proposed predict-and-search framework is novel.\n2. The trust region in the search algorithm is well designed.\n3. Experiments demonstrate that the proposed framework improves the performance of SCIP and Gurobi on several datasets.\n\nWeaknesses:\n1. The paper is hard to follow as the presentation of the proposed approach is unclear. For example, the definition of the so-called “weighted conditional marginal probability distribution” is confusing.\n2. The authors may want to add more baselines to demonstrate the effectiveness of the proposed approach. For example, as the predicting part of the method mainly follows [1], the authors should add [1] as a baseline.\n3. The authors may want to further discuss on the connections and differences between the proposed predict-and-search approach and existing predicting based (e.g., [1]) and searching based methods (e.g., [2]).\n4. The authors only consider discrete variables to be binary, which limits the applications of the proposed framework.\n5. In the 4th line in Section 5.2, why are the values of the size parameters the same?\n\nMinor Issue:\n1. The authors may want to use “\\citep{}” instead of “\\cite{}” for some of the citations.\n\n[1] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, and Yori Zwols. Solving mixed integer programs using neural networks, 2020.\n\n[2] Li Z, Chen Q, Koltun V. Combinatorial optimization with graph convolutional networks and guided tree search[J]. Advances in neural information processing systems, 2018, 31.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7Cn2yF-vzjV", "reviewer": "Reviewer_jKg3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers a neural network based algorithm for solving MILPs. The main novelty lies in the proposed trust region algorithm to construct solutions from the output of the neural network.\n", "summary_of_the_review": "I think the paper is interesting, however comparison to other work seems could be improved.", "strength_and_weaknesses": "I think the paper considers an interesting problem, which is potentially of value to those working in the field of machine learning for combinatorial optimization. My specific comments and questions are as follows:\n\n1) I think a more detailed comparison with the neural diving method of Nair et al 2020 would be really interesting. The authors mention the work of Nair et al 2020, however, it is not clear how the performance of their approach would compare.\n\n2) In addition, I think it is interesting to consider how the performance of other neural network based MILP solver methods would compare against the proposed method.\n\n3) The algorithm to solve Eq 11 seems critical for the proposed framework. In my opinion, it would increase the readability to include this algorithm in the main body of the paper.\n\n4) Is the algorithm/solver for SOLVE(M’) in Alg. 1 discussed somewhere in the paper?\n\n5) I think a simple yet interesting baseline to compare with the proposed method is by simply solving the relaxed LP and running the trust region algorithm on the solution of the relaxed LP.\n\n6) As far as I understand, the reported numerical results are for the MILP instances in the test set, not training or validation set. Is this correct? Also, is this explicitly stated somewhere?\n\n7) I think it would be nice to include a discussion on the neural network generalization. How does the performance on the training set compare to performance on the test set?\n\n8) In my opinion, the claim that “Most of the end-to-end approaches directly predict solutions to MILP problems, ignoring feasibility requirements enforced by model constraints. As a result, the solutions provided by ML methods could potentially violate constraints.” needs references to some works where this is the case. \n\nMinor issues:\n1) The font size for Fig.3 is too small.\n2) Typo in second sentence of the conclusion: supervise(d)-learning\n3) Typo in page 8: “are took into consideration”\n4) Typo in page 7, equation (6) and (6)\n5) Extra parenthesis in the second line of the equation block for L(\\theta): logp_(\n6) Typo in the line under eq 11, \\hat{x}_I - \\hat{x}_I\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster