Learning to Generate Columns with Application to Vertex Coloring
Authors: Yuan Sun
Andreas T Ernst
Xiaodong Li
Jake Weiner
Venue: ICLR 2023 poster (2023)
Keywords: Machine learning
combinatorial optimization
column generation

Abstract: We present a new column generation approach based on Machine Learning (ML) for solving combinatorial optimization problems. The aim of our method is to generate high-quality columns that belong to an optimal integer solution, in contrast to the traditional approach that aims at solving linear programming relaxations. To achieve this aim, we design novel features to characterize a column, and develop an effective ML model to predict whether a column belongs to an optimal integer solution. We then use the ML model as a filter to select high-quality columns generated from a sampling method and use the selected columns to construct an integer solution.  Our method is computationally fast compared to the traditional methods that generate columns by repeatedly solving a pricing problem. We demonstrate the efficacy of our method on the vertex coloring problem, by empirically showing that the columns selected by our ML model are significantly better, in terms of the integer solution that can be constructed from them, than those selected randomly or based only on their reduced cost. Further, we show that the columns generated by our method can be used as a warm start to boost the performance of a column generation-based heuristic.

Published as a conference paper at ICLR 2023
LEARNING TO GENERATE COLUMNS WITH APPLICATION TO VERTEX COLORING
Yuan Sun" La Trobe University
Andreas T. Erast Monash University
Xiaodong Li RMIT University
Jake Weiner
RMIT University
ABSTRACT
We present a new column generation approach based on Machine Learning (ML) for solving combinatorial optimization problems. The aim of our method is generate high-quality columns that belong to an optimal integer solution, in con- trast to the traditional approach that aims at solving linear programming relax- ations. To achieve this aim, we design novel features to characterize column, and develop an effective ML model to predict whether a column belongs to an op- timal integer solution. We then use the MI. model as filter to select high-quality columns generated from a sampling method and use the selected columns to con- struct an integer solution. Our method is computationally fast compared to the traditional methods that generate columns by repeatedly solving a pricing prob- lem. We demonstrate the efficacy of our method on the vertex coloring problem, by empirically showing that the columns selected by our ML model are signifi- cantly better, in terms of the integer solution that can be constructed from them, than those selected randomly or based only on their reduced cost. Further, we show that the columns generated by our method can be used warm start boost the performance of a column generation- baased heuristic.
INTRODUCTION
Machine Learning (ML) has been increasingly used to tackle combinatorial optimization problems (Bengio et al., 2020), such as learning to branch in Mixed Integer Program (MIP) solvers (Khalil
al.
2016 Balcan al. 2018 Gupta et al. 2020), learning heuristic search algorithms (Dai al. Li ct al. 2018). and learning to prune the search space of optimization problems (Lauri &
2017
Dutta 2019: Sun et al. 202 Hao et al., 2020). Given a large amount of historical data to learn
from, MI. techniques can often outperform random approaches and hand-crafted methods typically used in the existing exact and heuristic algorithms.
Predicting optimal solutions for combinatorial optimization problems via ML has attracted much
attention recently. A series of studies (Li et al. 2018 Lauri & Dutta 2019: Sun et al. 202 lb
Grassia et al. 2019 Fischetti & Fraccaro, 2019 Lauri et al. 2020; Sun et al. 202 2022, Ding jtt al. 2020 Abbasi et al.) [020] Zhang et al. (020)) have demonstrated that predicting optimal solution values for individual variables
achieve reasonable accuracy. The predicted solution
can be used in various ways (e.g., to prune the search space of problem (Lauri & Dutta 2019 Sun
let al. 2021b Hao et al. 2020) or warm-start search method (Li al., 2018]/Zang et al. 2020
Sun et al. 2022)) to facilitate the solving of combinatorial optimization problems.
However, for symmetric optimization problem, predicting optimal values for individual decision variables does not provide much benefit for solving the problem. For example, in the vertex coloring problem (VCP) (See Section for formal problem definition), a random permutation of the colors in an optimal solution results in an alternative optimal solution, and thus predicting the optimal colors for individual vertices is not very useful. On the other hand, predicting a complete optimal solution for problem directly is too difficult. This is partially due to the ha-hards of a problem and the difficulty in designing generic representation for solutions of different sizes.
In this paper, we take an intermediate step by developing an effective ML model to predict columns (or fragments (Alyasiry et al. 2019h) that belong to an optimal solution of combinatorial opti- mization problem. To illustrate our method, we use the VCP as an example, in which a column is
"Corresponding author; yuan. sun @ latrohe.edu.ar

---

Published as a conference paper at ICLR 2023
Maximal Independent Set (MIS) Tarjan & Trojanowski 1977), whose vertices can share the same color in a feasible solution. The aim of our ML model is to predict which MISs belong to an optimal solution for a given problem instance.
To train our ML model, we construct a training set using solved problem instances with known optimal solutions, where each training instance corresponds to a column in a training graph. Three categories of features are designed to represent a column, including 1) problem-speciffc features computed from the graph data, 2) statistical measures computed from sample solutions, and 3) línear program (LP) features (e.g., reduced cost) computed from the LP relaxation of the MIP model. A training instance is labeled as positive if the corresponding column belongs to an optimal solution; otherwise it is labeled as negative. This is then a standard binary classification problem and any existing classification algorithm can be used for this task.
We use the trained ML model to evaluate the quality of columns, and combine it with a sampling method to generate high-quality columns for unseen problem instances. Specifically, our method starts by randomly generating subset of columns. It then computes the features for each column in the current subset and uses the trained ML model to evaluate the quality of the columns. The low- quality columns predicted by ML are replaced by the new ones generated by sampling method. This process is repeated for multiple iterations with low-quality columns filtered out and high-quality columns remaining. A subproblem formed by the selected columns is then solved to generate an integer solution. We call this method Machine Learning- baaedd Column Generation (MLCG).
Our MLCG method is significant departure from the traditional CG methods (üübbecke & Desrosiers 2005] Mehrotra & Trick 1996). Firstly, the traditional methods typically generate columns solve the LP relaxation of the MIP, while our MLCG method aims at generating columns that are included in a high-quality integer solution. Secondly, the traditional methods select columns only based on their reduced cost, while our method learns a more robust criterion via ML based on a set of features for selecting columns. Thirdly, the traditional methods typically generate columns by repeatedly solving a pricing problem, while our method samples columns on the fly and uses the trained ML model to filter out low-quality columns.
To demonstrate the effectiveness of our MLCG method, we evaluate on the VCP, though the same idea is generally applicable to other combinatorial optimization problems. We empirically show that our ML model can achieve a high accuracy in predicting which columns are part of an optimal solution on the problem instances considered. The columns selected by our ML model are significantly better, in terms of the integer solution that can be constructed from them, than those selected randomly or based purely their reduced cost. Furthermore, we use the subset of columns generated by our method to warm-start a CG-based heuristic, the Restricted Master Heuristic (R.H)) (Taillard 1999 Bianchessi et al. 2014), and the results show that method combined with RMH significantly outperforms R.H. alone in terms of both solution quality and run time.
2 BACKGROUND AND RELATED WORK
Vertex Coloring Problem Formulation. Given an undirected graph G(V, where V is the set of vertices and E is the set of edges, the objective of VCP is to assign color to each vertex, such that the adjacent vertices have different colors and the total number of colors used is minimized. Since adjacent vertices cannot share the same color by the problem definition, the vertices that are of the same color in any feasible solution must form an Independent Set. Therefore, the VCP equivalent to a set partitioning problem which aims to select the minimum number of Independent Sets from a graph such that each vertex is covered exactly once. This is also equivalent to a set covering problem, the objective of which is to minimize the number of Maximal Independent Sets (MISs) selected such that each vertex in the graph is covered at least once (Mehrotra & Trick 1996).
Let S denote MIS, S denote the set of all MISs of graph G, and S. denote the set of MISs that contain vertex U E V. We use binary variable gg to denote whether MIS $ is selected. The set covering formulation of VCP is defined in (1(3) (Mehrotra & TTick 1996). A variable Is corresponds and also a column of the constraint matrix of the MIP. As the number of MISs in graph is potentially exponential in [Vi the number of columns of the MIP can be very large. It can be shown that the I.P relaxation of (1-3)
min Σ xs:
(1)
SE8
s.l. Σ xg 1, VEV; (2)
MIS the graph
SES.
is
(0,1),
SES. (3)
2

---

Published as a conference paper at ICLR 2023
provides a bound at least as good as that of the compact MIP formulation (Mehrotra & Trick [996]. Although the set covering formulation has a tight LP relaxation, solving the large LP rela relaxation is difficult. The traditional CG and branch-and-pae -ndd-ricee (B&P) algorithms (Mchrotra & Trick 1996. Barnhart et al,, 1998) Gualandi & Malucelli 2012) resolve this by generating a subset of columns on the fly, instead of enumerating all the columns upfront, which will be described in the following.
Column Generation. Let S S denote arbitrary subset of MISs based on which at least one feasible LP solution can be generated, and S,, denote the set of MISS in S that contain vertex v E V. To solve the LP relaxation of ([-3). master problem 4 6 with S. The dual solution for constraint (5) can be obtained after solving the restricted
min
zS.
(4)
SEB
s.t.
Σ Js 2 1,
V V;
(5)
3), CG starts by solving a restricted
SEc.
0 rg S 1,
SEB.
(6)
master problem: π = {T1, TT, ................................ ] (Tr 2 0), which can be used to compute the reduced cost of a variable zg for any S E S. Let u {21. U2..... "[vi be the binary string representation of a MIS S, where u, = 1 if the vertex E S. otherwise u, = O. The reduced cost of Is (for MIS S) is computed as 1 - >| function coefficient of zg would have to be reduced before S would be cost-effective to use (i.e., Is would take non-zero value in the optimal LP solution). In other words, if the reduced cost of variable 2ş is negative, adding S into the subset & and solving the restricted master problem again would lead to a better IPP solution assuming nondegeneracy. If the reduced cost of æs is non-negative for every S E S, adding any other MIS into 3 would not improve the LP solution. Hence, the LP has been solved to optimality with the current subset S.
;=1 T Ug The reduced cost computes the amount by which the objective
However, the number of MISs in graph may be exponentially large, explicitly computing the reduced cost for every decision variable z often impractical. CG resolves this issue by optimizing a pricing problem 7 compute the minimum reduced cost among all variables. The constraints the solution is a valid MIS in the graph G. The obje- ctive 7 minimizes the reduced cost among all possible MISS in the graph. This equivalent to solving a maximum weighted independent set problem with the dual value ग; being the weight of the vertex o (for 1, ......... [VD (Sakai et al. 2003). If the minimum objective value of the pricing problem is negative, the optimal solution generated 2z" (which a MIS) will be added into S, and the above process is repeated. If the minimum objective value of the pricing problem is zero, the LP relaxation of [ 3h has been solved to optimality with the current S. and the optimal objective value of the restricted master problem provides a valid lower bound for
M Σ i=1
min 1 12
as . Us.
(7)
s.t. us + uj S 1,
(0,, v3) E E; U/2 E V. (9)
(8)
(8) and (9) ensure that
W E (0. 1},
To generate an integer solution to the MIP be solved by MIP solver. This approach is known as RMH (Tailaard 1999. Bianchessi et al.) 2014). Alternatively, CG can be applied at each node of the waach-and-boumt tree to compute an LP bound, resulting in B&P algorithm (Mehrotra & Trick 1996; Gualandi & Malucelli 2012).
sub-problem with the subset of MISs $ can
A potential issue of the CG approach is that it may require to solve many instances of the pricing problem, which may be hP-hard itself. Further, the columns are generated only based the reduced cost. Although it guarantees the optimality of the LP relaxation, the integer solution contained in the subset may not be of high quality. This motivates us use MI. to learn a better rule from a set of features (including reduced cost), to predict which columns belong to an optimal integer solution.
There have been only few studies that use ML to improve CG and B&P algorithms. Václavík al. (0018) developed a regression model to predict an upper bound on the optimal objective value of the pricing problem, which was then used to prune the search space of the pricing problem. Morabit et al. (2020) developed supervised learning model to select the minimum number of columns that could lead to the best LP solution at each iteration of CG. ".,eShen al.) (2022) developed an ML-based pricing heuristic to boost the solving of pricing problems. These methods are still within the scope of the traditional CG framework, which is significantly different from our method, as explained earlier. The MI. model designed in (Furian et al., (02T)) was used to configure the variable selection and node selection in a B&P algorithm, but not about to improve CG.
3

---

Published as a conference paper at ICLR 2023
3 PREDICTING OPTIMAL COLUMNS
In this section, we develop an effective ML model to predict which columns (i.c., MISs) are part of an optimal solution for the VCP.
3.1 FEATURE EXTRACTION
Let S denote a subset of MISs generated from a graph GVV which contains at least one feasible solution. We extract three categories of features to characterize each MIS in S. Note that if the graph is small, we can easily enumerate all the MISs in it, and & in this case is the full set of MISs.
Problem-specific features. Let $ be a MIS in S, and |S] be the size of S. The first problem-speciie Generally, the larger MIS is, the more likely it belongs to an optimal solution. This is simply because a larger MIS contains more vertices, and therefore it potentially requires fewer MISs to cover all vertices in graph. Let S C $ denote the set of MISs that contain vertex V. and 02 denote the maximum size of MISs that contain vertex e: Oy ma, |S]. The ratio |S]/a, computes the relative 'payoff' of using the
feature designed to characterize S is fi (S) = |S1// ma |S').
set S cover vertex v, compared using the largest MIS in S. that can cover vertex v. The next four problem-specific features compute the maximum (f2), minimum (Js), average (f4) and standard deviation (f's of [ across the vertices in S. Let deg(r) be the degree of vertex v E V, i.e., the number of neighbours of and A be the maximum degree of vertices in V: A max.ev deg(v). The next four features designed to characterize are the maximum (fo), minimum (fr), average (fs) and standard deviation (fg) of the normalized degree (deg(u)/ A) across the vertices in S.
Statistical features. Let æ E {0, 13:61 be the binary string representation of a sample solution to the VCP, where a binary variable nş = 1 if and only if the corresponding MIS S is in the solution, for each S E S. We first use the method presented in Appendix A. efficiently generate sample and only
is the ,th sample solution. Let = =x y² ........ , be the objective values of the n solutions. The first statistical feature is an objective-based measure, which accumulates the 'payoff" of using S to construct solutions in terms of the objective values fobm (S) ='=rr'/v' Because the vertex coloring is minimization problem, a MIS that frequently appears in high-quality sample solutions is expected to have larger accumulated score. Let r frl, ,r",, ..... r") denote the ranking of the sample solutions in terms of their objective values. The next statistical feature used is the ranking-based measure originally proposed in (Sun et al. (2021b): frim (S) Σi= w/s/r.. If S frequently appears in high-quality sample solutions (with smaller rank). it is more likely to have a larger ranking-based score. The objective-basse score and ranking-basee based score are normalized by their maximum values across S. In addition, we compute the Pearson correlation coefficient and Spearman's 's rank correlation coefficient between the values of the binary decision variable 2g and the objective values y over the sample solutions. If æg is highly negatively correlated with y, means the sample solutions containing S generally have a smaller objective value than those not having S. We present an efficient method to compute these statsitical features in Appendix A.2
solutions {ar, ........ ,x"),, where æ's =
Linear programming features. The LP relaxation of MIP is typically much more efficient than the MIP itself to solve. Solving the LP relaxation can provide very useful information about the importance of a decision variable. Specifically, we solve the restricted master problem 4 (6) with the subset of MISs S using the Gurobi solver. The first LP feature extracted for a MIS S is its value in the optimal LP solution. The optimal LP solution value of 2g is a good indication of which binary value 2s takes in the optimal integer solution, information between the LP and integer solutions is noticeable. In general, if .ts has a fractional value closer to 1 in the optimal LP solution, it is more likely to be in the optimal integer solution to the sub-MIP. The next LP feature extracted for S E $ is the reduced cost (See Section 2 of the corresponding variable Is. When the restricted master problem is solved to optimality for S, the reduced cost of the decision variable 2s is non-negative for every 5 S. Furthermore, if the value of as in the optimal LP solution is greater than 0, the reduced cost of v3 must be 0. In general, the larger the reduced cost of yg the less cost-effective S is to construct solutions.
shown in Appendix B.2 that the mutual
The three categories of features are designed carefully, each capturing different characteristies of a MIS. The problem specific features focus on the local characteristics of a MIS such the number
4

---

Published as a conference paper at ICLR 2023
of vertices that a MIS can cover. Our statistical features are motivated by the observation that many optimization problems have a "backbone" " structure (Wu & Hao 2015). In other words, high high-quaiity solutions potentially share some components with the optimal solution. The goal of our statistical features is to extract the shared components from high-quality solutions. The L.P features are based on the LP theory, which is widely used by state-of-the-art MIP solvers. The relevance of each category of features is investigated in Appendix B.2nddxxBBBBde. due to the page limit.
3.2 CLASS LABELING
To construct a training set, we need compute the optimal solutions for set of problem instances for class labeling. We use small graphs in which all the MISs can be enumerated upfront as our training problem instances. For each training graph GVV,E) we first use the method proposed by (sukiyama et al. 1977) to list all MISs (S) in the graph. This method is based on vertex sequencing and backtracking, and has a time complexity of ([V] [S). An exact solver Gurobi then used to compute the optimal solutions for the problem instance by solving the MIP formulation ① (3. The existing optimal solution prediction approaches in literature typically compute only one optimal solution of optimization problem to supervise the training of an ML model (Li al.) 2018 Sun et al. b021b Ding et al. 2020; Sun et al. 202 However, this is insufficient in our case, because there often exist multiple optimal solutions in the VCP. For example, in some of the training graphs used in our experiments, more than 90% of MISs are part of optimal solutions, indicating the
existence of multiple optimal solutions. To tackle this, approach to compute for each MIS in a graph whether it belongs to any optimal solution. A MIS is assigned with class label of if it belongs any optimal solution; otherwise 0.
present in Appendix |A.3 brute-force
3.3 TRAINING AND TESTING
We use multiple graphs to construct a training set. The training graphs are small, so that all the MISs in the graphs can be enumerated easily (Tsukiyama et al. 1977 Csardi & Nepusz (006). Each MIS in a training graph is used as a training instance. The features and class label of a MIS are computed as above. After the training set is constructed, an to classify optimal and non-optimal MISs (i.e.. classifying whether a MIS belongs to an optimal so- lution or not). We will test multiple classification algorithms including K-Nearest Neighbor (KNN) Cover & Hart| 1967). Decision Tree (DT) (Breiman et al. Loh| 2011]. and Support Vector Machine (SVM) (Boser et al. 1992| Cortes& Vapnik] 1995) in our experiments. Given an unseen test prob- lem instance, if all the MISs in the corresponding graph can be enumerated upfront, our ML model can be used as problem reduction technique to prune the search space of the problem (Lauri & Dutta 2019 [un al. 2021b). However, the number of MISs in test graph may be exponentially large, and hence it is often impossible to enumerate all MISs upfront, especially for large graphs. To tackle this, we develop a search method in the next section generate subset of high-quality MISs (without the need of listing all MISs), guided by our ML model.
classification algorithm can be trained
GENERATING COLUMNS
This section describes our MLCG method. Our MLCG method starts with a randomly generated subset of columns (i.c., MISs) S. which contains at least one feasible solution. then goes through Ni number of iterations, and at each iteration it computes the features (designed in Section (3.1) for each MIS S E S. and uses the trained ML model to evaluate the quality of each MIS. The low- quality MISs in 5 predicted by ML are replaced by the newly generated ones. Finally, the MISs remain in the subset S are returned. In this sense, our MLCG method is significantly different from the traditional CG methods that typically generate columns by repeatedly solving a pricing problem.
Initializing a subset of MISs. The initial subset of MISs is generated randomly. To increase the diversity of S. we generate an equal number of MISs starting from each vertex v E V. This also ensures that S contains at least one feasible solution, since all vertices in V can be covered by S. To generate a MIS starting from vertex v, initialize the set S as and the candidate vertex set C as the set of vertices excluding v and e's neighbors. The set S is then randomly expanded to a MIS. In each step of expansion, we randomly select vertex v. from C and add v, into S. The candidate
5

---

Published as a conference paper at ICLR 2023
vertex set C' is then updated by removing v and vy's neighbors (due to the definition of independent set). This process is repeated until the candidate vertex set is empty.
Evaluating the quality of MISs. We use the ML model developed in Section 3 to evaluate the quality of the MISs in the subset S. To do this, we first extract the features designed in Section 3.1 for each MIS in S. Note that we do not need to enumerate all the MISs in a graph, because the features can be computed only based on the subset S. The ML model should be computationally efficient, as the time used in prediction should be counted as part of the total run time in solving the problem. Therefore, we only consider linear SVM and DT here, since KNN and non-linear SVM are slow in our case where the number of training instances is large. Let w be the vector of optimal weights learned by linear SVM. The quality score predicted by linear SVM for given MIS with feature vector f can be computed by (f) = Σ wy wifi. Generally, a MIS with a larger quality score is of better quality. For trained DT, leaf node as an indication of the quality of MISs belonging to that leaf node. The quality score of a MIS with a feature vector can be computed as pDr - nu (f)/(nn()
the proportion of positive training instances in
+ -n (f)), where ni (f) and no (f) are the number of positive and negative training instances in the leaf node that f belongs to. The score PDT is in the range of O and 1, with indicating the best quality predicted by DT.
Updating the MIS subset. We rank the MISs in S based on their quality scores predicted by the ML model. The top k percentage of MISs are kept and the remaining low-quality MISs are replaced by newly generated MISs. We investigate the following two different methods generate new MISs. The first method is a random approach. To replace a low-quality MIS S whose first vertex is v*, the random approach starts from the same vertex v² and randomly expands it to a MIS. The random approach has the merit of maintaining the diversity of the MIS subset S. but on the other hand it may require many iterations to generate high-quality MISs. The second method is a crossover approach inspired by the Genetic Algorithm (Golberg, 1989). which randomly selects two high-quality MISs to create new one. More specifically, it initializes the set S as the common vertices of the two high-quality MISs selected, and then randomly expands the set 5 to a MIS.
Generating an integer solution. With the subset of MISS obtained, we can use an existing opti- mization algorithm such as the Gurobi solver to construct a complete integer solution. To be specific, can form subproblem by using the subset of MISs generated by our MLCG method as inputs to the MIP formulation is significantly smaller than the original problem, and thus solving the subproblem is lot easier. In addition, the integer solution generated from the subproblem is likely to be of high-quality, which will be shown in our experiments. Directly solving the subproblem does not provide any optimal- ity guarantee. Alternatively, we can use the subset of MISs generated by our MLCG method to warm-start RMH. Specifically, we can use the MISs generated by our method as the initial subset of columns for the restricted master problem, and solve the LP relaxation of (T (3) using a tradi- tional CG approach (see Section 2). The optimal LP objective value provides a valid lower bound for the objective value of integer solutions. We then form subproblem with the columns generated by our MLCG method and the traditional CG method, and solve the subproblem using an existing algorithm. By doing this, we can obtain high-quality integer solution with a valid optimality gap. We will evaluate the efficacy of our MLPR method for seeding RMH in our experiments.
G.. and solve the subproblem using Gurobi. The size of the subproblem
EXPERIMENTS
This section presents the experimental results to show the efficacy of our MLCG method in generat- ing columns for the VCP. Our algorithms are implemented C++, and the source code is publicly available at hhttps: //gbbbbb. com/ yuansuny hmll://mcg.g../ qit. Our experiments are conducted on a high performance computing server with multiple CPUs @2.70GH. each with 4GB memory.
5.1 PREDICTION ACCURACY
We use the first 100 problem instances (g001-g100) from MATILDA (Smith-Miles & Bowly 2015) to construct a training set. These graphs are evolved using Genetic Algorithm to acquire controllable characteristics such density, algebraic connectivity, energy, and standard deviation of eigenvalues
of adjacency matrix. For each instance (V) = 100), we use the algorithm implemented in the
igraph library (Tsukiyama et al. 1977: Csardi & Nepusz 2006) to enumerate all MISs (S) in the

---

Published as a conference paper at ICLR 2023
corresponding graph. The Gurobi solver with the default parameter setting, 4 CPUs and 16GB memory is then used to compute the optimal solution value (i.e., class label) for each S E S. The constructed training set consists of 94, 553 positive (with class label 1) and 94, 093 negative (with a class label 0) training instances (i.e., MISs). The training set is reasonably balanced, indicating that there often exist multiple optimal solutions in the VCP. The distribution of the training instances in the 2D feature space created by PCA is presented in Appendix B.I
We test multiple classifiers for this classification task, including KNN (k: = 3), DT (depth - 20), linear SVM (C' = 1) and nonlinear SVM with the RBF kerne (C 1000). The implementations of KNN and DT are from the seikit-learn library (Pedregosa et al. 201T): the nonlinear SVM is from the LIBSVM library (Chang & Lin 2011); and the linear SVM is from the LIBLINEAR library (Fan et al. 2008). The parameters of these classification algorithms are tuned by hand. All the algorithms and datasets used are publicly available. We train each classification algorithm on the training set with fifteen features, and the ten-fold cross-validation accuracy of KNN, DT, linear SVM, and nonlinear SVM are 91%, 90%, 78% and 85%, respectively. The correlation between each feature and the class label, the feature weights learned by the linear SVM, and a trained simple DT presented and discussed in Appendix B.2
5.2 THE EFFICACY OF GENERATING MISS
Test instances. We use 33 problem instances from MATILDA (Smith-Miles & Bowly 2015) as our test instances, which cannot be optimally solved by Gurobi (with 4 CPUs) in 10 seconds. The number of vertices in those graphs are all 100. For each test instance, use our MLCG method to generate a subset of MISs, and use Gurobi to solve a sub-problem formed by the generated MISs. The quality of the best integer solution found in the sub-problem is an indication of the quality of the MISs generated by our MLCG method.
Parameter setting. The size of the MIS subset [$] is set to 2). where [V] is the number of vertices in graph. In general, a larger [š] leads to better integer solution, but at an expense of longer runtime. The number of iterations Nit is set to 10 for now, and will be tuned later. In each iteration of our MLCG method, 50% of MISs are replaced: ς = 50.
Linear SVM versus Decision Tree. We test two efficient classification algorithms, linear SVM and DT, for evaluating the quality of MISs. The average optimality gap generated by our MLCG method with linear SVM 2.49%, which significantly better than that with 7.95% (See BB.) This indicates that linear SVM is more effective than DT in evaluating the quality of MISs, which is somewhat surprising because the classification accuracy of DT is much higher than that of linear SVM. In the rest of our experiments, we will only use linear SVM to evaluate MISs.
Random update versus crossover update. We test two approaches (random and crossover) for generating new MISs replace low-quality MISs in each iteration of our algorithm. The two ap- proaches perform similarly, with the average optimality gap generated by the random approach 2.49% and that of the crossover approach 2.68% (See Appendix (B.4). The reason why the crossover approach is not more effective may be that the diversity of the generated MISs is important. In par- better
ticular, having more high-quality but similar MISs in the subset is not expected to result integer solution. In the rest of the paper, we simply use the random approach to generate new MISs.
Number of iterations. We vary the number of iterations (m2,) from 100, and record the optimal- ity gap generated by our MLCG method. The solution quality generated by our method improves dramatically in the first several iterations, and the improvement slows down later on. The smallest optimality gap is generated at around the 50th iteration, and cannot be further reduced afterwards (See Appendix B.5 for the detailed results). Hence, we set na. = 50 hereafter.
Baselines. We compare our MLCG method to four baselines for generating columns: /) Random, which randomly generates 10 MISs starting from each vertex in a graph, resulting in 10 V in total (the same number as our method | x 50%); 2) RC, which replaces linear SVM with a simple criterion of using the reduced cost to evaluate MISs; 3) MLF, which enumerates all MISs in a graph and uses linear SVM to seleet the top 10 MISs for each vertex, thus 10]V| in total; and 4) Full, which simply enumerates and uses all MISs in a graph. The MISs generated by each method are used to construct (sub-)problen) which is then solved by Gurobi with 4 CPUs and one-hour cutoff time.
7

---

Published as a conference paper at ICLR 2023
Table The experimental results generated by each algorithm for solving the test problem instances. The last row presents the p-value of the t-tests between the results generated by our MLCG method and each of the other methods. The ones with statistical significance (p-value < 0.05) are bold.
Graph
Density
Optimality Cap (%)
Runtime RC
MLCG
MLF
RC
Rand
Full
MLCG
MLF
Rand
Full
g134
0.34
10,00
11.20
10.00
22.40
10.00
137,04
81.27
122.99
130.11
3605.50
28.27
:144
0.37
10.00
13.20
10.40
12.40
0.00
5.10
6.74
6.12
1.53
20.92
g171
0.28
0,90
0.00
0.00
11,50
0.00
5.29
11.61
5.20
0.32
14.55
g173
9.70
g175
0.32
0.00
12.50
0.00
12.00
0.001
3.44
31.38
3.50
0.54
40.09
2214
0.26
0.90
0.00
0.00
12.00
0.00
4.38
15.12
4.24
0.18
26.15
2243
3611.80
2263
0:23
0.00
20.00
13.60
17.60
0.001
5.11
3.48
4.52
0.211
20.97
2324
0.38
0.90
0.00
0.00
5.00
0.00
6.52
17,90
4.63
0.62
25.08
g329
2348
0.21
0.00
0.00
0.00
10.29
0.00
4,99
9.80
4,80
0.16
17.17
g417
0.40
2,00
12.50
1,00
24,00
0.00
5.51
12.63
5.42
1,17
12.89
8420
0.00
107.48
g474
0.34
11.11
22.22
14.67
22.22
0.00
6.40
21.75
12.71
1.34
489.22
3479
0.23
0,00
0.00
0,00
6.67
0.00
4.78
18.48
4,81
0.65
34.95
g186
0.67
8487
041
0.90
0.00
0.00
8.92
0.00
20.84
13.14
13.26
31,06
864.33
g493
0.24
0.00
0.00
1.33
10.67
0.001
4,59
4,92
5.52
0.30
12.52
g996
8498
0.35
0.00
0.00
3.43
12.00
0.00
4.75
14.54
4.04
0.13
45.18
8508
0.53
0.00
0,00
0.89
0.00
0.00
3,98
9.66
5.65
0.14
10.19
2509
2511
0.50
0.00
0.00
0.00
0.00
0.00
4.57
10.51
4.54
0.17
15.31
g530
0.51
0.00
0,00
0.84
8.84
0.00
6.35
14,13
6.60
0.40
15.03
0.36
2753.70
2557
0.56
0.00
0.00
0.00
5.65
0.00
37,01
40.85
17.67
16.26
200.79
g597
0.46
0.00
0,00
0,00
7.14
0.00
115.78
61.61
38.31
96.75
814.56
36
g617
0.29
0.00
0.00
0.00
1.50
0.00
4.15
20.98
4.15
0.16
23.40
g876
0.43
1.71
14.29
13.71
14,29
0.00
5,33
4.48
4,77
0.34
22.78
2894
0.43
0.00
12.57
6.26
8.24
12.10
2913
0.44
0.00
0.00
7.43
14.29
0.00
4.38
7.45
6.25
0.18
29.17
Mean
1.87
5.25
3.64
10.54
0.91
22.60
21.45
15.62
15.19
417.02
1.22-00
7,29c-01
2.26e-02
Comparison results. The optimality gap (with respect to the lower bound produced by Full) of each algorithm for each test problem instance and the runtime of the algorithms are presented in MLCG method with
Table The results are averaged over 25 independent runs. Comparing Full (which is an exact approach), we can clearly see that MLCG consistently generates an optimal optrmal solution using much less runtime. On average, our MLCG method reduces 95% of the runtime of Full, and only increases the optimality gap from 0.91% to 1.87%. Notably on g243, the full problem cannot be solved to optimality by Gurobi in one-hour cutoff time. In contrast, using the columns generated by our MLCG method to construct a sub-problem, Gurobi able find better integer solution in only 33.63 seconds. Compared Random, our MLCG method consistently generates a better solution for the test problem instances except g496. The average optimality gap generated by our MLCG method about times better (smaller) than that of Random. Furthermore, our MLCG method significantly outperforms the RC method in terms of the optimality gap generated (with p-value- = 0.0.69). This clearly demonstrates that our MI model has learned more useful rule than the reduced cost for evaluating the quality of MISs. Surprisingly, the MLF method does not perform as well as the MLCG method in terms of the optimality gap. The reason for this is that the aim of CG is to select diverse set of high-quality MISs to cover each vertex at least once. The ML model can evaluate the quality MISs, but it cannot measure the diversity of MISs selected. In the MLF approach where all MISs are listed, multiple high-quality but similar MISs (i.e., sharing many common vertices) are likely to be selected. Although those selected MISs individually of high-quality, when combined loses diversity. Hence, the MLF method does not perform well compared to the MLCG method.
5.3 SEEDING RESTRICTED MASTER HEURISTIC
We use the columns generated by our MLCG method to warm-start RMH. namely MLRMH, com- pared to RMH with the typical random initialization. The number of initial MISs is set to V) The restricted master problem and the pricing problem are both solved by Gurobi. Apart from the 33 MATILDA problem instances used above, include 30 other MATILDA problem instances, in
8

---

Published as a conference paper at ICLR 2023
Table 2: The comparison between the MLRMH and RMH algorithms for solving the three sets of test problem instances. The results are averaged across the instances in each problem set.
Optimality Gap (%) RMH
CG Iterations
LP Runtime
Total Runtime
Graphs
MLRMII
MLRMH
RMH
MLRMI
RMH
MLRMI
RMH
MATILDA (33)
3.89
8,21
7.08
69.63
9.25
49.61
28.08
74.35
MATILDA (30)
8,96
12.53
59.38
156.28
37.39
74.77
58.30
84.99
DIMACS (12)
24.56
27.03
84.21
168.54
198.34
656.74
12439.00
12668.00
which the number of MISs is so large that they cannot be enumerated with 16GB memory. addi- tion, we evaluate the generalization of our method on set of larger DIMACS problem instances, in which the number of vertices vary from 125 to 1000.
The experimental results summarized in Table 2 and the detailed experimental settings and results are shown in Appendix B.6] Note that the optimal LP objective obtained is a valid lower bound (L.B) for the objective value of integer solutions, and is used to compute the optimality gap. The LB generated by MLRMH (or RMH) is very tight for most of the problem instances tested. Our MLRMH algorithm is able prove optimality for many of the problem instances and provide an optimality gap for the remainder, making it a quasi-exact method. The average optimality gap generated by MLRMH is significantly smaller than that of RMH. Interestingly, by using the columns generated by our MLCG method to warm-start RMH, the number of CG iterations is substantially reduced. This also leads to a significant reduction in the runtime of solving the LP. Note that the time used by our MLCG method to generate columns is counted as part of the LP solving time.
Our method is not confined to solving problem instances generated from similar distribution. In fact, the MATILDA graphs we used are evolved using Genetic Algorithm to acquire various characteristics such as density, algebraic connectivity, energy, and standard deviation of eigenvalues of adjacency matrix etc (Smith-Miles & Bowly 2015), and the DIMACS graphs are a collection of hard problem instances from multiple resources with very different problem characteristics and sizes. Our experimental results showed that our method trained subset of MATILDA graphs performs well across the MATILDA and DIMACS graphs.
6 CONCLUSION
In this paper, we have developed an effective CG method based on ML for the VCP. We defined a column as a Maximal Independent Set whose vertices can share the same color a feasible solution, and developed an ML model to predict which column belongs to an optimal solution. Novel features were designed to characterize a column, including those computed from the graph data, sample solutions and the LP relaxation. We then used the ML model to evaluate the quality of columns, and incorporated into a search method to generate subset of high-quality columns without the need of enumerating all columns in problem instance. We empirically showed that our ML model achieved a high accuracy in predicting which columms are optimal on the datasets considered. Furthermore, showed that the columns generated by our method were significantly better than those generated randomly or via the reduced cost. Finally, we showed that the columns generated by our method can warm start.
be used to boost the performance of a CG-based heuristic
Our proposed MLCG method is generic. Although we have only demonstrated the efficacy of this approach on the VCP, the same idea can be applied to other combinatorial optimization problems. Taking the vehicle routing problem as an example, in which a column is a resource constrained shortest path, an ML model can be built to predict which path is likely to be part of the optimal solution. This will require the design of problem specific features to characterize a path and a specialized sampling method to efficiently generate paths. Our paper has focussed on using CG as part of a heuristic approach, where only restricted master problem is solved to obtain final integer solution, as is commonly found in many papers applying CG to large scale problems. However, the same approach could easily be applied in the context of exact B&P method, where CG would be done predominantly using the ML approach with reduced-cost based pricing of columns only completed at the end to prove optimality of the LP at each node. Our results are indicative that such an ML boosted approach may be expected to have a positive impact on the performance of a B&P approach well. However a rigorous investigation of this is beyond the scope of the current paper.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work was supported by an ARC Discovery Grant (DP180101170) from Australian Research Council.
REFERENCES
Babak Abbasi, Toktam Babaci, Zahra Hosseinifard, Kate Smith-Miles, and Maryam Dehghani. Pre- dicting solutions of large-scale optimization problems via machine learning: A case study in blood supply chain management. Computers Operations Research, pp. 104941, 2020.
Ali Mehsin Alyasiry, Michael Forbes, and Michael Bulmer. An exact algorithm for the pickup and delivery problem with time windows and last-in-first-out loading. Transportation Science, 53(6); 1695-1705, 2019.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International Conference Machine Learning, pp. 344-35333 PMLR, 2018.
Cynthia Barnhart, Ellis L Johnson, George L Nemhauser, Martin WP Savelsbergh, and Pamela H Vance. Branch-and franch-and-price -nd-price: Column generation for solving huge integer programs. Operations Research. 46(3):316-329) 1-99,, 1998.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d' d'horizon. European Journal of Operational Research, 2020.
Nicola Bianchessi, Renata Mansini, and Maria Grazia Speranza. The distance constrained multiple vehicle traveling purchaser problem. European Journal of Operational Research, 235(1):73-87, 2014.
Bernhard Boser, Isabelle M Guyon, and Vladimir N Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pp. 152. ACM, 1992.
Breiman, Friedman, Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1277, 2011.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20(3):273-297, 1995.
Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE Transactions Infor- mation Theory, 13(1):21-27, 1967.
Gabor Csardi and Tamas Nepusz. The igraph software package for complex network research. InterJournal Complex Systems, 1695(5):1-9, 2006.
Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Proceedings of the 3 International Conference Neural Information Processing Systems, pp. 6351-6361, 2017.
Jian- Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang, Yinghui Xu, and Le Song. Acceler- ating primal solution findings for mixed integer programs based on solution prediction. In AAAI, pp. 1452-1459, 2020.
Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. LIBLINEAR. A library for large linear classification. The Journal of Machine Learning Research, 9:1871-1874, 2008.
Martina Fischetti and Marco Fraccaro. Machine learning meets mathematical optimization predict the optimal production of offshore wind parks. Computers & Operations Research, 106:289-299 2019.
10

---

Published as a conference paper at ICLR 2023
Nikolaus Furian, Michael O'Sullivan, Cameron Walker, and Eranda Çela. A machine learning-basd based branch and price algorithm for a sampled vehicle routing problem. OR Spectrum, pp. 1-40, 2021.
David E Golberg. Genetic algorithms in search, optimization, and machine learning. Addion Wesley, 198)(10)):36, 1989.
Marco Grassia, Juho Lauri, Sourav Dutta, and Deepak Ajwani. Learning multi-stage sparsification for maximum clique enumeration. arXiv preprint arXiv:1990.0055 2019.
Stefano Gualandi and Federico Malucelli. Exact solution of graph coloring problems via constraint programming and column generation. INFORMS Journal Computing, 24(1):81-100, 2012.
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, 2020.
Xiaotian Hao, Junqi Jin, Jianye Hao, Jin Li, Weixun Wang, Yi Ma, Zhenzhe Zheng, Han Li, Jian Xu, and Kun Gai. Learning to accelerate heuristic searching for large-scale maximum weighted b-matching problems in online advertising. In ICCA1-20, pp. 3437-3443 7 2020.
Elias B Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In AAA/ Conference on Artificial Intelligence 2016, pp- 724-731. Association for the Advancement of Artificial Intelligence (AAAI), 2016.
Juho Lauri and Sourav Dutta. sone-grained search space classification for hard enumeration variants of subset problems. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 2314-2321,, 2019.
Juho Lauri, Sourav Dutta, Marco Grassia, and Deepak Ajwani. Learning fine-grained search space pruning and heuristics for combinatorial optimization. arXiv preprint arXiv:2001.0122 00.:20000,/220, 2020.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optpiatiaiiloooimiiiiiiiiiiin with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp. 539-548, 2018.
Wei-Yin Loh. Classification and regression trees. Wiley Interdisciplinary Reviews: Data Mining and Knowledge discovery, 1(1):14-23, 2011.
Marco E Lübbecke and Jacques Desrosiers. Selected topics in column generation. Operations Research, (3(6):0007-100 2005.
Anuj Mehrotra and Michael A Trick. A column generation approach for graph coloring. Informs Journal on Computing, 8(4):344-354, 1996.
M. Morabit, G. Desaulniers, and A. Lodi. -eaiii----arning---e- based Column Selection for Column Generation. Les Cahiers du GERAD. GERAD, HEC Montréal, 2020. URL httts:://pssokttt
goog e. com. au hauuboooks' d= __G ZQEACAAJ
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Shuichi Sakai, Mitsunori Togasaki, and Koichi Yamazaki. A note on greedy algorithms for the maximum weighted independent set problem. Discrete Applied Mathematics, 126(2-3):313322,, 2003.
Yunzhuang Shen, Yuan Sun, Xiaodong Li, Andrew S. Eberhard, and Andreas T. Ernst. Enhancing column generation by a machine-learning based pricing heuristic for graph coloring. In Proceed- ings of the Sixthh AAAI Conference on Artificial Intelligence (to appear), 2022.
Kate Smith-Miles and Simon Bowly. Generating new test instances by evolving in instance space. Computers & Operations Research, 63:102- 2015.
11

---

Published as a conference paper at ICLR 2023
Yuan Sun, Andreas Ernst, Xiaodong Li, and Jake Weiner. Generalization of machine learning for problem reduction: A case study on travelling salesman problems. OR Spectrum, 43:607-633, 2021a.
Yuan Sun, Xiaodong Li, and Andreas Ernst. Using statistical measures and machine learning for graph reduction to solve maximum weight clique problems. JEEE Transactions on Pattern Anal- ysis and Machine Intelligence, 43(5):1746-17600 2021b. doi: 10. 1000/TTA...221..995555555
Yuan Sun, Sheng Wang. Yunzhuang Shen, Xiaodong Li, Andreas T Ernst, and Michael Kirley. Boosting ant colony optimization via solution prediction and machine learning. Computers & Operations Research, 143:105769, 2022.
Éric D Taillard. A heuristic column generation method for the heterogeneous fleet vrp. RAIRO- Operations Research-Recherche Opérationnelle, 33(1):1-14, 1999.
Robert Endre Tarjan and Anthony E Trojanowski. Finding a maximum independent set. SIAM
Journal on Computing, 6(3):537-546, 1977.
Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. new algorithm for generating all the maximal independent sets. SIAM Journal on Computing, 6(3):505-517, 1977.
Roman Václavík, Antonín Novák, Piemysl Súcha, and Zdenčk Hanzälck. Accelerating the branch- and-price al algorithm using machine learning. European Journal of Operational Research, 271 1055-1069, 2018. ISSN 0377-2217.
Qinghua Wu and Jin-Kao Hao. review on algorithms for maximum clique problems. European Journal of Operational Research, 242(3):693-709, 2015.
Wenjie Zhang, Zeyu Sun, Qihao Zhu, Ge Li, Shaowei Cai, Yingfei Xiong, and Lu Zhang. Nlocalsat: Boosting local search with solution prediction. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 1177-1183, 2020.
12

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 AN EFFICIENT RANDOM SAMPLING METHOD
We describe an efficient random sampling method to generate sample solutions the VCP in Al- gorithm A.1 The inputs to the algorithm the graph C(V, E) and the of MISs S, containing vertex v, for each U E V. The output is set of MISs selected which can cover all the vertices in V least once (i.e., a feasible solution denoted 3g). The random sampling method starts by initializing the solution S as empty and marking each vertex E V as not covered. It then iterates through each vertex E V. and if has not been covered, it randomly selects MIS S from S and adds the solution S. The vertices S are then marked as covered. feasible solution S. obtained when all vertices in V have been covered.
Algorithm A.1 Random Sampling
Input: graph GVV, E). MISs sets 3, for each v E V. Output: sample solution S..
Initialize 2 < ()-
Initialize covered(v] < for each V. for each E V do
covered|u] then
randomly select MIS from S...
add S into S.. for each ū E S do covered(ū +-1 1.
Lemma A.1. Given a graph G(V, E), the time complexity of generating a sample solution to the VCP using Algorithm A.I is O(V)) in the best case, and O(x(V)) in the worst case, where max (S) the maximum size of the MISs in S.
Proof. In the best case, the MISs selected do not share any common vertex. In other words, each vertex in the graph is covered exactly once. In this case. the number of basic operations (c.g., comparison and assignment) performed in Algorithm A. is about 3/V), which is in ((V))- In contrast, the MISs selected may share many common vertices and each vertex in the graph may be covered multiple times. In the worst case, each MIS selected in Algorithm A. can only cover one new vertex that has not been covered (with other vertices in the MIS already being covered). In this case, the number of assignments performed in the inner loop of Algorithm where |Sy| is the size of the hth selected MIS. a denotes the maximum size of the MISs in S,
A.1 is Σ 1i=1 [S,].
have |S&| < a and Σ IV] S|| < alV] Hence the worst case time complexity of Algorithm A. is (a)(V)).
We run Algorithm A.1 n times to generate sample solutions {S] 82 randomly permute the vertex set to increase the diversity the generated solutions. The sample size n should be large enough so that each MIS in S is expected to be sampled at least once. In our experiments, we set n
Sh). In each run,
A.2 AN EFFICIENT METHOD FOR COMPUTING STATISTICAL FEATURES
We first describe the statistical features in more detail. Let x E {0, |ق1 be the binary string repre- sentation of a sample solution, where a binary variable Vg = 1 and only if the corresponding MIS S is in the solution, for each S E S. The n sample solutions can be denoted as {x' x² xx where x'S
if and only if is in the ith sample solution. Let y {x y .... y²) be the objective values of the n solutions. The first statistical feature is an objective-basee measure, which accumulates the 'payoff" of using S to construct solutions in terms of the objective values:
faba (S)=
Σe
/
(10)
i=
13

---

Published as a conference paper at ICLR 2023
Because the vertex coloring is minimization problem. MIS that frequently appears in high- quality sample solutions (with smaller objective values) is expected to have a larger accumulated score, As the scale of the objective-based score is sensitive to the scale of objective values and sample size, we normalize the objective-based scores by the maximum objective-based score in S: f10(S) = fobm(() max E' (S')
Let r = {(r, ,?,................ ) denote the ranking of the n sample solutions in terms of their objective values. The next statistical feature used is the ranking- -baed measure originally proposed by (Sun ct al. 2021bb:
frbm (S) = a'g/r'.
(11)
If S frequently appears in high-quality sample solutions (with a smaller rank), it is more likely to have a larger ranking-basee based score. The ranking-basee score is normalized by the maximum ranking- based score in S: fu (S) frbm (S)/ max (S").
S'E8
The Pearson correlation coefficient between the values of the binary decision variable zy and the objective values y over the sample solutions can also be used quantify the expected benefits of using S to construct solutions:
Las Is) D) f12(8) VEin =z)² 1 7)2
(12)
where Ø. = Ei= l's/n and =E= 5/ n.. If as is highly negatively correlated with y, it means the sample solutions containing S generally have a smaller objective value than those not having S. Thus, using S to construct solutions is expected to result in a smaller objective value.
The last statistical measure computes the Pearson correlation coefficient between the values of the (r):
binary decision variable v and the ranking of the sample solutions
(a (z) F)
fia(S) = VE kS)
(13)
where Fgg = =E sss/n and F F= EE= /n. This ranking-based correlation score is equivalent to Spearman's 's rank correlation coefficient between ay and y. as the value of a's can be interpreted as its rank (considering tied ranks). A MIS with high negative ranking- -aaed correlation score is more likely to appear in high-quality sample solutions.
Computing the statistical features based the binary string representation of sample solutions (æ) can be achieved in (n This is computationally slow when the number of samples (n) and the number MISs ([S) are large. Based the fact that is a vector of binary variables, introduce an efficient method to compute the statistical features in the following.
Lemma A.2 (uSun& et al. 2021b ) For a binary variable r's. the following equality holds:
O'S = Σ (x's - -gg)² = nāg - -.
(14)
where is = EI I/s/n
Proof. Here, we provide a different proof to the Lemma than (Sun et al., (021b).
ss's T3)
((ab)) 2
(xr))² nxz
(15)
As a'y is a binary variable, Σ (xt))² Σm x3s = nnT.. Hence
0 nIs nn²s nā Is).
(16)
n
14

---

Published as a conference paper at ICLR 2023
Algorithm A.2 Computing Statistical Features
Input:
sample solutions (S).... " objective values {y',... yy", rankings (r',...."")
MIS subset S.
Output: statistical features fobm (S), from (S), fi2(S) and fia(S), for each S e S. Initialize fobm
0, (S) t 0, for each S E S.
Initialize ēy +- O, g 0, o 0, for each 5 S.
Compute the mean objective value: y Σ 1 y2 /n.
Compute the mean objective ranking: F < (1 12/2.
for i 1 to do for each ε S do
fobm (S) t fobm +5)+
frbm 5) t frbm (S) + 1/r".
ig 3s 1 1/n.
2y t g
ry + (y' 8).
0 + og + (r' (r²- -)). F).
Compute the objective variance: By + 2i (1² -g)2
Compute the ranking variance: o, + n(n + 1) - -1)122
for each S E $ do
T f [1 I5)m. fi2(5) - o5 Vo
fia(S) - d Vo
Lemma A.3. For a binary variable r'g and any variable y", the following equality holds:
ayy 0g
D(a's =z)( -ÿ)
Σ (2² -)--)). D).
(17)
iEfL." m//ag/-
where is = Ei / and y Ei= v¹ /n.
Proof. By making use of the fact that Σi= (1) 0, we have
n
0g
Σ
- Ø) = ( -
x's('' - ( - Es v 1) Σ
r's(y' -7). (18)
1=1
Y=1
As r'g is a binary variable,
29 0s"
Σ
1- - 0)+ +
Σ
0.'''
Σ (y¹ (3'- 7). (19)
1
(E(I...m)Ass 0
iE(1," =
Lemma A.3 holds for any variable y¹. By replacing y² with rf in Lemma A.3
the convariance
between the values of xg and the ranking of objective values r can be computed as
D Is) -F)
Σ
r).
(20)
(E(1, a m²
Furthermore, the ranking of the objective values from n, is difficult show that F Σn r² (n + 1)/2 and a, (r" 7)² n(n + 1)(n - 1)/12.
With this simplification, the statistical features can be computed efficiently using the repre- sentation of sample solutions (S) [S).... ... S.). The idea is to iterate through each S in the sample solutions S (where 1, 2, ... n)) and accumulate (S), (S), Øs. 0² and oz. The
two correlation-hased features can then be easily computed, as shown in Algorithm A.2 The time complexity of computing the statistical features using Algorithm A.2 is O([S) + Σ [ (), which much smaller than (n ()), because SS is much smaller than general.
15

---

Published as a conference paper at ICLR 2023
Algorithm A.3 Computing Optimal Solutions for Labeling
Input: graph G(V, E), the full set of MISs S. Output: optimal solution value vig for each S E S. "",y" Gurobi(G,s) for each S E do
if' I's 0 then
x. 0 < Gurobi
+ 1).
if 1 = y" then
for each S E S do
if i. then
S f-1 1.
A.3 COMPUTING CLASS LABELS
We present in Algorithm A.3 a "brute-force" approach to compute for each MIS in a graph whether it belongs to any optimal solution. The algorithm starts by solving given problem instance to optimality using the exact solver Gurobi, with an optimal solution x" and the optimal objective value y" obtained. The algorithm then iterates through each S S. If S does not belong any optimal solution found so far, Is is fixed to 1, and the corresponding subproblem is solved by Gurobi. If the best objective value found (ÿ) is equal y" it means that there exists least one alternative optimal solution that includes S; hence all the MISs used in the newly generated optimal solution (denoted as ))) are then marked as optimal.
This approach may not be the most efficient method to compute the class label for the MISs in a graph. There might exist better ways to compute all optimal solutions of problem instance, e.g., after optimal solution is found, cut can be generated to prune the optimal solution from the search space, so that a different optimal solution is generated one at a time until all have been enumerated. However, as training is conducted offline, Algorithm A.3 is sufficient to construct training set.
B SUPPLEMENTARY EXPERIMENTS
B. VISUALIZING TRAINING SET
To visualize the distribution of the training instances (i.e., MIS), we create a 2-D feature space via principal component analysis in Figure B.1 We can observe that the positive and negative training instances are separated to some extent. Most of the negative training instances are located in the left region, while the positive training instances are mainly in the middle of the reduced feature space.
B.2 FEATURE IMPORTANCE
To investigate the relevance of the features, we compute the Pearson correlation coefficient between each feature and the class label, which is shown Table B.I The reduced cost (f1s) has the highest correlation with the class label, indicating it is one of the most important features. The size of a MIS (f1) and the maximum, minimum and average relative sizes of a MIS (f2 fa) have noticeable correlation with the class label. As expected, the objective-basse based measure (f10) and the ranking- based measure (f11) are positively correlated with the class label, whilst the two correlation-based measures (J12 and fia) are negatively correlated with the class label.
We also compute the mutual information between each feature and the class label to capture any non-linear relationships between them. Since mutual information can be only computed for discrete variables. we discretize the values of each feature into five bins. The mutual information is normal- ized by the minimum entropy of the corresponding feature and the class label, that it is in the range of and 1. The LP features (f14 and fis) have the highest nonlinear correlation with the class label, shown in Table B.I
In addition, we present in Table B.I the optimal weights (w) of the features learned by the linear SVM classifier, which can be directly used evaluate the quality of MISs.
16

---

Published as a conference paper at ICLR 2023
negative positive
1.-
0.
N
0.0
-0.-
-1.0
-0.5
0.0
0.5
Figure B.I:
The distribution of training instances in the reduced feature space, where 21 and Ze are the first two principal components of the feature vectors. Each dot represents a training instance.
Table B.1: The Pearson correlation coefficient (PCC) and normalized mutual information (NMI)
between each feature and the class label, and the weight learned by linear SVM for each feature.
Feature
Name
PCC
NMI
weight
fi f2
size
0.2402
0.0389
-0.0169
max relative size
0.2417
0.0441
1.1620
fa f4
min relative size
0.2524
0.0450
-0.9010
ave relative size
0.2726
0.0470
0.2562
fs
std relative size
0.0494
0.0011
-2.7004
fe
max degree
0.0249
0.0135
-2.2259
f7
min degree
0.1372
0.0058
2.7940
fz
ave degree
0.0915
0.0084
0..505
fg
std degree
-0.1369
0.0361
2.9416
f10
obj-based measure
0.1225
0.0236
1.6858
f11
rank-based measure
0.1167
0.0209
0.4886
f12
obj correlation
-0.0915
0.0084
-.7993
f13
rank correlation
-0.0895
0.0082
1.0901
f14
LP solution value
0.1086
0.0934
0.9035
fis
reduced cost
-0.5676
0.2603
-2.1902
Finally, we investigate the trained Decision Tree (DT) to identify which features are important. When the depth of tree is set to 5, DT achieves accuracy of 80% with all features used except the min relative size (fz), obj correlation (f12) and rank correlation (fis). When the depth of tree is set to 3, DT achieves accuracy of 78% with three features used: reduced cost (f1s). max degree (fe) and min degree (fr). Hence, the reduced cost (fis), max degree (fa) and min degree (fr) are the most important features identified by DT. The trained DT with depth 3 is presented in Figure B.2
17

---

Published as a conference paper at ICLR 2023
reduced cost S
min degree I 0.238
reduced cost v 0.751
max degree & 0.974
reduced cost x 0.104
reduced cost 0.75
reduced cost s 0.778
negative
positive
positive
negative
negative
positive
negative
negative
The trained decision tree (with depth = 3) for predicting which MISs belonging to the optimal solutions.
Figure B.2:
Table B.2: The experimental results of our MLCG method when using different classifiers to eval- uate the quality of columns on the test problem instances. The results averaged across 25 inde- pendent runs. The last row presents the p-value of the I-tests between the results generated by linear SVM (with C 1) and DT with different depths. The ones with statistical significance (p-value 0.05) are highlighted in bold.
Graph
Optimality Gap (%)
Runtime
SVM
DT (d=3)
DT (d=10)
(d=15)
DT (d=20)
SVM
(d=5)
(d=13)
g134
10.00
10.00
45.60
20.00
20.00
661.32
744.72
1.49
34,24
34.69
g135
5.00
8.33
25.67
16.33
16.33
93.39
7.65
1.73
28.08
11.74
g144
10.00
10.00
11.20
10.00
10.40
1.48
1.79
1.92
2,36
2.17
g171
0.00
0.00
16.00
10.50
7.00
1.07
1.07
1.27
1.48
1.27
0.00
10.50
7.00
12.50
1.66
g175
0.00
0.50
1.00
9.50
6.50
1.32
1.66
1.68
1.36
1.27
g243
10.00
10.40
20.00
20.00
20.00
41.83
33,00
29.30
37.69
42,36
g263
0.80
1.60
0.00
14.40
16.00
1.15
1.10
1.03
1.02
0.94
g324
0.00
2.50
20.50
12.00
4.50
1.48
1.13
1.17
1.28
2.36
g329
0.00
0.00
3.20
0.98
1.12
1.15
1.53
g348
0.00
0.00
0.00
0.00
0.57
0.94
1.08
1.04
0.89
1.08
g417
11.00
9.50
12.00
12.50
12.50
1.57
1.29
1.81
1.47
2.11
g420
0.00
0.00
4.57
0.00
0.00
1.07
1.12
0.95
p474
11.11
11.56
11.56
20.00
21.33
1.81
3.73
4.71
1.76
2.33
g479
0.00
0.00
0.67
g486
0.00
3.24
8.38
4,76
4.76
15.45
13.12
1.37
2.52
3.72
p487
19.69
9.95
g493
0.00
35.33
14,67
10.67
14.00
1.42
0.92
1.09
1,31
1.10
g496
8.00
0.00
0.57
0.00
4.00
0.99
0.96
1.11
1.12
1.15
g498
0.00
0.00
0.00
4.57
4.57
0.90
0.85
0.97
0.85
0.90
g508
0.00
10.67
8.00
2.22
0.00
1.14
1.42
0.89
0.82
0.88
g509
9.78
17.33
23.11
17.78
13.33
1.12
1.04
1.08
g511
0.00
12.89
12.00
10.22
0.89
0.87
0.90
0.90
0.81
0.93
g556
0.00
3,03
9.09
7.64
9.09
350,30
325.36
9.36
43,85
46.08
g557
0.00
3.06
26.26
17.71
g597
0.00
0.00
18.00
6.43
7.14
86,31
53.01
1.62
112.95
46.83
g598
0.29
0.60
15.14
7.14
8.00
133.16
90.77
1.79
8.09
8.74
g617
0.00
0.00
0.50
0.50
0.00
0.98
0.84
0.98
0.92
0.97
g876
5.14
25.71
17.14
14.29
14.86
1.32
1.08
1.08
1.21
1.13
0.00
1.14
0.00
1.06
1.12
1.12
1.52
g913
1.14
20.57
14.29
14,29
8.00
1.13
0.88
1.10
0.90
1.48
Mean
2.49
6.24
10.49
8.41
7.95
44.47
40.44
2.99
9.53
7.48
P-yalue
1,28c-02
1.22c-05
3.01c-07
2.31c-07
3.31c-01
7.30e
1.0c-001
8.73c-02
B.3 COMPARISON BETWEEN DIFFERENT CLASSIFIERS
We test two efficient classification algorithms, linear SVM and DT, for evaluating the quality of MISs, and the results are presented in Table B.2 The optimality gap is computed based on the lower
18

---

Published as a conference paper at ICLR 2023
Table B.3: The experimental results of MLCG method when using different methods generate columns on the test problem instances. The results are averaged across 25 independent runs. The last row presents the p-value of the t-tests between the results generated by the two methods.
Optimality Gap (%)
Runtime
Graph
Random
Crossover
Random
Crossover
g134
10.00
10.00
661.32
268.08
g135
5.00
4.00
93.39
105.96
g144
10.00
10.00
1.48
1.57
g171
0.00
0,00
1.07
1.28
g173
0.00
0.00
1.21
1.33
g
0.00
0.00
1.32
1.16
g214
0.00
0.00
0.89
0.83
g243
10.00
10.00
41.83
28.37
g263
0.80
5.60
1.15
1.08
g324
0.00
0.00
1.48
1.18
g329
0.00
0.00
0,98
1.00
g348
0.00
3.43
0,94
0.95
g417
11.00
10,00
1.57
1.35
g420
0.00
0.00
1.07
1.06
g474
11.11
11.11
1.81
3.84
g479
0.00
0.00
1.08
1.03
g486
0.00
0.00
15.45
17.66
g487
0.00
0.00
30.89
36.33
g493
0.00
0.00
1.42
1.21
g496
8.00
5.14
0.99
0.81
g498
0.00
2.29
0,90
0.73
g508
0.00
0,44
1.14
0.82
g5509
9.78
11.11
1.12
0.90
g511
0.00
0.89
0.87
0.85
g530
0.00
0.00
1.53
1.71
g556
0.00
0.00
350.30
294.19
g557
0.00
0.00
26.26
28.94
g597
0.00
0.00
86.31
80.82
g598
0.29
0.29
133.16
141.79
g617
0.00
0.00
0.98
0.90
g876
5.14
3.43
1.32
1.11
g894
0.00
0.00
1.06
0.92
g913
1.14
0.57
1.13
0.92
Mean
2.49
2.68
44.47
31.23
P-value
4.29c-01
2.79c-01
bound generated by Gurobi with 4 CPUs and a one-hour cutoff time. We can clearly see that our method using linear SVM generates significantly better (smaller) optimality gap than that using DT, indicating linear SVM is more effective than DT in evaluating the quality of MISs. This is somewhat surprising, because the classification accuracy of DT much higher than that of linear SVM. Further, DT with a larger depth (d) may perform even worse in evaluating the quality of MISs, although the classification accuracy improves. This indicates that DT with a large depth may be overfitted. The other reason for this may be that the decision function used may not the most appropriate criterion to evaluate the quality MISs. For example, in a large decision tree, many leaf nodes have score of and DT cannot distinguish the MISs in those nodes, resulting in a poor performance. This issue can possibly be resolved by using a different criterion to evaluate the quality of MISs, such as using the "distance" from the feature vector of MIS to the decision boundary of DT. However, as our aim is not to compare which classification algorithm performs the best in this task, a further investigation along this line beyond scope of this paper.
B.4 COMPARISON BETWEEN RANDOM AND CROSSOVER UPDATE
We test two approaches (random and crossover) for generating new MISs to replace low-quality MISs in each iteration of MI.G method. The experimental results the test problem in-
19

---

Published as a conference paper at ICLR 2023
Optimality Gap (%)
10
20
30
40
50
60
70
80
90
100
Number of Iterations (nax)
Figure B.3: The optimality gap (%) generated by our MLCG method at different iterations (nz)-
The results averaged over 25 independent runs and 33 MATILDA test problem instances.
stances are presented in Table B.3 The two approaches perform equally well (without statistically significant difference). with the average optimality gap generated by the random approach 2.49% and that of the crossover approach 2.68%. The reason why the crossover approach is more effective may be that the diversity of the generated MISs is important. In particular, having more high-quality but similar MISs in the subset not expected to result better integer solution. In the rest of the paper, we simply use the random approach to generate new MISs.
B.5 EFFECTS OF NUMBER OF ITERATIONS
We investigate the effect of the number of iterations (Mi) the performance of our MLCG method. To do so, we vary the number of iterations from to 100, and present the average optimality gap generated by our method in Figure B.3 We can observe that the solution quality generated by our method improves (i.e., optimality gap decreases) dramatically in the first several iterations, and the improvement slows down later on. The best (smallest) optimality gap is generated at around the 50th iteration, and the solution quality cannot be further improved afterwards. Note that the result presented in Figure B.3 is the best optimality gap generated at each iteration, instead of the best optimality gap found so far. Therefore, the curve in Figure B.3 does not monotonically decrease due randomness. The detailed results for each test problem instance are presented Table B.4
B.6 DETAILED EXPERIMENTS FOR SEEDING RESTRICTED MASTER HEURISTIC
We use the columns generated by our MLCG method to warm-start RMH, namely MLRMH, com- pared to RMH with the typical random initialization. The number of initial MISs is set 10 The restricted master problem and the pricing problem are both solved by Gurobi. The detailed experimental results for the 33 MATILDA that the optimal LP objective is a valid lower bound (LB) for the objective value of integer solutions, and is used to compute the optimality gap Table B.5 We can observe that the LB generated by MLRMH is very tight for most of the problem instances tested. Significantly. our MLRMH algo- rithm able to prove optimality for many of the problem instances and provide an optimality gap for the remainder, making it a quasi-exact method. MLRMH consistently generates an equally or significantly better solution than RMH for the test problem instances except g496. The mean optimality gap generated by MLRMH is much smaller than that of RMH. Interestingly, by using the columns generated by our MLCG method to warm-start RMH, the number CG iterations is significantly reduced from 69.63 to 7.08 average. This also leads to significant reduction in the runtime of solving the LP and MIP. Note that the time used by our MLCG method to generate columns is counted part of the I.P solving time.
problem instances are presented in Table B.5 Note
20

---

Published as a conference paper at ICLR 2023
Table B.4: The average optimality gap (%) generated by our MLCG method different iterations on the test problem instances. The optimality gap is averaged over 25 independent runs. The last row presents the p- p-value of the t-tests between the results generated the first iteration and each of the other iterations. The ones with statistical significance (p-value < 0.05) are highlighted in bold.
Graph
lier
Ier 10
Ier 20
Iter 30
Iter 40
Iter 50
Iter 60
Ber 70
lter
lter 90
Iter 100
g134
22.40
10.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
g135
13:00
5.00
1.33
0.00
0.00
0.67
0.33
0.33
1.00
0.67
1.00
g144
12.40
10.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
g!71
0.00
0.00
0.00
0.00
0.00
g173
12.50
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
g175
12.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
g214
12.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
g243
20.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
10.00
g263
17.60
0.80
0.00
0.00
0,00
0.00
0.00
0.00
0.00
0.00
0.00
8324
5.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0,00
0.00
g329
6.40
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
8348
10.29
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
g417
24.00
11.00
8.00
7.00
5.50
2,00
3.00
2.50
2.00
4,00
3.50
8420
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
22.22
11.11
11.11
11.11
11.11
8479
6.67
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0,00
0,00
8486
4.76
0.19
0.00
0.19
0.00
0.19
8487
8.92
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
8493
0.00
0.00
0.00
0.00
0.00
8496
3.43
8.00
6.29
8.00
6.29
7.43
5.71
11.43
6.29
9.14
6.29
8498
12.00
0.00
0.00
0.00
0.00
0.00
0.57
0.00
1.14
0.00
0.00
g508
0.00
0.00
0.00
0.00
0,00
0,00
0.00
0,00
0.00
0.00
0.00
8509
10.67
9.78
10.67
10.22
10.67
844
10.22
9.33
9.78
9.33
10.67
g511
0.00
0.00
0.00
0.00
0,00
0.00
0.00
0.00
0.00
0.00
0.00
8530
8.84
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
R556
14.55
0.00
0.00
0.00
0.00
0.00
0.00
0,00
0.00
0.00
0.00
8557
5.65
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
g597
0.00
0.00
0.00
g598
14,00
0.29
0.00
0.00
0.29
0.00
0.00
0.00
0.00
0.00
0.00
g617
0.00
0.00
0.00
0.00
g876
14.29
5.14
2.29
0.57
1.14
1.71
0.00
1.14
2.29
0.00
2.29
g894
9.14
0.00
0.00
0.00
0.00
0.00
0.00
0.00
g913
14.29
1,14
0.00
0.00
0,00
0.00
0.00
1.71
0.00
0.00
0.00
Mean
10.54
2.49
2,11
2.03
1.97
1.87
1.85
2.05
1.93
1.95
1.97
P-value
2.59e-10
2.12e-10
4.42e-10
3.0dc-10
5.14c-10
3.65e-10
2.51c-09
4.68e-10
8.27e-10
4.26e-10
So far, we have only used the 33 MATILDA problem instances from (Smith-Miles & Bowly 2015)
as our test problem instances. The MISs in those graphs can be enumerated using 16GB memory.
Here, we include 30 other MATILDA problem instances from (Smith-Miles & Bowly 2015). in which the number of MISS is so large that they cannot be enumerated with 16GB memory. We evaluate the efficacy of our MLRMH method on these problem instances. Table B.6 presents the experimental results of our MLRMH algorithm compared against the RMH algorithm for solving the 30 MATILDA test problem instances. Our MIRMH algorithm able to prove optimality for 11 problem instances, while the RMH algorithm is only able to prove optimality for 8 instances. Fur- ther, the average optimality gap generated by our MLRMH method (8.96%) is statistically signifi- cantly better than that generated by the RMH algorithm (12.53%). By using the columns generated by our method to warm-start RMH, the average number of CG iterations is significantly reduced from 156.28 to 59.38. This also leads to significant reduction in the runtime of solving the LP and MIP. This clearly demonstrates that the RMH algorithm using the columms generated by our method as warm start performs significantly better than the RMH alone.
Finally, we use a set of larger DIMACS graphs, the number of vertices in which varies from 125 to 1, 000, to evaluate the generalization capability of our ML model. The cutoff time of MLRMH or RMH for solving each problem instance is set to ten hours. results (averaged over two independent runs) of the problem instances, whose LP relaxation can be optimally solved via CG within the cutoff time. Note that Gurobi with a ten-hour cutoff time may not be able to solve the reduced MIPs for large problem instances (c.g.. r1000.1), 1). resulting in a large optimality gap. Further, the time used by our MLCG method in generating columns for large problem instances may be non-negligible, because the computation of features requires solving the restricted master problem in each iteration of our algorithm. However, overall the RMH algorithm using the columns generated by our MLCG method as a warm start performs better than RMH alone.
the experimental
21

---

Published as a conference paper at ICLR 2023
Table B.5: The experimental results of MLRMH and RMH for solving the 33 MATILDA test prob- lem instances. The last row presents the p-value of the t-tests between the results generated by MLRMH and RMH. The ones with statistical significance (p-value < 0.05) are in bold.
Optimality Gap (%)
CG Iterations
LP Runtime
Total Runtime
Graph
Density
LB
MLRMH
RMH
MLRMH
RMH
MLRMH
RMH
MLRMH
RMH
gl34
10.00
16.40
28.52
206.88
258.56
236.12
544.03
g135
0.33
0.00
8.33
1.00
31.12
3.60
11.96
42.99
39.68
g144
0.37
10.00
10.00
1.00
18.36
4.21
4.04
4.72
5.92
g171
0.28
7
14.29
14.29
34.56
196.28
9.87
35.41
10.01
35.74
g173
0.36
8
0.00
7.00
4.92
110.28
4.59
15.37
4.81
16.67
g175
0.32
8
10.50
3.24
14.24
4.15
1.49
4,46
2.21
g214
0.26
7
0.00
2.29
1.04
22.56
3.96
1.84
4.06
2.14
0.30
10.00
20.00
7.58
46.05
25.36
60.95
g263
0.23
5
0.00
17.60
1.00
1.56
4.79
0,08
5.13
0.35
g329
0.21
0.00
7.20
1.00
1.00
4.71
0.05
4,88
0.33
g348
0.21
0.00
11.40
4.57
4.65
7.48
g417
0.40
8
3.50
12.00
22.36
254.72
14.86
159.33
15.39
159.68
g420
0.41
6
16.67
16.67
2.28
55.24
4.39
13.96
4.53
14.36
g474
0.34
11.11
20.00
1,00
25.76
5.07
6.20
6.35
7,86
B479
0.23
6
0.00
0.00
11.08
39.12
5.06
6,26
5.22
6.63
g486
53.19
28.63
$8.79
g487
0.41
12
8.33
8.33
25.24
180.68
45.98
165.59
69.10
196.42
3.33
1.18
g496
0.30
7
2.29
0.00
14,88
11.16
4,64
0.79
4.92
1.03
g498
0.35
7
2.86
1.00
4.00
4.51
4.69
0.36
5508
0.53
9
0.00
0.00
1.00
1.04
3.56
0.06
3.63
0.21
2509
0.52
9
8.89
10.22
1.00
1.08
3.42
0.08
3.54
0.25
g511
0.50
9
0.00
0.00
2.44
3,00
4.15
0.23
4,27
0.36
g530
0.51
0.00
2.53
1.00
79.16
5.96
49.58
6.24
$0.45
g556
0.35
10.00
16.80
20.68
203.88
29.53
247.74
145,90
436.49
g557
0.56
6.25
6.25
2.00
91.92
8.61
169.56
35.38
201.48
136.44
g598
0.48
13
7.69
15.39
3.04
145.08
9.02
173.66
102.27
188.43
7.52
4.82
g876
0.43
7
1.71
14.29
1.00
7.32
5.41
0.90
5.79
1.17
g894
0.43
7
1.71
6.68
93,92
5.24
14.97
5,39
16.17
g913
0.44
7
0.00
14.29
1.48
3.60
4.40
0.31
4.53
0.52
Mean
3.89
8.21
7.08
69.63
9.25
49.61
28.08
74.35
22

---

Published as a conference paper at ICLR 2023
Table B.6: The experimental results of the MLRMH and RMH algorithms for solving the 30 MATILDA test problem instances, in which the number of MISs is so large that they cannot be enumerated upfront using 16GB memory. The last row presents the p-values of the t-tests.
Optimality Gap (%)
CG Iterations
LP Runtime
Total Runtime
Graph
LB
MLRMH
RMH
MLRMH
RMH
MLRMH
RMH
MLRMH
RMH
g115
25
0.00
0.00
1.20
52.84
6.35
55.32
6.44
55.46
g133
6
23.33
32,00
178.32
348.72
162.23
244.24
306 206.22
276.87
g136
5
20.00
20.00
227.00
365.52
74.26
168.27
90.59
239.98
g140
8
12.50
12.50
73.04
277.60
25.51
87.73
27.92
92.32
g 166
6
16.67
16.67
229.40
407.84
92.99
151.73
103.00
180.35
g245
9
10.22
80.36
5.49
14.79
6.65
17.15
8249
33.33
34.80
155.16
9.71
16.34
14.87
g256
12.50
12.50
156.04
314.60
131.82
236.40
157.90
250.02
g296
7
14.29
14.29
175.24
337.32
169.35
269.26
252.70
286.23
g323
7
25.71
28.57
137.08
328.36
156.79
248.59
321.03
271.67
8326
9
7.11
11.11
120.84
307.28
66.12
119.24
85.43
124.04
g327
6
16.67
32.67
1.88
78.64
5.18
16.49
6.86
26.44
3347
6
2.00
16.67
1.00
19.04
5,55
3.06
5.88
3.84
g007
7
0.00
0.00
1.52
1.20
4.47
0.07
4.59
0.20
g416
21
0.00
0.00
1.52
13.88
5.55
7.72
5.74
7.99
4457
5
20.00
20.00
310.80
471.80
95.59
130.67
100.79
136.83
g460
5
20.00
284.68
15.99
$3.69
8472
7.20
155,80
195.43
155.58
250.68
477
16.67
4.56
4.44
0.36
4.76
0.60
g476
13.33
16.67
1.16
53.56
4.59
8.70
10.53
10.34
4477
8
0.00
5.00
27.04
171.84
11.09
39.85
11.67
43.84
g488
8
0,00
10,00
5.36
127.32
6.97
34.05
8.22
35.89
g490
6
1.33
14.67
1.00
2.76
5.33
0.16
5.78
0.63
g494
22
4.55
4.55
1.00
1.92
4,20
0.45
4.30
0.59
g499
7
0.00
0.00
1.00
1.00
4.42
0.05
4.55
0.15
g600
24
0.00
0.00
1.08
28.20
6.88
36.31
7.11
36,70
g623
0.00
3.08
53.32
5.46
17.32
5.53
17.48
g625
7.69
5.89
19.65
6.11
g647
0.00
80.24
5.31
43.87
5.50
g883
7
0.00
0.00
9.84
108.72
6.35
23.17
6.49
23.65
Mean P-value
59.38
156.28
37.39
74.77
58.30
84.99
5.49c-04
3.53e-08
5.58e-05
9.46c-04
Table B.7: The experimental results of the MIRMH and RMH algorithms for solving set of larger DIMACS problem instances. The last row presents the p-values of the t-tests.
Optimality Gap (%)
CG Iterations
LP Runtime
Total Runtime
Graph
LB
MI.MMH
RMH
MERMH
RMH
MIRMH
RMH
MIRMH
RMH
dsj:125.1
125
20.00
20.00
589,50
794,00
507.17
609.36
680.51
910.71
dsjc125,5
125
16
12.50
12.50
6,50
188.00
43.09
690.24
4363.00
2618.90
dxje125.9
2.33
15.55
40.52
15.73
40.88
r125.1
125
20.00
20.00
1,00
1.00
6.62
0.09
29.61
27.95
r125.1c le
125
46
0.00
0.00
L.00
1.00
5.83
0.73
5.87
0.78
r125.5
7.46
r250.
250
64
0.00
0.00
1.00
1,00
27.90
9,33
27.94
9.49
dsjc250.9
250
71
1,41
1.41
L.00
71,50
102.12
4304.90
119.71
4378,50
1e450_15a
450
73.33
207.00
510.00
$71.17
1091.20
36005.00
36006.00
le450. 15h
450
15
63.33
70.00
199,50
437.00
483.72
1112.40
36004.00
36008.00
1o450 25b
450
25
26.00
32.00
L.00
2.00
104.13
3.08
36003.00
36009.00 00
r1000.1
1000
20
90.00
3.50
505.00 08
36002.00
36002.00
Mean
24.56
84.21
168.54
198.34
656.74
12439.00
12668.00
P-value
2,22c-022
2.63c-02
2.216-01
5.73e-01
23


Reviews:
[{"review_id": "hm010sGdmz", "reviewer": "Reviewer_795f", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 Column Generation method for Vertex Coloring Problem, based on Machine Learning. The column in this case is a maximal independent set, which can potentially share the same color. Specific features were designed for this problem: 1) problem-specific features derived from the graph; 2) statistical measures computed from sample solutions; 3) linear program (LP) features. Various ML classifiers (KNN, Decision Trees, SVM) are trained on instances with known optimal solutions, in order to predict high quality maximal independent sets (MIS). The MLCG algorithm samples randomly generated MIS or uses a genetic algorithm like procedure to evolve new ones and keeps a subset of the highest quality ones. The generated columns are then fed into the Gurobi solver. A good sized experimental evaluation shows that MLCG outputs higher quality columns compared with other strategies, like random CG, Reduced Cost, MLF and Full. ", "summary_of_the_review": "The paper shows an improvement in Column Generating quality with the help of ML classifiers, for Vertex Coloring. While there is some novelty in the design of the features and of the method, the scope is still very focused on a single type of problem (VC), and the experimental evaluation is still limited to a small number of graphs of modest size.", "strength_and_weaknesses": "Strengths:\nFor the specific Vertex Coloring Problem, the features that are defined are natural and prove to be relevant in characterizing the quality of MIS. The method is clear and combines well understood ML classifiers. The experimental evaluation confirms the quality of the method.\n\nWeaknesses:\nIt is not clear how this method can be used for problems other than Vertex Coloring, although the authors claim that the method is generic, and mention in conclusion that vehicle routing may lend itself to a similar treatment. \nThe size of the test graphs is small, with only 100 vertices. Any indication of how this method would scale for larger graphs?", "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": "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": "7j9zTX0e5kp", "reviewer": "Reviewer_DZnS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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 combines the machine learning technique within the traditional column generation method for solving combinatorial optimization problems. Specifically, the authors propose to use machine learning algorithms to predict high quality columns that belong to an optimal integer solution. Here the machine learning model is trained using training instances that correspond to columns (MISs in the case of VCP), where the features of each instance are constructed from various perspectives. \n\nThe main contribution of this paper is, it presents a nice integration of MIP technique with the prediction power of machine learning. Instead of fully replying on ML predict the optimal solution for combinatorial optimization problem, here in this paper it simply leverages the power of ML technique for column selection. This idea in alignment with many recent literatures about learning to branch, learning to cut in MIP, becomes an increasingly exciting area in both communities.\n", "summary_of_the_review": "Overall, I think this paper has made significant contribution to the community of MIP or CO by leveraging the power of ML techniques. Even though this type of method is completely empirical-based and often times not the optimal method in practice, such attempt is still encouraging and in my opinion, it's not impossible to see major breakthroughs in combinatorial optimization in the future through unconventional approaches like ML. Based on the novelty and potential carried in this paper, I recommend this paper to be accepted. ", "strength_and_weaknesses": "Main strength: This paper is very nicely written with little typos and easy to follow. The numerical experiments are extensive and convincing. The main idea of this paper is novel and interesting and is extendable for many other types of combinatorial optimization problems, it provides another bridge between communities of ML and MIP. \n\nMain weakness: 1. The constructed features for training instances seem too arbitrary, a detailed explanation of the intuition and analysis can be helpful.     \n2. In the numerical experiment, all the benchmark methods are variants of column generation. A more detailed comparison with other state-of-art methods for VCP should be considered (either based on tighter LP relaxations or combinatorial properties of VCP). Based on the same reason, since for many classic combinatorial optimization methods there have already been quite successful combinatorial algorithms in the literature, simply extending the same idea of this paper to tackle those other problems cannot be trusted to outperform other algorithms. \n\nminor comments/questions: 1. In the formulation given by (1)-(3), since in the graph of VCP, every node can only be colored exactly once, should the $\\geq$ in (2) be equality?     \n2. You mentioned that the set covering formulation (1)-(3) has a tight LP relaxation. Can you add a reference for this statement? Is it also true that, if you select a subset $\\tilde{\\mathbb{S}}$ of $\\mathbb{S}$ and replace $\\mathbb{S}$, the binary IP (1)-(3) still has a tight LP relaxation?  \n3. In constraint (5), $\\tilde{\\mathbb{S}}$ should be $\\tilde{\\mathbb{S}}_v$, which has not been defined until later in Section 3.1.   \n4. In Algorithm 1, at every iteration you keep the top $\\epsilon$ percentage of MISs, here in convention $\\epsilon$ is used to denote small constant. Here you should either say \"top $\\epsilon$ of \" or use some other notation such as $\\kappa$. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6fgvj83QaH", "reviewer": "Reviewer_igoj", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 paper proposes a machine-learning-based approach for generating columns for LP relaxations of vertex cover problems (VCPs). The paper (implicitly) assumes that the VCPs are generated from some distribution and it proposes to learn a classifier to predict if a MIS is a part of the optimal solution, given a training set of VCP problem instances. Then, the standard column generation algorithm is used with the learned classifier to choose columns. The experiments using real data sets show that the proposed approach tends to produce better solutions.", "summary_of_the_review": " The idea itself is promising, but the technical contribution of the paper seem not significantly strong.", "strength_and_weaknesses": "Strength:\n- A motivated new approach to combinatorial optimization\n\n\nWeaknesses\n- The approach is not general, i.e., specifically designed for a series of optimization problems generated from similar distributions\n- The idea itself is interesting, but there is no new technique introduced\n\nThe proposed idea of learning relevant columns (MISs) from a series of problems would make sense when such similar problems are available. But, the approach has the limitation that it is not suitable to apply for new problems obtained from different distributions. The learning techniques themselves are quite standard. So, I feel that the technical contribution of the paper is not significantly strong though the idea itself is promising.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster